数据结构之各类排序算法代码及其详解

1. 排序的概念

排序是一种常见的算法概念，用于将一组数据按照特定的顺序进行排列。排序算法的目的是将一组数据按照递增或递减的顺序重新排列。常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。排序算法的选择通常取决于数据规模、数据分布和性能需求等因素。排序算法在计算机科学中具有非常重要的地位，被广泛应用于各种领域和问题的解决中。

1.1 稳定性的概念

在排序里面有一个非常重要的概念，那就是稳定性。

简单来说就是排序结束后，相同的数之间的相对位置关系不会发生改变。

比如，如果有一个包含学生信息的列表，需要按照学生的分数进行排序，但是分数相同的学生可能会有不同的其他信息（比如姓名、年龄等），如果排序算法是稳定的，那么相同分数的学生在排序后仍然保持着原本的顺序，这对于保持其他信息的相对顺序是非常有用的。

2. 常见的排序算法

以上这张图里面的就是我们接下来要实现的一些排序法。同时他们又因为不同的排序方法分为不同的类别比如说常见的插入排序（直接插入排序，希尔排序），选择排序（选择排序，堆排序）和交换排序（快速排序，冒泡排序）等等。

3. 插入排序

插入排序是一种简单直观的排序算法，其基本思想是将一个数据插入到已经排好序的数据序列中，从而逐步构建有序序列。

3.1直接插入排序

void InsertSort(int* a, int n)
{for (int i=1;i<n;++i){int end = i-1;int tmp = a[i];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}a[end + 1] = tmp;}}
}

函数接受两个参数，一个是整数指针 a ，表示要排序的数组，另一个是整数 n ，表示数组的长度。通过一个 for 循环从数组的第二个元素开始（索引为 1），依次将每个元素插入到已排序的部分。在每次循环中， end 表示当前要比较的位置，初始值为当前元素的前一个位置，还定义了一个变量 tmp 保存当前要插入的元素值。然后通过一个 while 循环，只要 end 大于等于 0 ，并且当前要插入的元素 tmp 小于 a[end] ，就将 a[end] 向后移动一位（a[end + 1] = a[end]），同时 end 向前移动一位（end--）。当找到合适的位置（tmp >= a[end]）时，就将 tmp 插入到该位置后面（a[end + 1] = tmp）。（类似于抓了一把扑克牌，然后从左往右排序）

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1) ，它是一种稳定的排序算法

4. 稳定性：稳定

3.2 希尔排序

希尔排序是一种插入排序的改进版本，也称为缩小增量排序。它是由美国计算机科学家希尔（Donald Shell）于1959年提出的。希尔排序的基本思想是将待排序的元素分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的长度，最终整个序列变成有序。

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

首先，通过一个 while 循环，只要 gap 大于 1 ，就将 gap 不断除以 2 来调整步长。对于每次确定的 gap 值，通过一个 for 循环，从索引 0 开始，对每隔 gap 个位置的元素进行插入排序的操作。在每次的插入排序过程中， end 为当前要比较的位置，初始值为 i ， tmp 保存当前要插入的元素值（即 a[i + gap] ）。通过一个 while 循环，只要 end 大于等于 0 ，并且当前要插入的元素 tmp 小于 a[end] ，就将 a[end] 向后移动 gap 个位置（a[end + gap] = a[end]），同时 end 向前移动 gap 个位置（end -= gap）。当找到合适的位置（tmp >= a[end]）时，就将 tmp 插入到该位置后面（a[end + gap] = tmp）。

有点类似于这张图，然后通过减小gap来达到渐渐有序。这样做有一个好处就是大的数可以快速的跳到后面，不用慢慢的一个一个向后调整 ，希尔排序就是通过这样的方式来实现优化。

PS:我们可以把直接插入排序理解为gap恒定为1的希尔排序。

4. 选择排序

4.1 选择排序

​
void SelectSort(int* a, int n)
{int left = 0;int right = n - 1;while (left < right){int mymin = left;int mymax = left;for (int i = left + 1;i < n; ++i){if (a[i] <a[mymin]){mymin = i;}if (a[i] > a[mymax]){mymax = i;}}Swap(&a[left], &a[mymin]);if (left == mymax){mymax = mymin;}Swap(&a[right], &a[mymax]);left++;right--;}
}​

