排序算法集合

1. 冒泡排序

排序的过程分为多趟，在每一趟中，从前向后遍历数组的无序部分，通过交换相邻两数位置的方式，将无序元素中最大的元素移动到无序部分的末尾（第一趟中，将最大的元素移动到数组倒数第一的位置；第二趟中，将第二大的元素移动到数组倒数第二的位置，以此类推）。

每排一趟，数组末尾的有序序列就向前增长一个元素，数组前端的无序部分就减少一个元素。

优化：某趟中，一次交换也没有发生，说明数组已有序，直接结束排序。

整个排序的过程中，剩余无序元素中最大的元素就像气泡一样不断“上浮”到数组末尾，所以该算法被称作冒泡排序。

冒泡排序的思想很简单，类似于递归：

要实现整个数组（n个元素）的有序，可以将数组分为前（n-1）个元素和最后一个元素。

首先确保最后一个元素有序（最大），然后再用相同的方式解决前（n-1）个元素组成的数组的有序性问题。

当然，你也可以当我上面这段话是放屁，因为冒泡排序的算法太过简单，按上面的方式来理解确实小题大做。

但伴随着简单算法的往往是极高的开销，这也使得冒泡排序没有任何的实际意义，仅作教学作用。

可以说冒泡排序是最拉的排序算法，接下来讲到的所有排序算法，效率都至少为其的十倍以上（实测结果非理论分析，理论分析出的时间复杂度几乎相同）

时间复杂度：最坏情况（元素逆序） $O(n^{2})$ ，最好情况（已有序） $O(n)$

空间复杂度： $O(1)$

//冒泡排序
void BubbleSort(int* arr, int len)
{for (int i = 0; i < len; i++){int flag = 1;for (int j = 0; j < len - 1 - i; j++){if (arr[j] > arr[j + 1]){flag = 0;swap(&arr[j], &arr[j + 1]);}}if (flag)return;}
}

2. 选择排序

顾名思义，就是在每趟排序中，直接选出最大的元素（的下标），然后将其与无序部分末尾的元素进行交换，同时无序部分的末尾向前缩短一个元素。

相对于冒泡排序，二者的做法很像，但选择排序省去了交换相邻元素的过程（效率提高的关键），手段更加直接。

优化：在选出最大元素的同时，将最小元素也选出来，两端同时排序。

void SelectSort(int* arr, int len)
{int begin = 0, end = len - 1;while (begin < end){int max = begin;int min = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] < arr[min])min = i;if (arr[i] > arr[max])max = i;}swap(&arr[begin], &arr[min]);swap(&arr[end], &arr[max]);begin++;end--;}
}

但是，直接进行优化之后的算法会存在一个小bug：

假设在每趟排序中，将最大元素和最小元素选出来之后，先让最小元素交换到无序部分的前端，再让最大元素交换到无序部分末尾。

那么，当最大元素刚好在无序部分前端时，就会发生如下的过程：

1. 首元素（最大元素）与最小元素交换

2. 最大元素（首元素，此时该位置为最小元素）与末尾元素交换

可以按照下面的方式解决。

//选择排序
void SelectSort(int* arr, int len)
{int begin = 0, end = len - 1;while (begin < end){int max = begin;int min = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] < arr[min])min = i;if (arr[i] > arr[max])max = i;}swap(&arr[begin], &arr[min]);if (begin == max)swap(&arr[end], &arr[min]);elseswap(&arr[end], &arr[max]);begin++;end--;}
}

时间复杂度： $O(n^{2})$

空间复杂度： $O(1)$

由于选择排序无法提前结束，所以其时间复杂度为稳定的 $O(n^{2})$ 。

但是，相比于冒泡排序，选择排序在整体上减少了频繁交换的消耗，在一般情况下，效率要远好于冒泡排序。

3. 插入排序

上面的两种算法是在为某个位置选择合适的元素填入，而插入排序则是在为某个元素选择合适的位置去存放，也正是这一差别，使其成为了这三位难兄难弟的老大哥。

