文章目录

• 排序的概念
• • 常见的排序算法
• 冒泡排序
• 堆排序
• 插入排序
• 希尔排序（缩小增量排序）
• 选择排序
• 快速排序
• • 划分
  • • 一、Hoare版本
    • 二、挖坑法
    • 三、前后指针
  • 整体排序——递归
  • 优化
  • • 针对选key的优化——三数取中
    • 小区间优化
  • 整体排序——迭代
• 归并排序
• • 递归
  • 迭代
  • 内排序 外排序
• 计数排序
• 总结

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

• 稳定的意义：

  • 稳定的排序算法不会改变相同的值的相对顺序，而相同的值可能带有不同的含义。

  • 比如将学生按总分排名，如总分相同，按数学排名。那么先将他们按数学排名，然后使用稳定的算法对总分排名，这样就能保证总分相同时数学排名的相对位置不变。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

常见的排序算法

我们之前已经学过冒泡排序和堆排序，下面简单复习一下。

注：本文的所有排序默认排升序

冒泡排序

冒泡排序一般是第一个学习的排序算法。我们也用它模拟过qsort的传参实现了一个通用的冒泡排序👉qsort函数用法 | 模拟qsort实现一个通用的冒泡排序_世真的博客-CSDN博客

下面简单复习一下。

• 每趟从第一对相邻元素开始进行比较，如果第一个比第二个大（小），那么就交换它们两个。
• 每趟都能将一个元素放到正确的位置
• 重复以上步骤（除了已排序的部分）

代码如下：

void Swap(int* a, int* b){int tmp = *a;*a = *b;*b = tmp;}void BubbleSort(int* a, int n){for (int i = 0; i < n; i++){int flag = 0;for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){flag = 1;Swap(&a[j], &a[j + 1]);}}if (flag == 0)break;}}

这里定义的flag是对冒泡排序的优化。

我们知道，冒泡排序最坏的情况，时间复杂度为 O ( n 2 ) O(n^2) O(n2)，最好的情况呢？

最好情况就是数组已经有序，但是两层循环依然会全部走一遍，进行两两比较，时间复杂度依然是 O ( n 2 ) O(n^2) O(n2)

所以我们定义一个flag，当某一趟排序没有发生交换时，就说明数组已经有序，然后跳出循环。

这样对于接近有序的序列就提高了排序效率。

堆排序

在学习堆的时候已经是实现了。👉[数据结构二叉树顺序结构之堆|堆实现|堆排序|TOPK_世真的博客-CSDN博客](https://blog.csdn.net/CegghnnoR/article/details/124119000?spm=1001.2014.3001.5502)

这里贴出代码：

void AdjustDown(int* a, size_t size, size_t root){size_t parent = root;size_t child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] > a[child]) {++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void HeapSort(int* a, int n){for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}size_t end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}}

插入排序

一般也被称为直接插入排序，插入排序是一种最简单的排序方法。

基本思想就像我们玩斗地主抓牌，开始时我们的左手为空，每次摸到牌之后，我们就会选择一个合适的位置将这张牌插入进去，为了找到合适的位置，我们将它与已在手中的每张牌进行比较。这样手中的牌就总是有序的。

---

• 插入排序一般都是最后一个元素插到前面的元素中，但是前面的元素必须有序。那么可以把第一个元素看成有序，第二个元素往里面插，这样前两个元素有序，然后第三个元素往里面插，前三个就有序，第四个往里面插$\cdots \cdots$

• 单趟插入排序：假设下标[0,end]的元素有序，下标end+1的元素和前面的元素依次从后往前比较，比它大的都往后移动，直到遇到比它小的，就把它插入到小的元素的后面。或者与[0,end]个元素都比较完毕，就把它插入到最前面。