首先，定义了两个变量 left 和 right ，分别表示数组的起始位置和结束位置。在 while 循环中，只要 left 小于 right ，就执行以下操作:在每次循环中，先假设 left 位置的元素是最小的（mymin = left）和最大的（mymax = left）。然后通过一个 for 循环，从 left + 1 位置开始遍历数组，找到当前最小元素的位置 mymin 和最大元素的位置 mymax 。接下来，交换 left 位置和 mymin 位置的元素。如果此时 left 等于之前的 mymax ，则更新 mymax 的值为 mymin 。再交换 right 位置和 mymax 位置的元素。最后，将 left 向右移动一位，right 向左移动一位。

PS：简单来说，我们可以想象现在我们手上有一把扑克牌，然后我们一眼扫过去，把最大和最小的依次放入左边和右边，这就是这个选择排序的逻辑。

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1)

4. 稳定性：不稳定

4.2 堆排序

void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >=0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);end--;}
}

首先，通过一个 for 循环从数组中间位置开始向前（i = (n - 1 - 1) / 2），对每个非叶子节点调用 AdjustDown 函数进行调整，构建一个大根堆。然后，将堆顶元素（即最大元素）与最后一个未排序的元素交换位置，并对堆顶元素重新调用 AdjustDown 函数进行调整，使剩余元素仍保持大根堆的性质。这个过程一直持续到整个数组都被排序，通过 end 从数组末尾逐渐向前移动来控制。

PS:在i=(n-1-1)/2里面，第一个 -1是为了获取最后一个元素的索引，第二个-1是因为根据父节点公式 (子节点索引-1)/2，计算该元素的父节点索引，所以这里才会-1-1，同时这是为了区分（即更好的理解这段代码）。

PS:这里面的这个while我们可以理解为堆本身的一种缺陷，因为他不像AVL树，红黑树那样（即大的往右边，小的往左边），所以需要用到这里面的while。

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度： O(N*logN)

3. 空间复杂度： O(1)

4. 稳定性：不稳定

5. 交换排序

5.1 冒泡排序

这个冒泡排序一般来说是我们学习的第一个排序算法。他非常的容易理解，同时他的代码也容易实现。简单来说这个代码写起来的逻辑就像是水里面的泡泡一样，小的上浮，大的下沉。

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

外层的 for 循环控制排序的轮数，一共进行 n 轮。在每一轮中，初始化一个标志变量 ex 为 1，表示假定这一轮不需要交换元素，数组已经有序。内层的 for 循环用于比较相邻的元素，如果前一个元素大于后一个元素，就交换它们的位置，并将 ex 置为 0，表示这一轮进行了交换操作。每一轮结束后，如果 ex 仍然为 1，说明在这一轮中没有进行交换，即数组已经完全有序，此时通过 break 语句提前结束排序。

PS:ex是我加的一种优化，并不是必须的。

冒泡排序的时间复杂度是O(n^2)，相对较低效，特别是在对大量数据进行排序时。然而，冒泡排序是一种容易实现和理解的算法，适用于小规模数据的排序。

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1)

4. 稳定性：稳定

5.2 快速排序

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

三数取中法选key

int ChooseMid(int* a, int left, int right)
{int mid = (left + right) / 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{if (a[left] < a[right])return left;else if(a[mid]>a[right]){return mid;}else{return right;}}
}

首先，计算区间的中间位置 mid 。然后通过比较区间左右端点和中间点的值，来确定返回哪个位置的索引作为中间值的索引。如果 a[left]<a[mid] ，再判断 a[mid] 和 a[right] 的大小。如果 a[mid]<a[right]，返回 mid ；如果 a[left]>a[right]，返回left；否则返回right。如果 a[left]>=a[mid]，同样再判断 a[left] 和 a[right] 的大小。如果 a[left]<a[right] ，返回 left ；如果 a[mid]>a[right]，返回mid；否则返回right。

PS:这个函数是为了取出一个不是最大或者最小的值，因为max或者min的值会影响快速排序的效率。

5.2.1 Hoare版快速排序