为某个元素选择合适的位置，必然只有在其他元素都有序的情况下才能做到（或者局部有序）。

尽管数组在整体上无序，我们却可以将开头的一个元素看作是无序，接着将第二个元素插入其中。

于是，前两个元素就变得有序了，我们又可以将第三个元素插入其中……以此类推，数组便逐渐有序了。

插入排序，就是将数组分为两个部分：数组前端的有序部分（开始只有一个元素），和数组后半段的无序部分。然后将无序部分的元素逐个插入到有序部分。

而对于插入，我们采用的办法是：

从后向前遍历有序部分，如果当前位置的元素比要插入的元素大，则将当前位置的元素向后移动一个元素（为要插入的元素腾位置）；如果当前位置的元素要比插入的元素小，则将要插入的元素插入到当前位置的后面（自己原本的位置，或者是第一种情况腾出来的位置）。

优化：可优化为希尔排序，详见下文。

//插入排序
void InsertSort(int* arr, int len)
{for (int i = 1; i < len; i++){int temp = arr[i];int j = i;while(j > 0 && arr[j - 1] > temp){arr[j] = arr[j - 1];j--;}arr[j] = temp;}
}

时间复杂度：最坏情况（元素逆序） $O(n^{2})$ ，最好情况（已有序） $O(n)$

空间复杂度： $O(1)$

虽然看上去与冒泡排序一模一样，但是其实际的消耗要小得多，相比于选择排序也要更优。

4. 希尔排序

在插入排序算法中，越小的元素越早插入越好，越大的元素越晚插入越好。

当元素恰好逆置时，算法的消耗较大，几乎等价于冒泡排序。

而希尔排序就是希尔为解决插入排序痛点而设计的算法，解决这一痛点的方法就是，先对整个数组进行跨度较大的粗调，再进行更加细致的调整（只有数据量较大时希尔排序的优化才有意义，否则直接使用插入排序即可）。

我们发现，如果较大的元素插入得较早，之后就会进行大量的操作将该元素后移，并且每次只移动一个元素。

如果我们能够快速地（一次跳过多个元素）将这些较大的元素调整到靠后的位置，使得数组基本有序，插入排序的时间复杂度就会无限接近于最好情况。

那么如何进行粗调呢？

1. 将数组的元素分为若干组（记组数为gap），每一组元素的下标模上gap所得的值相同（即每一组元素的下标为模gap的同余关系，类似于分层抽样）。

2. 对每一组的元素进行插入排序（这样一来，较大的元素每次向后移动的元素个数为gap，粗调的效率就远高于直接插入排序）。

3. 缩小gap的值，重复上述过程（一般做法为gap=gap/3+1，+1的目的是使得最后一趟排序时gap为1，也就是对整个数组进行一次插入排序）。

