常见排序算法的C++实现

算法的C++实现"/>

常见排序算法的C++实现

常见排序算法c++实现

文章目录

• 常见排序算法c++实现
• 前言
• 一、冒泡排序
• 二、选择排序
• 三、插入排序
• 四、希尔排序
• 五、快速排序
• 六、归并排序

前言

应为快毕业了，想回顾一下数据结构和算法 @_@
所以花了一点时间把排序算法实现了一下。（至于各个算法之间的比较啊，优缺点啊，什么时间复杂度，空间复杂度啊，本文没有）

提示：以下是本篇文章正文内容，下面案例可供参考，我们从简单的开始

一、冒泡排序

冒泡简单的说就是两两比较，最直接也是最简单的

void bubbleSort(int * arr, int size)
{int time=size;for (int j = 0; time>1; j++){for (int i = 0; i < time-1; i++){if (arr[i] > arr[i+1]){int temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}time--;}
}

二、选择排序

正如他的名字，每遍历一次挑选出最大（最小）的放到队列里
代码如下（示例）：

void selectSort(int * arr, int size)
{for (int i = size-1; i > 0; i--){int max = i;for (int j = 0; j < i; j++){if (arr[j] > arr[max]){int temp = arr[j];arr[j] = arr[max];arr[max] = temp;}}}
}

三、插入排序

就像我们抓牌一样，抓一张插到对应的位置

void insertSort(int * arr, int size)
{for (int i = 1; i < size; i++){int j = i - 1;int temp = arr[i];while (arr[j] > temp && j >= 0){arr[j+1] = arr[j];j--;}arr[j+1] = temp;}//这个就不那么好了/*for (int i = 0; i < size; i++){for (int j = i+1; j < size; j++){for (int k = 0; k <= i; k++){if (arr[j] < arr[k]){int temp = arr[j];arr[j] = arr[k];arr[k] = temp;}}}}*/
}

四、希尔排序

对插入排序的升级，比插入排序更快

void shellSort(int * intArr, int size)
{int step = size / 2;   //原始步长int nTemp = 0;while (step > 0){for (int i = step; i < size; i++){nTemp = intArr[i];int j = i - step;while (j >= 0 && intArr[j] > nTemp){intArr[j + step] = intArr[j];j = j - step;}intArr[j + step] = nTemp;}step /= 2;} /*int step = size / 2;while(step > 0){for (int j = 0; j < size; j++){for (int i = j; i < size; i += step){int k = i - step;int temp = arr[i];while (arr[k] > temp&&k >= 0){arr[k + step] = arr[k];k -= step;}arr[k + step] = temp;}}step = step / 2;}*/
}

五、快速排序

递归版，可能有BUG哈

void quick(int * arr, int left, int right)
{int key = arr[left];int l = left, r = right;while (l < r){while (l < r && arr[r] >= key){r--;}while (l < r && arr[l] < key){l++;}if (l < r){swap(&arr[l], &arr[r]);}}if (left < right){quick(arr, left, l);quick(arr, l+1, right);}
}void swap(int * a, int * b)
{int temp = *a;*a = *b;*b = temp;
}void quickSort(int * arr, int size)
{quick(arr,0,size-1);
}

六、归并排序

void mergeSort(int * arr, int size)
{int*arr1 = 0;int*arr2 = 0;if (size > 1){arr1 = new int[size / 2];arr2 = new int[size - size / 2];memcpy(arr1, arr, size / 2 * sizeof(int));memcpy(arr2, arr + size / 2, (size - size / 2) * sizeof(int));mergeSort(arr1, size / 2);mergeSort(arr2, size - size / 2);}if (size == 1)return;int i = 0;int j = 0;int k = 0;while (i < size / 2 && j < size - size / 2){arr[k++] = arr2[j] < arr1[i] ? arr2[j++] : arr1[i++];}//arr[k] = arr2[j] < arr1[i] ? arr2[j++] : arr1[i++];if (i > size / 2 - 1 && j< size - size / 2){memcpy(&arr[k], &arr2[j], sizeof(int)*(size - size / 2 - j));}if (j > size - size / 2 - 1&& i < size / 2){memcpy(&arr[k], &arr1[i], sizeof(int)*(size / 2 - i));}
}