void QuickSort1(int* a, int left, int right)
{if (left >= right)return;int begin = left;int end = right;int keyi = ChooseMid(a, left, right);Swap(&a[keyi], &a[left]);while (left < right){while(a[right] >= a[begin]&&left<right){--right;}while(a[left] <= a[begin]&&left<right){++left;}Swap(&a[left],& a[right]);}Swap(&a[begin],& a[left]);keyi = left;
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi + 1, end);
}

首先，检查区间的起始位置 left 是否大于等于结束位置 right ，如果是则直接返回，因为这种情况不需要排序。然后，初始化起始和结束位置的变量 begin 和 end ，通过 ChooseMid 函数选择一个 keyi ，并将keyI与起始位置的元素交换。接下来，通过两个 while 循环，从右向左找到小于keyi，从左向右找到大于keyi，然后交换它们的位置，直到左右指针相遇。相遇后，将keyi与当前指针位置的元素交换，确定keyi 的最终位置 。最后，对keyi左右两侧的子区间分别递归调用 QuickSort1 函数进行排序。

PS:我个人认为Hoare版本的快速排序挺简单的也好理解,个人比较推荐掌握这种。

我们把这个快速排序递归部分具体出来就是这个样子，通过这种方式来把它变的有序。

5.1.2 挖坑法版快速排序

void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int begin = left;int end = right;int keyi = ChooseMid(a, left, right);Swap(&a[keyi], &a[left]);int hole = begin;int key = a[hole];while (left < right){while (a[right] >= key&& left < right){--right;}a[hole] = a[right];hole = right;while (a[left] <= key && left < right){++left;}a[hole] = a[left];hole = left;}//Swap(&stay, &a[left]);//keyi = left;a[hole] = key;keyi = hole;QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi + 1, end);
}

首先，如果区间的起始位置 left 大于等于结束位置 right ，则直接返回，因为这种情况不需要排序。然后，初始化起始和结束位置的变量 begin 和 end ，通过 ChooseMid 函数选择一个基准元素的索引 keyi ，并将基准元素与起始位置的元素交换。接着，定义一个变量 hole 并初始化为起始位置，同时记录基准元素的值 key 。通过两个 while 循环，从右向左找到小于key的值，将其放到 hole 位置，更新 hole 为当前的右指针位置；从左向右找到大于基准元素的值，将其放到 hole 位置，更新 hole 为当前的左指针位置（简单来说就是先右边找比key小的，找到后给他放到key的位置，然后key变到右边，接着左边找比key小的，再换给已经到右边的key，最后循环往复）。循环结束后，将key放到 hole 位置，确定基准元素的最终位置 keyi 。最后，对key左右两侧的子区间分别递归调用 QuickSort2 函数进行排序。

5.1.3 前后指针版快速排序

void QuickSort3(int* a, int left, int right)
{if (left >= right)return;int begin = left;int end = right;int keyi = ChooseMid(a, left, right);//int keyi = left;Swap(&a[keyi], &a[left]);int first = left;int second = left + 1;while (second <= right){if (a[second] < a[keyi]&&++first!=second){//++first;Swap(&a[first], &a[second]);}++second;}Swap(&a[keyi], &a[first]);keyi = first;QuickSort3(a, begin, keyi - 1);QuickSort3(a, keyi + 1, end);
}

如果左边的位置大于等于右边，就不排序直接返回。先记录下开始和结束的位置，选一个基准元素并和左边的元素交换。然后设两个指针，一个从左边开始，另一个从左边下一个位置开始。在一个循环里，如果第二个指针（second）指向的元素小于基准元素，并且两个指针位置不同(因为同一位置交换没有意义），就交换它们指向的元素，两个指针再移动。如果second指向的元素比keyi大，那就不走if语句，直接加加second。循环完后，把基准元素和第一个指针指向的元素交换，确定基准位置。最后，对keyi两边的子区间再分别进行同样的排序操作。

5.3 快速排序（非递归版）

我们之所以要学习非递归版本的是因为递归版本的快速排序在面对大数量级的时候容易造成栈溢出，从而导致错误，所以我们要学习非递归版本的快速排序。

int PartSort3(int* a, int left, int right)
{int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur], &a[prev]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);int keyi = PartSort3(a, begin, end);if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

PartSort3 函数前后指针版快速排序，只不过去掉了递归。

