数据结构（9）——排序
文章目录
目录
文章目录
前言
一、排序的概述
1.1排序相关概念
1.2常见的排序算法
二、排序的实现
2.1插入排序
2.2希尔排序
2.3选择排序
2.4堆排序
2.5冒泡排序
2.6快速排序
2.6.1霍尔版本
2.6.2填坑版
2.6.3前后指针版
2.6.4非递归版
2.6.5小区间优化
2.7归并排序
2.7.1非递归一次性拷贝
2.7.2非递归分拷贝
2.8计数排序
三、排序效率比较
总结
前言
排序算法是计算机科学中用于将一组数据按照特定顺序排列的算法。我们在生活中能看到很多利用排序的地方，例如你去查榜单或者去买东西的时候，有一个价格升序类似等等，都利用了排序算法。通过排序算法我们能看到最好的或者最坏的，最贵的或者最便宜的，大大节省了我们筛选的时间。
这里所有的排序都是按照升序来进行的。
一、排序的概述
1.1排序相关概念
排序：所谓排序，就是使一串记录，按照其中的某一个或者某些关键字的大小，递增或者递减排列起来的操作。
稳定性：如果在排列的记录序列中，有多个相同的关键字的记录，如果通过排序，这些记录的相对次序保持不变，例如如果有两个2，那么这两个2的次序是不变的，第一个在第二个的前面，排列完之后也是如此，如果符合这种那么就说明这种排序算法是稳定的，否则成为是不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：针对大规模数据，无法一次性装入内存时使用的排序算法。由于数据存储在外部存储（如磁盘），需要减少磁盘I/O次数以提高效率。根据排序过程的要求不能在内外之间移动数据的排序。
1.2常见的排序算法
常见的排序算法可以分为四类：插入排序，选择排序，交换排序，归并排序，还有一些其他的排序，其中插入排序包括直接插入排序、希尔排序，选择排序包括选择排序、堆排序，交换排序包括冒泡排序、快速排序，归并排序就是归并排序。
二、排序的实现
2.1插入排序
插入排序是一个简单的排序法，其基本的思想就是把待排序的记录按照其关键码值的大小逐个插入到一个已经排好序的有序序列中，知道所有的记录插入完为止，最后得到一个有序序列，生活中经典的例子就是玩扑克牌。
void InsertSort(int* a, int n);//插入排序怎么来说呢，插入排序我感觉其实就是不断找空隙，符合了就把前面小的塞进去，但是这个算法我们如何设计呢，不妨自己想一想。
在实现算法我们首先要想的是单趟排序是如何排序的，最后在单趟的基础上来实现全部的排序。对于单趟排序，肯定是先定一个要移动的数（目标数），同时我们要考虑如何给这个留空，其实也就是让与目标数比较的数往后移动，那么原来这里肯定会留出一个空，只要通过目标数和要比较的数进行比较，如果目标数小于这个数，那么用一个临时变量保存目标数的值，接着把比较的数往后移动，直到找到一个数比目标数小或者下标为-1的时候，就把目标数放在空里面，这就是单趟排序，而全部的排序也就是通过一个循环进行控制。
这里给出代码：
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int tmp = a[i];//拷贝一份int end = i - 1;while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}下面用一个321的例子来进行分析和理解：
当i=1时，tmp=a[ 1 ]=3，end=i-1=0，因为tmp不符合小于a[end]，所以是break，走下一次循环。
当i=2时，tmp=a[ 2 ]=1,end=i-1=1，进入循环，因为tmp<a[end]，所以将a[end]往后移动，a[end+1]也就是a[end]的值。
end--，也就是end=0；
此时tmp还是小于a[end]，所以所以将a[end]往后移动，a[end+1]也就是a[end]的值。
end--，此时end=-1;
因为end=-1，不符合循环条件了，直接break；
执行循环外的语句，将空理插入tmp，也就是a[end+1]=tmp；
当i=3时不符合；此时完成排序。
2.2希尔排序
希尔排序（Shell Sort）是插入排序的一种高效改进版本，也称为缩小增量排序。其核心思想是通过将原始列表分割成多个子序列进行插入排序，逐步缩小子序列的间隔，最终完成整体排序。希尔排序的时间复杂度取决于增量序列的选择，通常介于O(n log²n)到O(n²)之间。
void ShellSort(int* a, int n);//希尔排序
算法步骤
选择增量序列
确定一个递减的增量序列（如gap = n/2, n/4, ..., 1），用于划分子序列。初始增量通常为数组长度的一半，后续逐步减半，这里gap可以取别的。按增量分组并排序
对每个增量值gap，将数组分为gap个子序列，每个子序列包含相距gap的元素。对每个子序列执行插入排序。缩小增量并重复
逐步缩小增量gap，重复上述分组和排序过程，直到增量为1。此时整个数组作为一个序列进行最后的插入排序，确保完全有序。
其实就是插入排序的变形，通过预排序使其接近有序，然后对每一组进行插入排序，让小的数更快一点跑到前面去，让大的数更快一点跑到后面去，之后再进行直接插入排序，插入排序对接近有序的数列很快就排出来，所以这样就可以提升效率，而且效率大大的显著。gap越大跳的越快，就越不接近有序，越小越慢，越接近有序，gap一般是变化的。正常gap取多少都行，一般都取gap/3+1，这里为什么要加1呢，因为最后要保证最后的gap是1。
当gap大于1的时候都是预排序，而当gap为1的时候就是直接插入排序。
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//gap /= 2; gap =gap/3 + 1;for (int j = 0; j < gap; j++){for (int i = j; i < n-gap; i += gap){int tmp = a[i + gap];int end = i;while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tmp;}}}
}其实直接插入排序会了，这个也就会了，就是中间间隔了几个进行直接插入排序。
例如当i=0时，这时候i=0，end=i，tmp是i+gap，进入循环比较a[end]和tmp，这里和直接插入排序一样，就是多了个gap，如果tmp比a[end]小的话，a[end]就移动到a[end+gap]也就是tmp的位置上，end-=gap。下一步end就<0跳出循环，此时a[end+gap]的位置就是原来移动后的空，把tmp放里就是第一趟排序。
当i=1时
当i=2时
通过这样的过程最后就可以实现。当然是否发现还有一种写法，这种写法可以少写一层循环，但是基本的时间复杂度并没有改变。
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap =gap/3 + 1;//除三的话不能保证最后是1for (int i = 0; i < n - gap; i++){int tmp = a[i + gap];int end = i;while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;a[end + gap] = tmp;}}}
}依次往后走跟分组往后走一样的。
2.3选择排序
选择排序是一种简单直观的排序算法。其核心思想是在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾。重复该过程直到所有元素均排序完毕。
无论数据是否有序，选择排序都需要进行n(n-1)/2次比较，因此时间复杂度恒为O(n²)。
这里我们了解的是优化版本的选择排序，基本的选择排序太废物了，所以我们选择双向选择排序。
双向选择就是通过每一轮寻找最大值和最小值，然后最小的与做左侧的数交换，最大的与最右侧交换，当左侧等于右侧的时候，就是排序完了，当然这里还有一个要注意的地方。我们直接看代码进行分析：
当我们这样写的时候是否对？这里给出一组数字，可以自己去验证一下
int a[] = { 0,5,1,6,2,3,7,8,3,9};void SelectSort(int* a, int n)
{int left = 0, right = n-1;while (left <= right){int min = left, max = left;for (int i = left; i <= right; i++){if (a[i] < a[min]) min = i;if (a[i] > a[max]) max = i;} Swap(&a[left], &a[min]);Swap(&a[right], &a[max]);left++;right--;}
}我们跑出来的结果是（第二行）：
这里可以看见，第二个3的位置为什么不对呢，代码逻辑也没问题啊？哈哈这里就是注意的点，细节问题，当我们换到这时候：
此时在[left,right]这个数列中最大的是a[3]=6，最小的是a[5]，接下来就是将最大的与right互换，最小的与left互换。
根据代码的逻辑先是小的换到left的位置：
然后是大的换到right的位置，而原先大的下标是3，此时a[3]并不是6了，而是3，所以交换之后就是：
错误就出现在这里了，我们根据这个错误进行修改一下，也就是判断一下左侧的位置是否等于最大数的下标，如果等于那么在交换完左侧的时候，更新一下现在最大数的下标，也就是原来最小数的下标：
Swap(&a[left], &a[min]);
if (left == max)
{max = min;
}
Swap(&a[right], &a[max]);这样就可以完美的解决问题。
2.4堆排序
堆排序是一种基于二叉堆数据结构的比较排序算法，具有O(n log n)的时间复杂度。它利用了堆的性质（最大堆或最小堆）来实现排序，属于选择排序的一种改进版本。
void HeapSort(int* a, int n);堆排序步骤
构建初始堆
将无序数组转换为一个最大堆。从最后一个非叶子节点开始（索引为n/2 - 1），依次对每个节点执行堆化（heapify）操作。交换堆顶与末尾元素
将堆顶元素（最大值）与数组末尾元素交换，此时末尾元素为最大值。调整剩余堆
对剩余n-1个元素重新堆化，确保堆顶为次大值。重复交换和调整步骤，直到堆大小为1。
一般都是需要有一个向下调整或者向上调整的过程，这里本系列文章在堆里讲了，一般用的向下调整比较多一些：
//向下调整
void AdjustDown(int* a, int parent,int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}这里是通过不断调整孩子和父节点值的大小，比较当前节点与其左右子节点的值，取最大与父节点比较，把大的往上送，最后变成大根堆:
void HeapSort(int* a, int n)
{//向下调整O(n) N-lognfor (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, i, n);}int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, 0, end);--end;}
}之后跟节点就是最大的，利用跟节点和最后的节点交换，每交换一次，最后往前窜一个元素，这样的话最后的都会排好，--end直到循环结束，就可以完成最后的排序。
2.5冒泡排序
冒泡排序我们并不陌生，因为它的思想很简单，而且非常适合教学使用。冒泡排序是一种简单的排序算法，通过重复遍历待排序列表，比较相邻元素并交换顺序错误的元素。每一轮遍历会将当前未排序部分的最大（或最小）元素“冒泡”到正确位置。
算法步骤
- 从列表的第一个元素开始，比较相邻的两个元素。
- 如果前一个元素大于后一个元素（升序排序），则交换它们的位置。
- 对每一对相邻元素重复上述操作，直到列表末尾。
- 重复上述过程，每次遍历时未排序部分减少一个元素（因为最大的元素已到位），直到整个列表排序完成。
void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){bool exchange = false;for (int j = 1; j < n-i; j++){if (a[j - 1] > a[j]){Swap(&a[j - 1], &a[j]);exchange = true;}}if (exchange == false)break;}
}怎么想呢，其实就是小的不断往前走，直到排到前面，就跟水冒泡一样，往上浮动。
2.6快速排序
这里快速排序有好几种写法，我们这里分别对霍尔版本的、挖坑法、前后指针法、以及小区间优化法进行解析。
2.6.1霍尔版本
快排是霍尔首先提出来的，其平均时间复杂度为 O(n log n)，最坏情况下为 O(n²)，递归次数过多就会出现溢出，因为每一次递归都是在栈里开辟空间，数据过多容易爆炸栈，但通过优化（如随机化选择基准）可避免最坏情况。
它的思想其实就是分治，选择一个基准（pivot），将数组分为两部分，使得左边元素均小于等于基准，右边元素均大于基准，对左右子数组递归调用快速排序，由于每次划分后基准已位于正确位置，递归完成后数组自然有序。
单趟排序：
int PartSort1(int* a, int left,int right)
{//左边做key，让右边先走，右边做key，那么就让左边先走int begin = left, end = right;int keyi = left;while (left < right){//右边找小while(left<right && a[keyi] <= a[right]) --right;//左边找大while(left < right && a[keyi] >= a[left]) ++left;Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;return keyi;//或者直接返回left
}分治递归：
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi+1, right);
}我们可以先来分析一下这个单趟排序，为什么可以这么写呢？我们用画图来解释一下，帮助理解：
我们现在有一个这样的数列a，同时根据我们的逻辑设置俩指针，同时设置标志值为最左侧的。
然后左右俩指针开始走，左侧找比key大的，右侧找比key小的，记住这里是right先走，这里有一个技巧记住就行，就是左侧是标志位右侧就先走，反过来右侧是标志位，左侧就先走；这里是找到了这两个位置。
交换一下，接着走，因为left和right没有碰到，循环继续;
这里循环停止，我们可以观察一下当前相遇的位置是什么？是不是我们key标准值如果按排序的位置。
进行交换，返回当前位置的下标，自此函数结束。
接着是分治递归，为什么要用分治递归呢？
通过分治递归，不断的实现之前的步骤，可以看到左侧的2和1排完，交换完之后，QuickSort(a, 0, 0)（子数组长度 1，返回）和 QuickSort(a, 2, 1)（无效范围，返回）。左侧子数组排序完成。
后来的可以看这张图：
在选择标准值的时候也有说法，随机选择可以避免最坏的情况：
//随机选Key
int randi = left + (rand() % (right - left));
Swap(&a[left], &a[randi]);但是如果这组数据接近有序或者有序的情况下，随机选择反而不好，所以这里有一种方法，都适用：
//三数取中
int GetNumMidi(int* a, int left, int right)
{int mid = (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{if (a[mid] > a[right]) return mid;else if (a[left] < a[right]) return left;else return right;}
}int midi = GetNumMidi(a, left, right);
if (midi != left) Swap(&a[midi], &a[left]);就是利用三树取中法，即可实现最佳策略。第一种方法霍尔的了解了之后，后面的几个方法都简单了，都是在它的基础上实现的。
2.6.2填坑版
这一种方法其实就是先把最左侧看做是一个坑，它原本的值用临时变量key来保存，通过不断的填坑，最后找到适合放key的坑。
int PartSort2(int* a, int left, int right)
{int midi = GetNumMidi(a, left, right);if (midi != left) Swap(&a[left], &a[midi]);int key = a[left];int hole = left;//坑的位置int begin = left, end = right;while (left < right){while (left < right && a[right] >= key) --right;a[hole] = a[right];hole = right;while (left < right && a[left] <= key)++left;a[hole] = a[left];}a[hole] = key;return hole;
}2.6.3前后指针版
这一版的步骤其实就两步：
1.cur找到比key小的值,++prev,cur和prev交换位置,++cur
2.cur找到比key大的值，++cur
int PartSort3(int* a, int left, int right)
{int midi = GetNumMidi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;int prev = left, cur = left+1;while (cur <= right){ if (a[cur] < a[keyi] && ++prev!=cur)Swap(&a[prev], &a[cur]);else++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}prev要么紧跟着cur（prev下一个就是cur），要么就是prev跟cur中间间隔着比key大的一段值区间，过程就是把key大的值往右翻，比key小的值翻到左边。
2.6.4非递归版
利用栈来实现，其实就是用栈的特点保持着一个范围然后利用前面的快排的函数来进行排序，非递归快速排序通过栈保存子数组边界，模拟了递归过程。
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);STPop(&st);int keyi = PartSort3(a, begin, end);if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi+1);}if (keyi - 1 > begin){STPush(&st, keyi-1);STPush(&st, begin);}}STDestroy(&st);
}2.6.5小区间优化
我们知道递归对于小的数据量来说没有什么用，反而可能时间更长，所以这里通过一个策略来实现一个优化：
void QuickSort(int* a, int left, int right)
{if (left >= right)return;//小区间优化，小区间直接用插入排序if ((right - left + 1) > 10)//这里可以变化{int keyi = PartSort1(a, left, right);//1,2,3任意QuickSort(a, left, keyi - 1);QuickSort(a, keyi+1, right);}else{InsertSort(a + left, right - left + 1);}
}前面用快排，就剩下最后几个了用插入排序就可以。
2.7归并排序
归并排序是一种基于分治策略的排序算法。通过递归地将数组分解为更小的子数组，直到子数组长度为1，然后合并已排序的子数组，最终得到完全有序的数组。其核心操作是“合并”（Merge），即将两个有序数组合并为一个更大的有序数组。
算法步骤
分解阶段
将当前数组从中间位置分成左右两个子数组，递归地对左右子数组进行分解，直到子数组长度为1。合并阶段
- 创建临时数组存放合并结果。
- 使用双指针分别遍历左右子数组，将较小元素依次放入临时数组。
- 将剩余未遍历的元素直接追加到临时数组末尾。
- 将临时数组复制回原数组对应位置。
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,begin2=mid+1,end1=mid,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++];memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc failed");return;}_MergeSort(a,0,n-1,tmp);free(tmp);
}总的来说就是先把一组数分成一个个的，然后一个一个比较，这样就可以实现几组两个有序数，然后两组比较（4个数），再两组比较（8个数），以此类推，比较完后放到新开辟的数组里，最后一拷贝到原来的数组中就行了。
2.7.1非递归一次性拷贝
void MergeNotRSort1(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc failed");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, begin2 = i + gap;int end1 = i + gap - 1, end2 = i + 2 * gap - 1;int j = i;//这里注意 是有边界判断的if (end1 >= n)//对end1进行判断，若超过n - 1则修正为n - 1，避免第一个子数组越界。{end1 = n - 1;begin2 = n;//end1此时越界，第二组则需要修正成一个不存在的区间end2 = n - 1;}else if (begin2 >= n){begin2 = n;//第二组则需要修正成一个不存在的区间,因为此时begin2已经越界了，代表第二粗不存在end2 = n - 1;}else if (end2 >= n) end2 = n - 1;//对end2进行判断，若超过n - 1则修正为n - 1，避免第二个子数组越界。//printf("[%d][%d] [%d][%d] ", begin1, end1, begin2, end2);//测试打开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++];}//printf("\n");//测试打开gap *= 2;memcpy(a, tmp, sizeof(int) * n);}free(tmp);
}非递归版本通过gap（子数组长度）控制拆分与合并的粒度，具体步骤：
- 初始
gap=1（单个元素本身是有序的）；- 每次将相邻的两个长度为
gap的子数组合并为长度为2*gap的有序子数组；gap翻倍（gap *= 2），重复合并过程，直到gap >= n（整个数组有序）。
其实逻辑大差不差，这里用gap来进行模拟递归的进行，这里最重要的是边界判断的地方，很容易出错和不考虑。
若
end1 >= n：第一个子数组超出范围，修正end1 = n-1，同时将begin2设为n（标记第二个子数组不存在）；若
begin2 >= n：第二个子数组不存在，直接标记begin2 = n；若
end2 >= n：第二个子数组结束索引越界，修正为end2 = n-1。
2.7.2非递归分拷贝
void MergeNotRSort2(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc failed");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, begin2 = i + gap;int end1 = i + gap - 1, end2 = i + 2 * gap - 1;int j = i;//这里注意 是有边界判断的if (end1 >= n || begin2>=n)//对end1和begin进行判断，若超过则直接，归并一部分拷贝一部分{break;}if (end2 >= n) end2 = n - 1;//对end2进行判断，若超过n - 1则修正为n - 1，避免第二个子数组越界。//printf("[%d][%d] [%d][%d] ", begin1, end1, begin2, end2);//测试打开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++];memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));}//printf("\n");//测试打开gap *= 2;}free(tmp);
}这段代码实现了另一种非递归归并排序，核心思路与MergeNotRSort1一致（通过gap控制子数组合并粒度），但在边界处理和结果复制时机上有明显差异。
与MergeNotRSort1相同，该函数通过迭代扩大gap（子数组长度），将相邻的两个有序子数组合并为更大的有序子数组，直到整个数组有序。主要差异体现在：
- 边界处理更简洁：当子数组越界时直接
break跳过，而非调整索引；- 结果复制更及时：每合并完一组子数组后，立即将结果从
tmp复制回原数组a的对应位置，而非整轮gap结束后统一复制。
边界控制：
当
end1 >= n（第一个子数组越界）或begin2 >= n（第二个子数组不存在）时，直接break，不处理当前i对应的子数组；仅当
end2 >= n时，修正end2为n-1，避免第二个子数组越界。
合并完成后，立即通过memcpy(a+i, tmp+i, sizeof(int)*(end2-i+1))将tmp中当前合并的部分（从i到end2）复制回原数组a，而非等待整轮gap结束后统一复制。
2.8计数排序
计数排序（Counting Sort）是一种非基于比较的线性时间排序算法，适用于数据范围较小的整数排序。其核心思想是通过统计每个元素出现的次数，直接确定元素在输出数组中的位置。是一个非基于比较的排序算法，计数排序其实类似键值映射（Map）。
算法步骤
统计元素频率
遍历输入数组，统计每个元素出现的次数，存入一个计数数组。计数数组的索引代表元素值，值为该元素出现的次数。
例如，输入数组[4, 2, 2, 8, 3, 3, 1]，计数数组为[0, 1, 2, 2, 1, 0, 0, 0, 1]（索引 0~8）。计算累积频率
对计数数组进行累加操作，使得每个位置的值表示小于等于当前索引值的元素总数。
上述计数数组累加后变为[0, 1, 3, 5, 6, 6, 6, 6, 7]。生成排序结果
逆序遍历输入数组，根据累积计数数组确定当前元素在输出数组中的位置，每放置一个元素后，将对应的累积计数值减 1。
例如，逆序遍历到8时，根据count[8] = 7，将8放入输出数组索引6（即第 7 个位置），然后count[8]减为6。
void CountSort(int* a, int n)
{int min = a[0];int max = a[0];for (int i = 0; i < n; i++){if (a[i] < min) min = a[i];if (a[i] > max) max = a[i];}int tmpn = max - min+1;int* tmp = (int*)malloc(sizeof(int) * tmpn);if (tmp == NULL){perror("malloc failed!");return;}for (int i = 0; i < tmpn; i++){tmp[i] = 0;}for (int j = 0; j < n; j++){tmp[a[j] - min] += 1;}int ai = 0;for (int k = 0; k < tmpn; k++){if (tmp[k] == 0) continue;else{while (tmp[k]--){a[ai++] = k+min;}}}free(tmp);
}计数排序适合范围集中，且范围不大的整数数组排序，不适合范围分散或者非整形的排序，这里用的相对位置，如果是绝对位置那么如果里面有负数的话就会出现越界，相对位置则不会出现。
计数排序 O(N+range) range与N差不多量级的时候都还行，空间复杂度O(range)。
三、排序效率比较
总结
本文系统介绍了多种经典排序算法及其实现。主要内容包括：1. 基础排序算法：插入排序(O(n²))、希尔排序(O(n^(1.3-2)))、选择排序(O(n²))、冒泡排序(O(n²))；2. 高效排序算法：快速排序(O(nlogn))及其多种变体、堆排序(O(nlogn))、归并排序(O(nlogn))的递归与非递归实现；3. 特殊排序：计数排序(O(n+k))等非比较排序；4. 优化策略：如三数取中法、小区间优化、边界处理等技巧。文章通过代码示例和图示详细解析了每种算法的核心思想、实现步骤和性能特点，为理解和应用排序算法提供了全面参考。