//希尔排序(插入排序优化)
void ShellSort(int* arr, int len)
{int gap = len;while (gap > 1){gap = gap / 3 + 1;for (int group = 0; group < gap; group++){for (int i = group + gap; i < len; i += gap){int temp = arr[i];int j = i;while (j > group && arr[j - gap] > temp){arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}}}
}

可以看到，最内层的两层循环其实就是将插入排序中的“1”替换为了“gap”，将起点从“0+1”改成了“group + gap”。

控制group的循环就是在切换插入排序的组别。

优化：如果觉得四层循环看起来很唬人的话，我们也可以优化掉一层循环（但效率不变）

//希尔排序X(各组同时排，优化掉三重循环，但效率相同)
void ShellSort_X(int* arr, int len)
{int gap = len;while (gap > 1){gap = gap / 3 + 1;for (int i = gap; i < len; i++){int temp = arr[i];int j = i;while (j > 0 && arr[j - gap] > temp){arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}}
}

时间复杂度：平均情况 $O(n^{1.3})$ ，最好情况 $O(n(logn)^{2})$

空间复杂度： $O(1)$

初见希尔排序的代码，可能会误以为其效率极低，但实际上希尔排序的效率极高，甚至在数据量较大时，效率高出上文介绍的算法不止一个量级（百倍以上）！

接下来的几种算法，于希尔排序同属一个量级，但效率有略微差别。

其排序的过程极其复杂，具有许多不可控因素，不能简单地通过循环的层数来计算时间复杂度。

希尔排序的代码很难理解，但是其解决问题的思想却很值得我们学习借鉴。

5. 堆排序

详见这篇文章：全面详解堆-CSDN博客

6. 快速排序

详见这篇文章：C语言实现快速排序算法-CSDN博客

值得一提的是，快速排序正如其名，快且综合实力强。

C语言中，qsort函数的底层算法便是采用的快速排序算法。

7. 归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

以二路归并为例，假如一个数组从中间位置被分为了前后两个部分，而这两个部分都是有序的，那么我们就可以采用与合并两个有序链表相同的思路：比较两个序列中的最小值，将较小的那个插入到新的序列中，不断重复这样的操作，直到原序列中的值全部插入到新序列中。

但前提是，前后两个子序列都要有序。

所以我们的首要任务是使得前后两个子序列有序，而使其有序的方式依然如上。

于是我们找到的递归的思路：

void _MergeSort(int* arr, int* copy, int begin, int end)
{if (begin >= end)return;//区间不能分为[begin,mid-1]和[mid,end]int mid = (begin + end) / 2;_MergeSort(arr, copy, begin, mid);_MergeSort(arr, copy, mid + 1, end);//归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int cur = begin;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){copy[cur++] = arr[begin1++];}else{copy[cur++] = arr[begin2++];}}while (begin1 <= end1) { copy[cur++] = arr[begin1++]; }while (begin2 <= end2) { copy[cur++] = arr[begin2++]; }memcpy(arr + begin, copy + begin, (end - begin + 1) * sizeof(int));
}//归并排序
//时间复杂度O(n*logn)，空间复杂度O(n)
void MergeSort(int* arr, int len)
{int* copy = (int*)malloc(sizeof(int) * len);if (copy == NULL){perror("malloc fail");return;}_MergeSort(arr, copy, 0, len - 1);free(copy);
}

和快速排序类似，既然这个算法是用递归的方式实现的，我们就会考虑其非递归的实现方式。

但与快速排序不同，快速排序的递归方式类似于二叉树的前序遍历，但是归并排序类似于后序遍历。

参考栈与递归的实现-CSDN博客会发现，二叉树前序遍历的非递归实现很简单，但是后序遍历的非递归实现则十分麻烦。

将递归算法转化为非递归算法，除了利用栈来模拟实现，也可以尝试直接利用迭代来实现。

思路就是将数组按gap个数据为一组分为多组，每两个相邻的组进行插入合并，随后gap变为原来的两倍，再次重复以上过程，直到gap大于数组长度。

当然，最后一组可能分配不到gap个数据，也可能只能分出奇数个组，针对这些问题，进行插入合并（归并）的代码进行了调整。

//归并排序非递归
void MergeSortNonR(int* arr, int len)
{int* copy = (int*)malloc(sizeof(int) * len);if (copy == NULL){perror("malloc fail");return;}for (int gap = 1; gap < len; gap *= 2){for (int i = 0; i < len; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//第二组都越界，不归并了if (begin2 >= len){break;}//第二组越界部分，修正并归并if (end2 >= len){end2 = len - 1;}int cur = i;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){copy[cur++] = arr[begin1++];}else{copy[cur++] = arr[begin2++];}}while (begin1 <= end1) { copy[cur++] = arr[begin1++]; }while (begin2 <= end2) { copy[cur++] = arr[begin2++]; }memcpy(arr + i, copy + i, ((end2 - i + 1) * sizeof(int)));}}free(copy);
}

时间复杂度： $O(nlogn)$