文章目录
- 直接插入排序
- 代码实现
- 复杂度的计算
- 希尔排序
- 希尔排序的预排序
- 代码实现
- 选择排序
- 代码实现
- 堆排序
- 冒泡排序
- 代码实现
- 快速排序
- 递归实现
- Hoare版本
- 代码实现
- 递归图解
- 挖坑法
- 代码实现
- 递归图解
- 前后指针法
- 代码实现
- 递归图解
- 非递归实现
- Hoare版本
- 挖坑法
- 前后指针法
- 非递归快排代码实现
- 图解代码
- 快速排序的两个优化
- 1.三数取中
- 代码实现
- 2.小区间的优化
- 代码实现
- 归并排序
- 递归实现
- 递归图解
- 区间划分要注意（死递归）
- 非递归实现
- 代码实现
- 递归图解
- 计数排序
- 绝对映射和相对映射
- 代码实现
- 八大排序性能测试
💢 注：以下排序都是以排升序为例。
直接插入排序
直接插入排序的主要思路就是：
1.首先默认第一个元素是有序的。
2.然后将其下一个元素作为待排序的元素，插入到前面有序序列的相应位置。至于插入的过程，如果遇到比待排序大的元素，则这个元素后移，直到遇到比其小的元素，然后将待插入元素放入其前一个位置。
代码实现
void Insertsort(int *a, int sz)
{
int i = 0;
for (i = 0; i < sz-1; i++)
{
//用j来记录i的位置，这样可以省得到时候有些情况i从头或接近从头开始走
int j = i;
int temp = a[i + 1];
while (i >= 0)
{
if (temp<a[i])
{
a[i + 1] = a[i];
i--;
}
else
{
break;
}
}
a[i + 1] = temp;
i = j;
}
}
注：绝大部分的直接插入排序算法其实是没有在代码中记录i的位置的，其实记录了i的位置可以提高执行效率，因为这样可以省得到时候有些情况i从头或接近从头开始走。
复杂度的计算
在代码中，创建的临时变量个数是常数个，所以空间复杂度为O（1）。
希尔排序
在上面的直接插入排序中我们会发现：
1.普通插入排序的时间复杂度最坏情况下为O(N2)，此时待排序列为逆序，或者说接近逆序。
2.普通插入排序的时间复杂度最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
于是希尔这个科学家就想：若是能先将待排序列进行一次预排序，使待排序列接近有序（接近我们想要的顺序），然后再对该序列进行一次直接插入排序。因为此时直接插入排序的时间复杂度为O(N)，那么只要控制预排序阶段的时间复杂度不超过O(N^2)，那么整体的时间复杂度就比直接插入排序的时间复杂度低了。
希尔排序的预排序
希尔排序，又称缩小增量法。那么如何缩小增量了？
1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作 （一般情况下我们取得第一增量大小是序列长度的一半）
2.当增量的大小减到1时，其实此时预排序已经完成了，这时已经达到我们一开始要的目的：让序列接近我们要的顺序。
3.最后对整个序列进行直接插入排序即可。
举个例子来看下。
在这个序列中，gap=3时其实就是对原序列进行了预排序。使其接近我们要的升序，方便之后的直接排序。
注：希尔排序和直接插入排序是稳定排序：我们可以发现，在希尔排序的过程中，序列中两个9的相对位置没有发生改变，具有这样特性的排序，我们称之为稳定排序。
代码实现
void Shellsort(int *a, int sz)
{
int i = 0;
int gap = sz / 2;
while (gap >= 1)
{
for (i = 0; i < sz-gap; i++)
{
int j = i;
int end = i;
int temp = a[i + gap]; //这儿一定要记录下那个位置的数据，而不是写成temp=i+gap记录下标的形式，因为之后那个记录的下标的位置的数据可能被前面的数据前移占据了。
while (end >= 0)
{
if (temp < a[end])
{
//a[temp] = a[end]; 因为下面要用到a[end+gap]=a[temp],所以这儿不能写成a[temp]
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp;
i = j;
}
gap = gap / 2;
}
}
选取这种增量方法的时间复杂度：O（nlogn），具体这个我是这么理解的，首先预排序阶段，你每次都将gap除以2，其实也就是高度次：logn，预处理中的交换次数可以看成常量，然后预处理完，这时已经接近最好情况的直接排序了，时间复杂度为O（n），所以最终的时间复杂度为O（nlogn），具体的证明过程等后序会补充更新。
空间复杂度：这里我们只定义了常数个常量，故空间复杂度为O（1）。
选择排序
选择排序
1.首先从整个数组中选出最小值，记录下最小值位置的下标与第一个位置交换，这样相当于最小值就到了头上。
2.此时将除最小值之后的元素再来选出次小的数，与第二个位置交换，之后迭代这个过程，最终就可以排成升序。
代码实现
void chosesort(int *a, int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
int min = i;
for (int j = i; j < sz; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
swap(&a[i], &a[min]);
}
}
时间复杂度：最坏的情况下是一个等差数列为O（n^2)
空间复杂度：创建了常数个变量，为O（1）
实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
void chosesort(int* a, int sz)
{
int start = 0;
int end = sz - 1;
while (start < end)
{
int min = start;
int max = start;
for (int j=start; j <= end; j++)
{
if (a[j] < a[min])
{
min = j;
}
if (a[j]>a[max])
{
max = j;
}
}
swap(&a[start], &a[min]);
//万一最大的值在最左边，这样max的位置的值就被最小值覆盖了，如果没有这个处理，会导致下面交换时出错。
if (max == start)
{
max = min;
}
swap(&a[end], &a[max]);
start++;
end--;
}
}
注：这里要小心一种极端情况：万一最大的值在最左边，这样max的位置的值就被最小值覆盖了，如果没有if这个处理，会导致下面交换时出错。
堆排序
博主之前专门写了一篇关于堆排序以及堆的文章，由于是最近不久写的，这里就不再赘述了，💢堆排序以及堆相关的知识
冒泡排序
相信冒泡排序是很多小伙伴第一个知道的排序算法。
其实它的思想正和他的取名一样，它就是每趟排序冒出一个最大（最小）值。那么它是如何冒的了？很简单，相邻两个元素比较，前一个比后一个大，则交换。
代码实现
void Bubblesort(int *a, int sz)
{
int i = 0;
int flag = 0; //记录原序列是否有序
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - i - 1; j++)
{
if (a[j]>a[j + 1])
{
swap(&a[j], &a[j + 1]);
flag = 1; //交换过了，说明原序列无序
}
}
if (flag == 0) //原序列一次交换都没有发生，说明原序列本来就有序，无需在继续进行
{
break;
}
}
}
注：这里可以自己定义一个标识符flag来记录原序列是否发生过交换，如果没有发生过，则说明原序列本来就有序，无需再进行之后的趟数。
快速排序
快速排序是公认的排序之王，
其基本思想为： 任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。
对于如何按照基准值将待排序列分为两子序列，常见的方式有：
1、Hoare版本
2、挖坑法
3、前后指针法
这三种方法并没有明显的优缺点，时间复杂度都为O（nlogn）
递归实现
Hoare版本
Hoare版本单趟排序的基本步骤如下：
1.选一个key作为比较值，一般是最左边或者最右边。
2.定义一个left和right，如果key选取的是左边就让右边的先走，直到right找到一个比key小的值，然后让left从左边走，直到让它找到一个比key大的值，然后交换两者，之后继续让right先走，left后走，直到left与right相遇停下来。
3.最终再让相遇处与key处位置对应的值做交换，这样就可以达到我们想要的效果了。
4.之后递归它的左序列和右序列，最终排成升序。
注意：可能有小伙伴会问了，如果你最后key与meet（相遇处）处对应的值交换，万一meet比key处的值大，那不就达不到我们要的效果了吗？其实这里并不会出现这个问题，因为这种方法让right先走了，所以不会出现这种问题，大家可以多去尝试几组数据看看，是不是会有这个特点
代码实现
//快速排序（Hoare版本）
void QuickSort1(int* a, int left, int right)
{
if (left >= right)//当只有一个数据或是序列不存在时，不需要进行操作
return;
int begin = left;//L
int end = right;//R
int key = left;//key的下标
while (left < right)
{
//right先走，找小
while (left < right&&a[right] >= a[key])
{
right--;
}
//left后走，找大
while (left < right&&a[left] <= a[key])
{
left++;
}
if (left < right)
{
swap(&a[left], &a[right]);
}
}
int meet = left;//L和R的相遇点
swap(&a[key], &a[meet]);//交换key和相遇点的值
QuickSort1(a, begin, meet - 1);//key的左序列进行此操作
QuickSort1(a, meet + 1, end);//key的右序列进行此操作
}
注意：
1.这里要保存一下left和right的值，因为你在代码过程中left和right的值会发生变化，如果你不保存，在递归时传参直接传left和right的话，那时就不是我们想要的值了。
2.这里你key要记录left的下标，而不是记录a[left]这个数值，因为如果这样的话，你在下面交换key位置和meet位置对应的值时就会出问题，你只有记录下标，才可以做到对应位置值得交换。
递归图解
挖坑法
挖坑法的单趟排序的基本步骤如下：
1.先选取一个初始坑位，并让此位置的值记作key（一般选取最左边或者最右边）
2.同样这里也是right先走，直到找到一个比key小的值，然后将这个值填入坑位，并让这个位置再来做坑，之后移动left，直到找到一个比key大的值，再将这个位置的值填入坑位，然后让这个位置来做坑。这样一直循环下去，直到left==right。
3.当left与right相遇时，此时将key的值赋值给相遇位置即可，这时就达到我们想要的效果：key左边的值都小于key，key右边的值都大于key。
4.然后仍然是递归其左序列和右序列，最终整个序列升序。
代码实现
//快速排序 （填坑法）
void QuickSort2(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left; //保存left的值，为了下面的递归传递
int end = right;//保存right的值，为了下面的递归传递
/*int key = left;*/ //这个地方要记住那个数，因为记下标
//的话，没用，left已经和其他位置交换过了，那么就不是我们想要的值了
int key = a[left];
int hole = left;
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];
hole = left;
}
int meet = left;
a[meet] = key;
QuickSort2(a, begin, meet- 1);
QuickSort2(a, meet+ 1, end);
}
注意：
1.这里同样也要保存下left和right的值，原因同Hoare法的一样，因为代码过程中其值发生改变会影响递归传递。
2.这里与Hoare法有所不同，这里key要记录a[left],而不是下标，因为你在之后的填坑过程中，left下标处的值可能被交换了，不是我们最初想要的值，所以要记录下来最初的那个值，即a[left]。
递归图解
前后指针法
前后指针法的单趟排序的基本步骤如下：
1.选出一个key作为比较值，一般是最左或者最右边。让prev指向left，cur指向left+1。
2.之后比较cur位置的值和key的值，首先要保证cur位置的值要小于key，而且++prev！=cur,这时交换prev和cur位置对应的值，不管满不满足这两个条件，cur都要++，这样才能迭代起来。
3.直到cur越界，此时prev为key应该在的位置，此时交换prev位置的值和key，就可以达到我们想要的效果。
4.仍然是递归其左序列和右序列，最终整个序列有序。
代码实现
//快速排序（前后指针法）
void QuickSort3(int *a, int left, int right)
{
if (left >= right)
{
return;
}
//这里没有必要记录left和right的值，因为整个代码中这两个量一开始是什么值，最终仍然是那个值
//int begin= left;
//int end = right;
int pre = left;
int cur = left + 1;
int key = left; //这里要记住小标，不然值是交换不过去的，一般快排中用到交换的换，都是记录下标
while (cur <= right)
{
if (a[cur] < a[key] && ++pre != cur)
{
swap(&a[pre], &a[cur]);
}
cur++;
}
int meet = pre;
swap(&a[meet], &a[key]);
QuickSort3(a, left, meet - 1);
QuickSort3(a, meet + 1, right);
}
注意：
1.这里没有必要再和上面一样保存left和right的值了，因为整个过程中left和right的值并没有变化。
2.这里和Hoare法那儿一样，key要记录left这个下标，而不是a[left]这个值，因为你之后要交换meet和key位置处对应的值，而你一开始如果记录a[left]是做不到这一点的。(一般而言如果有swap交换这个需求的话，都要记录下标，而不是下标处对应的值）
3.这里要注意a[cur] < a[key] && ++pre != cur这两个条件写的先后顺序，一定要把比较大小写在前面，如果你的a[cur]都不满足比a[key]小，那么就不需要++prev这一步的判断了。
递归图解
非递归实现
当我们需要将一个用递归实现的算法改为非递归时，一般需要借用一个数据结构，那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本，其实主体思想一致，只是调用的单趟排序的算法不同而已。
Hoare版本
//快速排序（前后指针法）
void QuickSort3(int *a, int left, int right)
{
if (left >= right)
{
return;
}
//这里没有必要记录left和right的值，因为整个代码中这两个量一开始是什么值，最终仍然是那个值
//int begin= left;
//int end = right;
int pre = left;
int cur = left + 1;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++pre != cur)
{
swap(&a[pre], &a[cur]);
}
cur++;
}
int meet = pre;
swap(&a[meet], &a[key]);
QuickSort3(a, left, meet - 1);
QuickSort3(a, meet + 1, right);
}
挖坑法
//挖坑法（单趟排序）
int QuickSort2(int* a, int left, int right)
{
int key = a[left];//在最左边形成一个坑位
while (left < right)
{
//right向左，找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右，找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇点
a[meeti] = key;//将key抛入坑位
return meeti;//返回key的当前位置
}
前后指针法
//前后指针法（单趟排序）
int QuickSort3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)//当cur未越界时继续
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界时，prev的位置
Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
return meeti;//返回key的当前位置
}
快速排序的非递归算法基本思路：
1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
2、当栈不为空时，读取栈中的信息（一次读取两个：一个是L，另一个是R），然后调用某一版本的单趟排序，排完后获得了meet的下标，然后判断meet的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的L和R入栈；若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。
3、反复执行步骤2，直到栈为空为止。
非递归快排代码实现
//类似于二叉树的遍历，根——右子树——左子树
void QuickSort4(int* a, int left, int right)
{
ST p;
StackInit(&p);
StackPush(&p, left);
StackPush(&p, right);
while (!StackEmpty(&p))
{
int right= StackTop(&p); //注意栈的性质，或进先出，因此先赋值给right
StackPop(&p);
int left= StackTop(&p);
StackPop(&p);
//if (left >= right) 可写可不写
//{
// return;
//}
int meet = QuickSort5(a, left, right);
if (left < meet - 1) //左序列还存在时
{
StackPush(&p, left);
StackPush(&p, meet - 1);
}
if (meet + 1 < right) //右序列还存在时
{
StackPush(&p, meet + 1);
StackPush(&p, right);
}
}
StackDestory(&p);
}
注意：这里要注意栈的性质后进先出，因此要先赋值给right再赋值给left。
图解代码
时间复杂度：O（nlogn）
快速排序的两个优化
1.三数取中
快速排序的时间复杂度是O(NlogN)，是我们在理想情况下计算的结果。在理想情况下，我们每次进行完单趟排序后，key的左序列与右序列的长度都相同：
若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，那么快速排序的时间复杂度就是O(NlogN)。
但是万一当待排序列本就是一个有序的序列时，我们若是依然每次都选取最左边或是最右边的数作为key，那么快速排序的效率将达到最低：
这时的时间复杂度为O（n^2)。其实，对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则则效率越高。
为了避免这种极端情况的发生，于是出现了三数取中：
三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。
代码实现
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2; //防止整形溢出
if (a[right] > a[mid])
{
if (a[mid] > a[left])
{
return mid;
}
else if (a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[left] > a[mid])
{
return mid;
}
else if (a[right] > a[left])
{
return right;
}
else
{
return left;
}
}
}
2.小区间的优化
我们可以看到，就算是上面理想状态下的快速排序，也不能避免随着递归的深入，每一层的递归次数会以2倍的形式快速增长。
为了减少递归树的最后几层递归，我们可以设置一个判断语句，当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，而且待排序列的长度越长，该效果越明显。
代码实现
//快速排序的小区间优化
void QuickSort6(int *a, int left, int right)
{
if (left >= right)
{
return;
}
if (right - left + 1 > 20)
{
int meet = QuickSort5(a, left, right);
QuickSort5(a, left, meet - 1);
QuickSort5(a, meet + 1, right);
}
else
{
ShellSort(a,right-left+1);
}
}
归并排序
归并排序是采用分治法的一个非常典型的应用。其基本思想是：先让每个子序列都有序，然后再合并这些子序列，让整个序列有序。这其中要注意了：
子序列又可以看成是一个整体又可以分成两个子序列，要直到分到序列只有一个数时，这时才不能继续分了，且当只有一个数时，这个序列就是有序的。其实这儿的思想和二叉树的好像，当你看完代码和递归过程后，你还会发现其实这个和二叉树的后序遍历很相似。
下面来看个例子：
其实这张图就相当于是整个递归的过程，分解的过程相当于递归的顺序执行，合并的过程相当于递归返回的过程。
递归实现
其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列，合并完毕后再将数据拷贝回原数组。
void MergeSort(int* a, int left, int right,int* temp)
{
if (left >= right)
return;
int mid = left + (right - left) / 2;
int begin1 = left, end1 = mid;
int begin2 = mid+1, end2 = right;
int i = left,j=0; //i一定要写成left不能写成0，如果是递归左序列还可以适用，但是递归到右序列时就不行了
MergeSort(a, left, mid, temp); //这里要注意区间的划分，不然可能出现死递归
MergeSort(a, mid + 1, right, temp);
while (begin1 <= end1&&begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
for (j = left; j < right + 1; j++)
{
a[j] = temp[j];
}
}
时间复杂度 ： O（NlogN） 空间复杂度： O（N）
递归图解
区间划分要注意（死递归）
在上面的代码中，我们将区间划分成了[left,mid]和[mid+1，right],是不是只能这样分了？带着这样的好奇，我尝试了另一种分法，将区间划分成[left,mid-1]和[mid,right],这样划分是否可以了？经过画图分析后，答案是不可以的，在这个问题中，区间只能这么划分。
如果你是这样划分的话，在某些测试用例中，可能会出现死递归。其原因是你的mid和right有可能永远不会相等，也就无法结束掉某个递归，因此造成了死递归。
非递归实现
归并排序的非递归并不像快速排序那样一定要用栈来实现，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序
这只是一个理想化的例子，在做这种题目时，我们一定要充分考虑到边界情况。
情况一：
第二个小区间存在，但是个数不满，这时我们需要对边界进行控制，不然会导致序列合并时数组越界的问题。
情况二：
第二个小区间不存在，第一个小区间存在，这时我们不需要在意第一个小区间有没有满，因为这时只有一个区间，无法进行序列的合并，所以直接不管它，即break出去就行。
代码实现
void _MergeSort(int *a, int begin1,int end1,int begin2,int end2, int * temp)
{
int j = begin1;
int i = begin1;
while (begin1 <= end1&&begin2 <= end2) //用&&链接，其中有一个结束就结束了
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
while (begin1 <= end1) //如果区间一还有则全部赋值过去
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2) //如果区间二还有则全部赋值过去，这时两个序列合并完成
{
temp[i++] = a[begin2++];
}
for (; j <= end2; j++) //将合并好的序列传给原数组
{
a[j] = temp[j];
}
}
void MergeSort2(int *a, int n)
{
int *temp = (int *)malloc(sizeof(int)*n);
if (temp == NULL)
{
printf("malloc failed\n");
exit(-1);
}
int gap = 1; //控制每次元素的个数
int i = 0;
while (gap < n)
{
for (i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + (2 * gap) - 1;
if (begin2 >= n) //此时只有第一个区间，不存在两个序列合并的需求，因此直接break
{
break;
}
if (end2 >= n) //此时第二个区间元素个数不满，为了防止合并两个序列时数组访问越界，在这里处理掉
{
end2 =n-1;
}
_MergeSort(a, begin1, end1, begin2, end2, temp);
}
gap *= 2;
}
free(temp);
}
递归图解
计数排序
计数排序又叫非比较排序，它不需要比较就可以排序，是不是很神奇了？它主要是利用哈希映射来实现的（这在之后c++部分会详细介绍），这里大概说下它的思路：
1.首先创建一个数组，那么这个数组的大小怎么定了？这取决于原数组中的最大值和最小值。
2.然后我们遍历原数组，遇到哪个值则在创建的数组中以他为下标的位置++。
3.最后打印创建的数组的下标，那个下标存放的值为几，则那个下标就打印几次。
注意：为什么我们这样就能保证数组是有序的了？其实最主要的原因是因为数组的下标本来就是有序的，其次这其中利用了哈希映射。
绝对映射和相对映射
上列中的映射方法称为绝对映射，即arr数组中的元素是几就在count数组中下标为几的位置++，但这样会造成空间浪费。例如，我们要将数组：1001,1002,1005，进行排序，难道我们要开辟1006个整型空间吗？
所以我们使用计数排序时，最好是使用相对映射。下面我们来简单介绍下相对映射：数组中的最小值就相对于count数组中的0下标，数组中的最大值就相对于count数组中的最后一个下标。这样，对于数组1001,1002,1005我们只需要开辟5个空间即可，即此时count数组中下标为i的位置，记录的是1001+i出现的次数。
总的来说：
绝对映射：count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
相对映射：count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。
这里也要注意：计数排序针对数字较为集中时处理比较高效，如果刚刚那个数组为1,100,1005则不管使用什么映射，都会存在空间的浪费。
代码实现
//计数排序
void CountSort(int*a, int sz)
{
int min = a[0], max = a[0];
int i = 0;
int j = 0;
for (i = 1; i < sz; i++)
{
if (a[i] < min)
{
min = a[i];
}
if (a[i]>max)
{
max = a[i];
}
}
int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身）
int *count = (int*)calloc(range, sizeof(int));//min和max之间的自然数个数（包括min和max本身）
if (count == NULL)
{
printf("calloc failed\n");
exit(-1);
}
统计相同元素出现次数（相对映射）
for (i = 0; i < sz; i++)
{
count[a[i]-min]++;
}
根据统计结果将序列回收到原来的序列中
for (i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i+min;
}
}
free(count);
}
时间复杂度：O(n+range) 空间复杂度：O（range)
八大排序性能测试
要想测试各个排序的性能，首先我们要保证给的数据的公平性，因为我们采用随机数组的方式。注意用完之后要释放，不然会内存泄漏。在测试的时候因为我们给的数据量都是很大的，为了不让我们等待太久，最好是使用Release版本测试。
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);
int* a5 = (int*)malloc(sizeof(int)*N);
int* a6 = (int*)malloc(sizeof(int)*N);
int* a7 = (int*)malloc(sizeof(int)*N);
int* a8 = (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];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
a8[i] = a1[i];
}
//为了防止给的随机数相对集中或者重复时计数排序的效率不真实
a7[0] = 0;
a7[10000] = 10000;
//这里最好将计数排序写在前面
/*int begin7 = clock();
CountSort(a7, N);
int end7 = clock();*/
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
BubbleSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort1(a5,0,N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort2(a6, N);
int end6 = clock();
int begin8 = clock();
HeapSort(a8, N);
int end8 = clock();
/*printf("CountSort:%d\n", end7 - begin7);*/
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("BubbleSort:%d\n", end4 - begin4);
printf("QuickSort1:%d\n", end5 - begin5);
printf("MergeSort2:%d\n", end6 - begin6);
printf("HeapSort:%d\n", end8 - begin8);
free(a7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a8);
}
注意：这里并没有测试计数排序，因为计数排序要单独来出来测试，放在一起测试，可能会出问题。
多测试几组后发现，快速排序基本都是最快的，这也是为什么人家敢叫快速排序的原因。