各种排序算法整理各种排序算法整理

本文主要对七种排序算法做宏观上的总结，没有死扣代码细节，意在充分理解各种排序算法的思想。

文章图片
排序算法关系示意图 I、上帝视角看排序 【各种排序算法整理】排序算法常出现在各种面试题中，对于算法时间空间复杂度的分析，稳定性要求等都需要灵活掌握。
1.1 冒泡排序基本思想：两两比较相邻的关键字，如果反序则交换。
时间复杂度：最好是O(n)，最坏的情况是O(n^2)。
改进思路：
1、设置标志位，明显如果有一趟没有发生交换（flag=false），说明已经有序；
2、记录下一轮下来标记的最后位置，下次从头部遍历到这个位置就OK。
1.2 简单选择排序基本思想：通过n-i次关键字之间的比较，从n-i+1个元素中选择关键字最小的元素，并和第i(1<=i<=n)个元素交换。
时间复杂度：为O(n^2)，但简单选择排序的性能略优于冒泡排序。
1.3 直接插入排序基本思想：将一个元素插入到已经排好序的有序表中，从而得到一个新的，元素数新增1的有序表。
时间复杂度：为O(n^2)，但是比冒泡排序和选择排序的性能要更好一些。
1.4 希尔排序基本思想：先将整个待排序元素序列分割成若干个序列（由相隔某个“增量”的元素组成），分别进行直接插入排序，然后依次缩减增量在进行排序，待整个序列中元素基本有序（增量足够小）时，在对全体元素进行一次直接插入排序（增量为1）。
时间复杂度：其时间复杂度为O(n^1.5)。
1.5 归并排序基本思想：假设初始序列含有n个元素，则可以看成n个有序的子序列，每个子序列长度为1，然后两两归并，得到（不小于n/2的最小整数）个长度为2或1的有序子序列，然后在两两归并，...如此重复，直到得到一个长度为n的有序序列为止。
时间复杂度：时间复杂度为O(nlgn)，空间复杂度为O(n+lgn)，如果非递归实现归并，则避免了递归时深度为lgn的栈空间，空间复杂度为O(n)。
1.6 堆排序关于堆排序的详细说明见wenmingxing 堆排序初探
时间复杂度：堆排序的时间复杂度为O(nlgn)。
1.7 快速排序关于快速排序的详细说明见wenmingxing 深入理解快排
时间复杂度：快排的时间复杂度为O(nlgn)。
II、七种排序算法比较

文章图片
排序算法比较 III、参考代码下面参考代码中没有堆排序和快速排序的代码，可以见上面的链接文章。

#include using namespace std; void swap1(int *left, int *right) { int temp = *left; *left = *right; *right = temp; }void swap2(int &left, int &right) { int temp = left; left = right; right = left; }void swap3(int &left, int &right) { if (&left != &right) { left ^= right; right ^= left; left ^= right; } }/*****************************************************************/ /* 冒泡排序时间复杂度最好的情况为O(n),最坏的情况是O(n^2) * 基本思想是:两两比较相邻记录的关键字,如果反序则交换 */void BubbleSort1(int arr[], int num) { int i, j; for (i = 0; i < num; i++) { for (j = 1; j < num - i; j++) { if (arr[j - 1] > arr[j]) swap1(&arr[j - 1], &arr[j]); } } }// 改进思路：设置标志位，明显如果有一趟没有发生交换（flag = flase)，说明排序已经完成. void BubbleSort2(int arr[], int num) { int k = num; int j; bool flag = true; while (flag) { flag = false; for (j = 1; j < k; j++) { if (arr[j - 1] > arr[j]) { swap1(&arr[j - 1], &arr[j]); flag = true; } } k--; } } //改进思路：记录一轮下来标记的最后位置，下次从头部遍历到这个位置就Ok void BubbleSort3(int arr[], int num) { int k, j; int flag = num; while (flag > 0) { k = flag; flag = 0; for (j = 1; j < k; j++) { if (arr[j - 1] > arr[j]) { swap1(&arr[j - 1], &arr[j]); flag = j; } } } } /*************************************************************************//**************************************************************************/ /*插入排序: 将一个记录插入到已经排好序的有序表中, 从而得到一个新的,记录数增1的有序表 * 时间复杂度也为O(n^2), 比冒泡法和选择排序的性能要更好一些 */void InsertionSort(int arr[], int num) { int temp; int i, j; for (i = 1; i < num; i++) { temp = arr[i]; for (j = i; j > 0 && arr[j - 1] > temp; j--) arr[j] = arr[j - 1]; arr[j] = temp; } }/****************************************************************************//*希尔排序:先将整个待排元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（增量为1）。其时间复杂度为O(n^3/2),要好于直接插入排序的O(n^2) */ void ShellSort(int *arr, int N) { int i, j, increment; int tmp; for (increment = N / 2; increment > 0; increment /= 2) { for (i = increment; i < N; i++) { tmp = arr[i]; for (j = i; j >= increment; j -= increment) { if (arr[j - increment] > tmp) arr[j] = arr[j - increment]; else break; } arr[j] = tmp; }} }/**************************************************************************//* 简单选择排序(simple selection sort) 就是通过n-i次关键字之间的比较,从n-i+1 * 个记录中选择关键字最小的记录,并和第i(1<=i<=n)个记录交换之 * 尽管与冒泡排序同为O(n^2),但简单选择排序的性能要略优于冒泡排序 */void SelectSort(int arr[], int num) { int i, j, Mindex; for (i = 0; i < num; i++) { Mindex = i; for (j = i + 1; j < num; j++) { if (arr[j] < arr[Mindex]) Mindex = j; }swap1(&arr[i], &arr[Mindex]); } }/********************************************************************************/ /*假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后 * 两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,... * 如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序 * 时间复杂度为O(nlogn),空间复杂度为O(n+logn),如果非递归实现归并,则避免了递归时深度为logn的栈空间 * 空间复杂度为O(n) *//*lpos is the start of left half, rpos is the start of right half*/ void merge(int a[], int tmp_array[], int lpos, int rpos, int rightn) { int i, leftn, num_elements, tmpos; leftn = rpos - 1; tmpos = lpos; num_elements = rightn - lpos + 1; /*main loop*/ while (lpos <= leftn && rpos <= rightn) if (a[lpos] <= a[rpos]) tmp_array[tmpos++] = a[lpos++]; else tmp_array[tmpos++] = a[rpos++]; while (lpos <= leftn) /*copy rest of the first part*/ tmp_array[tmpos++] = a[lpos++]; while (rpos <= rightn) /*copy rest of the second part*/ tmp_array[tmpos++] = a[rpos++]; /*copy array back*/ for (i = 0; i < num_elements; i++, rightn--) a[rightn] = tmp_array[rightn]; }void msort(int a[], int tmp_array[], int left, int right) { int center; if (left < right) { center = (right + left) / 2; msort(a, tmp_array, left, center); msort(a, tmp_array, center + 1, right); merge(a, tmp_array, left, center + 1, right); } }void merge_sort(int a[], int n) { int *tmp_array; tmp_array = (int *)malloc(n * sizeof(int)); if (tmp_array != NULL) { msort(a, tmp_array, 0, n - 1); free(tmp_array); }else printf("No space for tmp array!\n"); }

【参考】
[1] 《大话数据结构》
[2] 十种排序算法总结