void InsertSort(int* a, int n){for (int i = 0; i < n - 1; ++i){int end = i;// 单趟排序：[0, end]有序 end+1位置的值，插入进入，保持他依旧有序int tmp = a[end + 1];while (end >= 0){if (tmp < a[end])// 降序则是比它小的往后移动，只要把  即可。{a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}}

---

直接插入排序特性总结：

时间复杂度分析：

最好情况：数组已经排好序，时间复杂度$O(n)$

最坏情况：逆序，每个元素都要与前面所有元素都比较一次，等差数列求和。时间复杂度为 O ( n 2 ) O(n^2) O(n2)

对于插入排序来说，接近有序的序列排序是比较快的。

空间复杂度$O(1)$

---

与冒泡排序比较

对于顺序有序的数组，如 1, 2, 3, 4, 5, 6, 8, 7

插入排序只需要走一趟，比较8次。

冒泡排序走第一趟可以排到有序，但是发生了交换，flag不为0，所以还要再走一趟，比较7 + 6 = 13次。不优化要比较28次。

对于局部有序的数组，如 3, 4, 2, 8, 7, 9, 5, 9

插入排序只要比较12次。

冒泡排序要比较22次，不优化也要比较28次，优化的效果不明显。

所以，顺序有序，插入排序和冒泡排序是差不多的。

但是如果局部有序，或者接近有序，那么插入排序的适应性更高。

希尔排序（缩小增量排序）

希尔排序是插入排序的一种，是直接插入排序的一种更高效的改进版本。

我们知道插入排序在数组接近有序时更好，但是大多数情况都是无序的，这个要求太高了。

希尔排序则是将排序分为两部分。

1. 预排序 （使数组接近有序）
2. 直接插入排序

预排序就是将元素进行分组，如gap = 3，就是每间隔为3的元素为一组，总共分为3组。

然后分别对这gap组元素进行插入排序。

这样排出来的结果为1 3 2 4 6 2 7 9 5 8

明显比原数组更接近有序了。

并且不难发现，gap越小越接近有序。gap越大，小的数可以更快到前面，大的数可以更快到后面。

---

先来写这部分代码：

第一层循环控制每一组的第一个元素，第二次循环对这一组进行插入排序。

int gap = 3;for (int i = 0; i < gap; ++i) //控制组{for (int j = i; j < n - gap; j += gap) //控制每一组中的插入排序{int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tmp;}}

也可以写成这样，只要两层循环：

第一组先排前两个，然后去排第二组的前两个，接着排第三组的前两个，然后排第一组的前三个$\cdots \cdots$

int gap = 3;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tmp;}

两种写法本质上一样。

---

最后就是gap的控制。

gap初始给多少？不同的数据量肯定要设定不同的gap；而且为了使数组越来越接近有序，gap肯定是要缩小的，怎么缩小？

其实gap的给值和缩小官方并没有给固定的方式。这边一种建议的写法就是初始为n / 3 + 1，以后每一次都有gap = gap / 3 + 1直到gap为1。

gap > 1的时候都是在进行预排序，gap == 1时就是直接插入排序。

void ShellSort(int* a, int n){int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tmp;}}}

---

希尔排序快不快？就这样看没什么感觉，我们来测试一下。

用以下测试代码生成一些随机数，然后分别对不同的排序算法计时

void TestOP(){srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();BubbleSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);free(a1);free(a2);free(a3);free(a4);}

这边拿10万个数测试了一下。结果非常的amazing啊！希尔排序不仅远比插入排序快，甚至赶上了堆排序。

---

所以希尔排序还是非常快的，下面来讨论一下希尔排序的时间复杂度。

希尔排序的时间复杂度很难计算，这里给出一个粗略的估计：

gap很大时，数据跳得很快，里面的循环几乎可以忽略不计，差不多是$O(n)$。当gap很小时，数组已经很接近有序，差不多也是$O(n)$。最外层可控制gap的循环，每次令gap/3，知道最后为1，差不多是 O ( log⁡ 3 n ) O(\log_3n) O(log3​n)。所以总的时间复杂度大概就是 O ( n log⁡ 3 n ) O(n\log_3n) O(nlog3​n)