QuickSortNonR 函数实现非递归的快速排序。首先创建一个栈 st 并初始化，将排序区间的左右边界压入栈。在循环中，取出栈顶的两个值作为当前排序区间的起止位置，调用 PartSort3 进行部分排序得到基准索引。若基准右边区间可继续划分，将右边新的区间边界压入栈；若基准左边区间可继续划分，将左边新的区间边界压入栈。循环结束后销毁栈。

PS:其实本质这就是通过栈来进行一种对递归的模拟实现。

6. 归并排序

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);int begin1 = begin; int end1 = mid;int begin2 = mid + 1;int end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}for (int i = 0; i < end-begin+1; ++i){a[i+begin] = tmp[i+begin];}
}void MergeSort(int*a,int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

_MergeSort 函数用于对数组的指定区间进行归并排序的核心操作。如果起始位置大于等于结束位置，函数直接返回。通过计算中间位置，对左右子区间分别递归调用 _MergeSort 进行排序。然后，通过循环比较两个子区间的元素，将较小的元素依次放入临时数组 tmp 中。当其中一个子区间遍历完后，将另一个子区间剩余的元素放入 tmp 。最后，将 tmp 中的元素复制回原数组。MergeSort 函数用于对外提供归并排序的接口。首先分配一个与原数组大小相同的临时空间 tmp ，如果分配失败则报错并返回。然后调用 _MergeSort 对整个数组进行排序，排序完成后释放临时空间。

PS：其实他的本质就是分成一块一块然后进行小区间排序，然后小块合并再进行小区间排序，最后达到有序。

6.1 归并排序非递归版

void _MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;int j = i;if (end1 > n || begin2 > n){break;}if (end2 > n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}int k = begin1;memcpy(a + i, tmp + i, sizeof(int)*(end2 - i + 1));}gap *= 2;}free(tmp);
}void MergeSort(int*a,int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}MergeSortNonR(a,n);free(tmp);
}

首先分配一个与原数组大小相同的临时数组tmp用于辅助排序。然后通过一个循环不断增加归并的子数组大小gap，每次循环对数组进行分组归并。对于每个分组，确定两个子数组的起始和结束位置，然后比较并合并两个子数组到tmp中，最后将tmp中的排序结果复制回原数组。当gap小于数组长度n时，不断重复这个过程。MergeSort函数主要用于分配临时空间，调用_MergeSortNonR进行排序，最后释放临时空间。

PS:非递归版的归并排序在代码实现的部分要格外注意边界处理。

7.  计数排序

void CountSort(int* a, int n)
{int max = a[0];int min = a[0];for (int i = 0; i < n; ++i){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}int range = max - min + 1;int* cmp = (int*)malloc(sizeof(int*) * range);if (cmp == NULL){perror("malloc fail");return;}memset(cmp, 0, sizeof(int) * range);for (int i = 0; i < n; ++i){cmp[a[i] - min]++;}int j = 0;for (int i = 0; i < n; ++i){while (cmp[i]--){a[j++] = i + min;}}free(cmp);
}

首先，通过遍历数组找到数组中的最大值 max 和最小值 min 。然后计算数据的范围 range ，并分配一个与范围大小相同的辅助数组 cmp 。接着，再次遍历原数组，对每个元素在辅助数组中对应的位置进行计数。之后，通过另一个循环，根据辅助数组中的计数，将元素按顺序放回原数组。最后，释放辅助数组的内存。

PS：简单来说，他的原理就类似于这种（画的有点丑陋），通过记录出现的数的次数，最后把他们依次放入原始数组里面。从这张图我们也可以看出计数排序在原数组数字重复多并且数字间隔比较密的时候（max-min+1），计数排序会格外的好用。

6. 总结

在实际工程中，没有绝对的最优算法。当处理百万级数据时，快速排序往往表现优异；面对海量数据时，归并排序的稳定性优势凸显；在资源受限的嵌入式系统中，堆排序可能是更安全的选择。理解算法本质，分析数据特征，结合具体场景，才能做出最合适的决策。愿这些排序算法成为你解决实际问题的利剑，在编程之路上助你披荆斩棘！
 
 建议读者在实践中尝试用不同算法处理同一数据集，直观感受性能差异。当面对特殊业务场景时，也可以考虑将多种算法组合使用，或者基于这些经典思想进行改良创新。排序的世界永远充满惊喜，期待你在实践中发现更多精妙之处！