具体的计算涉及一些数学上的难题。因为gap的变化不固定，很多书中给出的希尔排序的时间复杂度也不固定。比如有些地方也给出了 O ( n 1.3 ) O(n^{1.3}) O(n1.3)的时间复杂度。

选择排序

选择排序也是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，然后与序列第一个元素交换，然后从剩余未排序元素中选出一个最小的，与已排序序列后一个元素交换，以此类推，直到待排序的数据元素的个数为零。

与堆排序的不同就在于，它是通过遍历选出最大或最小的元素，这肯定不如堆的调整快。

代码很简单，我们直接写一个优化版本，一次遍历同时选出最大和最小两个数。

void SelectSort(int* a, int n){int left = 0, right = n - 1;while (left < right){int mini = left, maxi = left;for (int i = left + 1; i <= right; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left], &a[mini]);// 如果left和maxi重叠，修正一下maxi即可if (left == maxi)maxi = mini;Swap(&a[right], &a[maxi]);left++;right--;}}

注意修正left和maxi重叠的情况，因为最小的元素和left位置的元素交换，如果原来left位置的元素就是最大的，那么它会被换到mini的位置。

时间复杂度： O ( n 2 ) O(n^2) O(n2)，最好和最坏情况都是 O ( n 2 ) O(n^2) O(n2)

到这里 O ( n 2 ) O(n^2) O(n2)的排序我们学了三个：冒泡排序、插入排序、选择排序。

对于接近有序的数组，插入排序和优化后的冒泡排序都有一定的适应性，而选择排序识别不了有序的情况。对于完全无序的数组，选择排序一次选两个比冒泡好一些。

总体而言，插入排序更优一些，顺序有序，局部有序都有一定的适应性。

快速排序

快速排序内容较多，下面都是“硬菜“，也是重点。

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

划分

将序列分成两子序列的方式有三种。

一、Hoare版本

这是Hoare最初写的版本，使用的是相向双指针。

1. 选出一个key，一般是第一个数或最后一个数。
2. 设置双指针L、R
3. 先让R从右往左找比key小的值，然后L从左往右找比key大的值，找到后交换
4. 重复第3步直到L、R相遇
5. 把相遇位置的值与key互换

🤔思考：

双指针一定会相遇吗？

如果选第一个数为key，那么相遇位置的值一定要比key小才能交换，相遇位置的值比key小怎么保证？

答：

双指针一定会相遇，两指针相向而行，并且每次只走一步，相遇就停止循环。

右指针先走可以保证相遇位置的值比key小，因为右指针找到最后一个小于key的值后，左指针走，左指针会因为与右指针相遇而跳出循环，此时这个位置的值必然比key值小。

如果选最后一个数为key，相遇位置的值应该比key大，那么应该让左指针先走。

上图是右指针去遇到左指针，之后，左指针判断与右指针相遇就没有继续走。实际也会有左指针遇右指针的情况，一样是左指针走，判断到与右指针相遇便跳出循环。

我们先写这部分代码：

因为除了第一次划分，后面要划分的序列都是一段一段的，所以参数传入的是一段区间[left, right]，最后不要忘了返回key

int PartSort(int* a, int left, int right){int keyi = left;while (left < right){// 找小while (left < right && a[right] >= a[keyi])--right;// 找大while (left < right && a[left] <= a[keyi])++left;Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;}

二、挖坑法

这是一种更好理解的方法

1. 选出一个key，并把它保存起来，使key位置就形成了一个坑位。我们这里先选第一个位置为key
2. 右指针先从右向左走，遇到比key值小的就把它放到坑位上，于是右指针位置形成一个新的坑位
3. 左指针从左向右走，遇到比key值大的就把它放到那个新的坑位上，于是左指针位置又会形成一个新的坑位
4. 重复2、3两步，直到左右指针相遇，最后把key值放到相遇位置上。

这样坑位其实一直在左右指针之间传递，其中一个挖好最后一个坑之后，另一个指针会因为与它相遇而停止，所以相遇位置必然是个坑位。

与Hoare的版本比起来，挖坑法不用理解为什么最终相遇位置的值比key值小，也不用理解为什么左边作key右指针先走，右边作key左指针先走。一个挖坑一个填，是非常自然的，所以说比较好理解。

代码实现：

int PartSort2(int* a, int left, int right){int key = a[left];// 坑位int pit = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= key){--right;}a[pit] = a[right];pit = right;// 左边走，找大while (left < right && a[left] <= key){++left;}a[pit] = a[left];pit = left;}a[pit] = key;return pit;}

三、前后指针

1. 设置两个指针，perv指向第一个数，cur指向第二个数，选第一个数作为key
2. cur往右找比key小的数，找到后prev++，然后和prev位置的数交换。
3. 重复第2步直到cur走到末尾，然后将key与prev交换

遇到小的就给prev，遇到大的cur走prev不走，这样就能保证cur和prev之间的数是比key大的。

代码实现：

int PartSort3(int* a, int left, int right){int keyi = left;int prev = left, cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && a[++prev] != a[cur])Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);return prev;}

这个方法的好处就是代码容易写，不容易错。

这三种划分的时间复杂度都是$O(n)$，性能差异不大。

整体排序——递归

每划分一次，就有一个key已经放到了正确的位置。这个位置就不需要动了。接下来就是分别划分左子序列和右子序列。像这样层层划分，问题规模越来越小，显然可以用递归分治的方法。

递归三要素：

1. 确定参数和返回值：每一层递归表示对[begin, end]区间的元素排序，所以参数int* a, int begin, int end，返回类型void
2. 确定终止条件：最小子问题就是区间只有一个元素，或者区间不存在。
3. 确定每一层的递归逻辑：先划分，然后分别对左右子序列排序。

void QuickSort(int* a, int begin, int end){if (begin >= end)return;int keyi = PartSort(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}

时间复杂度计算：

最好情况：$O(n\log n)$

每次划分选择的key都正好是这个区间的中位数，这样每一次划分都正好把区间分为两半。

划分的时间复杂度是$O(n)$，而每一层有n个数，每一层的时间复杂度就是$O(n)$，层数为log⁡ 2 n + 1 \log_2n+1 log2​n+1，所以总的时间复杂度为$O(n\log n)$

最坏情况： O ( n 2 ) O(n^2) O(n2)

每次划分选择的key都正好是这个区间的最值，这样就和选择排序差不多了，时间复杂度为 O ( n 2 ) O(n^2) O(n2)

对于无序数组，每次选到最大值或最小值那运气就太背了，可是对于接近有序的数组呢？而且递归层数太深，还很容易出现栈溢出。这么一看，这快排也不行啊，那为什么c、c++库里的排序都是快速排序？

优化

如果不优化，你的快排可能过不了这题👉912. 排序数组 - 力扣（LeetCode） (leetcode-cn.com)

针对选key的优化——三数取中

三数取中，就是从区间第一个数，中间一个数和末尾的一个数中选择中位数作key。

写一个函数传入这段区间，获得三数取中后的值的下标，逻辑和代码如下：

int GetMidIndex(int* a, int left, int right){int mid = left + (right - left) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]) return mid;else if (a[left] > a[right]) return left;else return right;}else // a[left] >= a[mid] {if (a[mid] > a[right]) return mid;else if (a[left] < a[right]) return left;else return right;}}

接下来只要在划分前把选出的值换到第一个数的位置，然后取第一个数为key，剩下的不变。

int PartSort(int* a, int left, int right){int midi = GetMidIndex(a, left, right);Swap(&a[midi], &a[left]);int keyi = left;//...}

这样快排就没有什么大的缺陷了。

小区间优化

通过分析时间复杂度的最好情况可以看出，快排的递归很像一棵满二叉数，层数越深，区间越小，需要递归的次数越多。对于小区间，继续递归调用函数显得不太划算。不如直接用插入排序。

void QuickSort2(int* a, int begin, int end){if (begin >= end)return;// 小区间直接插入排序控制有序if (end - begin + 1 <= 10){InsertSort(a + begin, end - begin + 1);}else{int keyi = PartSort3(a, begin, end);QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi + 1, end);}}

整体排序——迭代

递归虽然代码简单，但是有栈溢出的风险。有些时候可能要改写迭代版本。

我们知道，递归的原理和栈相似。递归版本每次都要传入一个区间的左右两端，我们的迭代版本也可以通过栈来保存区间左右两端。

栈在这里👉[数据结构栈和队列_世真的博客-CSDN博客](https://blog.csdn.net/CegghnnoR/article/details/123791953?spm=1001.2014.3001.5502)

有详细注释的代码如下：

void QuickSort3(int* a, int begin, int end){    //创建并初始化栈，将区间左右端入栈ST st;StackInit(&st);StackPush(&st, begin);StackPush(&st, end);while (!StackEmpty(&st)){ //出栈，先出栈的是右端，后出栈的是左端int right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);int keyi = PartSort3(a, left, right);//划分// 接下来对左右子区间进行划分，划分前要先判断左右区间的元素个数是否大于1，如果小于等于1则不需要划分，也就不需要入栈。if (left < keyi - 1){StackPush(&st, left);StackPush(&st, keyi - 1);}if (keyi + 1 < right){StackPush(&st, keyi + 1);StackPush(&st, right);}}StackDestory(&st);}

其实用队列也是可以的。都是成对的入，成对的出，最终只要能把所以最小子区间都划分到就可以了。

归并排序

归并的思想很简单，也很容易想到。你可能在这道题中已经用过归并👉21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

归并排序就是把已经有序的子序列合并，得到完全有序的序列。要使子序列有序，则需要继续分解，直到不可分解再开始合并。

这显然也是可以分治递归实现。

递归

重新开辟一个数组tmp用来存放合并后的序列，由于开辟tmp数组不能放到递归函数里，所以我们再写一个子函数递归。

递归三要素：

1. 确定参数和返回值：每一层递归表示将数组[begin, end]的元素排序。传入参数int* a, int begin, int end, int* tmp，返回类型void
2. 确定终止条件：区间里只有一个元素或区间不存在
3. 确定每一层的递归逻辑：先求中间下标，然后分解，最后合并。类似二叉树的后序遍历，因为合并是自下而上的。

void _MergeSort(int* a, int begin, int end, int* tmp){if (begin >= end)return;int mid = (begin + end) / 2;// 这里是向下取整，如果分割为[begin, mid-1][mid, end]就不均匀，容易死循环。_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);// 归并[begin, mid][mid+1, end]int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[index++] = a[begin1++];elsetmp[index++] = a[begin2++];}while (begin1 <= end1)tmp[index++] = a[begin1++];while (begin2 <= end2)tmp[index++] = a[begin2++];memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));}void MergeSort(int* a, int n){int* tmp = (int*)malloc(sizeof(int) * n);assert(tmp);_MergeSort(a, 0, n - 1, tmp);free(tmp);}

迭代

如图所示，我们只要控制好子区间的大小和子区间的位置也能实现归并。

但是这不容易控制，不是所有序列的元素个数都是 2 n 2^n 2n，比如6个数的序列，按1个元素大小的区间归并没问题，而2个元素大小的区间只能分成3组，最后一组没有区间和它归并，如果不处理，就会出现越界。

有详细注释的代码如下：

void MergeSortNonR(int* a, int n){int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap < n)// 控制子区间的大小gap{for (int i = 0; i < n; i += 2 * gap)// 控制要归并的两个区间的位置{int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// end1 越界，修正if (end1 >= n)end1 = n - 1;// begin2 越界，说明第二个区间不存在，那么直接给个不存在的区间if (begin2 >= n){begin2 = n;end2 = n - 1;}// begin2 合法， end2越界，修正end2即可if (begin2 < n && end2 >= n)end2 = n - 1;//归并int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[index++] = a[begin1++];elsetmp[index++] = a[begin2++];}while (begin1 <= end1)tmp[index++] = a[begin1++];while (begin2 <= end2)tmp[index++] = a[begin2++];}memcpy(a, tmp, n * sizeof(int));gap *= 2;}free(tmp);}

时间复杂度：$O(n\log n)$

每一层有n个数，排序的时间复杂度为$O(n)$，一共有log⁡ 2 n + 1 \log_2n+1 log2​n+1层，所以时间复杂度为$O(n\log n)$

和快速排序不同的是，它是绝对的二分，不受选key的影响。

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

创建了大小为n的tmp数组，空间复杂度$O(n)$；递归深度为log⁡ 2 n + 1 \log_2n+1 log2​n+1，每一层递归开辟常数个空间，所以递归的空间复杂度为$O(\log n)$，总的空间复杂度为$O(n)$

迭代也要开辟tmp数组，所以空间复杂度也是$O(n)$

---

最终对决：堆排序，希尔排序，快速排序，归并排序四个最强排序放到一起比一比

一千万个数：

一亿个数：

内排序 外排序

内排序是指数据在内存上进行排序；外排序指数据在磁盘上，数据量通常很大。

对于数据量小的内排序，归并排序在空间复杂度上占不到优势。但是对于外排序，只有归并排序能做。

这就涉及到文件操作了，这里就不细讲了。

计数排序

以上都是比较排序，计数排序是非比较排序。计数排序的思想也比较简单，我们在oj题中也可能用到过。

计数排序是通过哈希数组统计数据个数，最后遍历哈希数组输出有序序列。

如要排序的序列为{ 10, 3, 5, 8, 4, 1, 3, 1 }

1. 开辟一个大小为11的哈希数组并初始化为0

2. 遍历序列，以待排元素的值为下标使哈希数组相应位置的值加1。

3. 遍历哈希数组，数组中的值代表该下标输出次数。

哈希数组开的大小取决于待排元素值大小的跨度，对于跨度在500~1000内的序列，只需要开大小为501的数组，然后对每个值加偏移量即可。待排序列中有负数也同理。

缺点：可排序的类型有限，比如浮点型，字符串。对于值特别分散的序列，时间和空间复杂度都较高。

void CountSort(int* a, int n){    // 计算跨度int min = a[0], max = a[0];for (int i = 1; i < n; ++i){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;int* countA = (int*)calloc(range, sizeof(int));assert(countA);// 计数for (int i = 0; i < n; ++i){countA[a[i] - min]++;}// 排序int j = 0;for (int i = 0; i < range; ++i){while (countA[i]--){a[j++] = i + min;}}}

时间复杂度：$O(range+n)$

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

总结

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O ( n 2) O(n^2) O(n2)	$O(n)$	O ( n 2) O(n^2) O(n2)	$O(1)$	稳定
选择排序	O ( n 2) O(n^2) O(n2)	O ( n 2) O(n^2) O(n2)	O ( n 2) O(n^2) O(n2)	$O(1)$	不稳定
插入排序	O ( n 2) O(n^2) O(n2)	$O(n)$	O ( n 2) O(n^2) O(n2)	$O(1)$	稳定
希尔排序	O ( n log ⁡ n ) ∼ O ( n 2) O(n\log n)\sim O(n^2) O(nlogn)∼O(n2)	O ( n 1.3) O(n^{1.3}) O(n1.3)	O ( n 2) O(n^2) O(n2)	$O(1)$	不稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
快速排序	$O(n\log n)$	$O(n\log n)$	O ( n 2) O(n^2) O(n2)	$O(\log n)\sim O(n)$	不稳定

快排，归并，希尔是我们学习排序的重中之重，难度也相对比较大。

读书笔记网