数据结构初阶：排序
本期博客我们来到了初阶数据结构最后一个知识点：排序
排序，我们从小到大就一直在接触，按身高、成绩、学号等等不同的排序我们已经历许多，那么各位是按怎样的方法进行排序的呢？
废话不多说这期博客我们对各种排序方法进行总结：
目录
一、排序的概念
二、常见的排序算法
三、常见的排序算法实现
3.1 直接插入排序
3.1.1 基本思想
3.1.2 代码实现
3.2 希尔排序
3.2.1 基本思想
3.2.2 代码实现
3.3 直接选择排序
3.3.1 基本思想
3.3.2 代码实现
3.4 堆排序
3.4.1 基本思想
3.4.1 代码实现
3.5 冒泡排序
3.5.1 基本思想
3.5.2 代码实现
3.6 快速排序（递归）
3.6.1 Hoare版本快速排序基本思想
3.6.2 Hoare版本快速排序代码实现
3.6.3 挖坑法版本快速排序基本思想
3.6.4 挖坑法版本快速排序代码实现
3.6.5 前后指针版本快速排序基本思想
3.6.6 前后指针版本快速排序代码实现
3.7 快速排序（非递归）
3.7.1 非递归快速排序的基本思想
3.7.2 非递归快速排序的代码实现
3.8 归并排序（递归）
3.8.1 归并排序基本思想
3.8.2 归并排序代码实现
3.9 归并排序（非递归）
3.8.1 非递归归并排序基本思想
3.8.2 非递归归并排序代码实现
3.9 计数排序
3.9.1 计数排序的基本思想
3.9.2 计数排序代码实现
四、所有排序算法总结
五、性能测试
5.1 测试代码
5.2 测试结果
六、排序算法全部代码
一、排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
二、常见的排序算法
三、常见的排序算法实现
3.1 直接插入排序
直接插入排序是简单的排序方法，无脑比较后插入即可
3.1.1 基本思想
即把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想。
下面是插入排序模拟图（按升序排序）：
可以看出，直接插入排序方法的时间复杂度为:O(n^2)，但是其效率会随着数据的有序性升高而提升。
3.1.2 代码实现
void InsertSort(int *a,int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i, temp;//end记录已排完元素的个数
temp = a[end + 1];//temp保存插入元素
while (end >= 0)//找到合适的插入位置
{
if (temp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = temp;//插入
}
}3.2 希尔排序
希尔排序建立在直接插入排序基础之上是对其的优化，主要就是先分组再使用直接插入排序。
3.2.1 基本思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行直接插入排序。然后，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。
下面是希尔排序举例模拟图（按升序排列）：
本次举例只讲述了一次将数组分为gap组的排序，实际在进行整体排序之前gap值可以多次改变，以此来进行多次预排序
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，并且在预排序中数组越来越接近有序，导致很难去计算，因此在一些书中给出的希尔排序的时间复杂度都不固定。我们时间复杂度暂时就按：O(n^1.3)来算。
3.2.2 代码实现
void ShellSort(int* a, int n)
{
int gap = n;
//gap不为1之前进行预排序
//gap值等于1时进行整体的直接插入排序
while (gap > 1)
{
gap = gap / 3 + 1;//不断改变gap值进行多次预排序，+1是为了保证gap值最后一次为1
for (int j = 0; j < gap; j++)//将整个数组分为gap组，每一组进行直接插入排序
{
for (int i = j; i < n - gap; i += gap)//一组进行直接插入排序
{
int temp, end = i;//end记录已排完元素的个数
temp = a[end + gap];//temp保存插入元素
while (end >= 0)//在组内找到合适的插入位置
{
if (temp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = temp;//插入
}
}
}
}
3.3 直接选择排序
直接选择排序在这里是最简单的排序方法
3.3.1 基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
但是这种方法太慢了，我们对其进行改进：每次遍历数组时选择最小和最大的数分别放在数组的起始和结束位置。
下面是改进方法举例模拟图：
该方法的时间复杂度是：O(n^2)，不如直接插入排序的效率（直接选择排序时间复杂度不会随数据的变化而变化）
3.3.2 代码实现
void Swap(int* a, int* b)//交换函数
{
int temp = *b;
*b = *a;
*a = temp;
}
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1, mini, maxi;
while (begin < end)
{
mini = begin;
maxi = begin;
for (int i = begin + 1; i <= end; i++)//找到最大与最小值
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[mini], &a[begin]);//交换
if (maxi == begin)//防止数据出现重叠,如果出现重叠需要进行位置更新
{
maxi = mini;
}
Swap(&a[maxi], &a[end]);//交换
begin++;
end--;
}
}3.4 堆排序
3.4.1 基本思想
堆排序在之前的树与二叉树——堆中详细讲过，这里不再赘述，直接附上链接：
数据结构初阶：树与二叉树——堆
3.4.1 代码实现
void AdjustDown(int* data, int n,int parent)//向下调整
{
int chlid = parent * 2 + 1;//找到其左孩子
while (chlid < n)//防止数组越界
{
if (data[chlid + 1] > data[chlid] && chlid + 1 < n)//判断左右孩子的大小，chlid + 1 < n要防止存在左孩子而无右孩子时的数组越界（想要按小堆调整需将前一个>改为<号）
{
chlid += 1;
}
if (data[chlid] > data[parent])//（想要按小堆调整需将 > 改为 < 号）
{
Swap(&data[chlid], &data[parent]);//将大的孩子元素与其替换
//继续向下比较替换
parent = chlid;
chlid = parent * 2 + 1;
}
else//如果孩子元素都没有其父元素大则直接跳出
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)//n-1是最后一个元素的物理位置（（n-1）-1）/2是其父节点的物理位置
{
AdjustDown(a, n, i);//向下调整
}
int end = n - 1;
while (end > 0)
{
Swap(&a[end], &a[0]);//每一次调整之后将最大的元素挪到堆的最后面
AdjustDown(a,end,0);
end--;
}
}
3.5 冒泡排序
冒泡排序，对于计算机类的同学再熟悉不过了
3.5.1 基本思想
遍历n-1（n为数组元素个数）次数组，每次遍历时比较相邻的两个元素将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动，这样每次遍历完数组最大值都会被带到数组末尾，下一次遍历时就可以少遍历一个数据。
思路模拟举例图（按升序排序）：
这样整个数组就排序完成了。
在这里冒泡排序的时间复杂度为:O(n^2)
3.5.2 代码实现
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
{
Swap(&a[j - 1], &a[j]);
}
}
}
}我们可以对其优化一下，当某一趟冒泡排序没有进行交换时（说明所有数据都有序了）直接跳出：
优化后的代码：
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;//exchange判断排序时是否进行了交换
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
{
Swap(&a[j - 1], &a[j]);
exchange = 1;
}
}
if (exchange == 0)
{
break;//没有进行交换进行跳出
}
}
}3.6 快速排序（递归）
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法
3.6.1 Hoare版本快速排序基本思想
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
下面是快速排序思路举例举例模拟图：
我们先以数组元素第一个值为基准（基准也可以定为数组元素最后一个值，视具体情况而定），进行快速排序的第一次排序：
我们发现本次排序过后基准元素前面的元素值全小于其基准值，基准元素后面的元素值全大于其值
这样一来基准元素在整体的数组中位置已经是正确的了，不需要对其再进行操作。
这样我们就可以将整个数组拆为基准元素前半部分和后半部分，对其分别再进行上述排序操作：
本次分为两组的排序分别已经完成，我们需要对其继续进行拆分再进行排序：
最后一次排序完成，整体快速排序结束。
在快速排序中，按升序排序时为了保证L和R指针相遇位置比基准值要小，在第一个元素做基准值时R指针要先走，在最后个元素做基准值时L指针要先走。
在理想情况下，假如每次取的基准值都在数组元素的中间值（这样每次进行拆分时都可以分掉数组的一半），快速排序算法的时间复杂度为：O(N*㏒⑵N)
在数组趋近于有序时，这样会导致每次进行拆分数组时一边元素极多一边元素极少，元素极多的数组会增加后续继续分组的次数，所以在最坏情况下快速排序算法的时间复杂度为：O(N^2)
该方法在递归时需要建立函数栈帧，所以空间复杂度为：O(N*㏒⑵N)
3.6.2 Hoare版本快速排序代码实现
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)//递归判断
return;
int left = begin, right = end;
int keyi = left;//确定基准元素下标
while (left < right)
{
while (left < right && a[right] >= a[keyi])//left<right是为了防止数组越界
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;//交换过后基准元素下标改变，需要更新
QuickSort(a, begin, keyi - 1);//递归拆分基准值左半部分
QuickSort(a, keyi + 1, end);//递归拆分基准值右半部分
}为了避免最坏情况的发生，我们可以使用三数取中的方法（即选取数组中开始、中间、末尾三个数值在中间的数来作为基准数），优化代码如下：
int GetMidIndx(int* a, int begin, int end)//三数取中
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
return mid;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[end] < a[mid])
return mid;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)//递归判断
return;
int mid = GetMidIndx(a, begin, end);//三数取中
Swap(&a[begin], &a[mid]);//取中后交换元素位置
int left = begin, right = end;
int keyi = begin;//确定基准元素下标
while (left < right)
{
while (left < right && a[right] >= a[keyi])//left<right是为了防止数组越界
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;//交换过后基准元素下标改变，需要更新
QuickSort(a, begin, keyi - 1);//递归拆分基准值左半部分
QuickSort(a, keyi + 1, end);//递归拆分基准值右半部分
}
在我们进行递归时，遇到小区间的数组（数组元素个数较少）时，可以不再进行拆分递归，而是直接对小区间数组进行直接插入排序来减少递归的消耗来提升效率，再优化代码如下：
int GetMidIndx(int* a, int begin, int end)//三数取中
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
return mid;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[end] < a[mid])
return mid;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)//递归判断
return;
if ((end - begin + 1) <= 10)//遇到小区间数组直接插入排序，10只是一种取值，取值视情况而定
{
InsertSort(&a[begin], end - begin + 1);
}
else
{
int mid = GetMidIndx(a, begin, end);//三数取中
Swap(&a[begin], &a[mid]);//取中后交换元素位置
int left = begin, right = end;
int keyi = begin;//确定基准元素下标
while (left < right)
{
while (left < right && a[right] >= a[keyi])//left<right是为了防止数组越界
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;//交换过后基准元素下标改变，需要更新
QuickSort(a, begin, keyi - 1);//递归拆分基准值左半部分
QuickSort(a, keyi + 1, end);//递归拆分基准值右半部分
}
}
3.6.3 挖坑法版本快速排序基本思想
挖坑法比Hoare版本更容易理解，即进行排序时，提取基准元素（基准元素的位置就空缺了），在R指针移动后将找到的元素直接填到基准元素的位置上（R指向的元素的位置就空缺了），接着在L指针移动过后将找到的元素直接填到R所在元素的位置上（L指向的元素的位置就空缺了），然后R再开始移动接着填补L指针上的位置元素（R指向的元素的位置再次空缺）·········这样重复每次找到元素之后R和L指针必有一个位置是空缺的，等到它们相遇时将基准元素填补到它们所在的位置上即可。
这样单次遍历结束。接下来进行拆分数组一直进行此排序。
3.6.4 挖坑法版本快速排序代码实现
int PartSort2(int* a, int begin, int end)
{
int mid = GetMidIndx(a, begin, end);//三数取中
Swap(&a[begin], &a[mid]);//取中后交换元素位置
int left = begin, right = end;
int key = a[begin];
int hole = left;//记录空缺元素位置
while (left < right)
{
while (left < right && a[right] >= key)//left<right是为了防止数组越界
{
right--;
}
a[hole] = a[right];//填补空缺位置
hole = right;//更新空缺位置
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];//填补空缺位置
hole = left;//更新空缺位置
}
a[hole] = key;//最后将基准元素插入到空缺位置
return hole;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)//递归判断
return;
if ((end - begin + 1) <= 10)//遇到小区间数组直接插入排序，10只是一种取值，取值视情况而定
{
InsertSort(&a[begin], end - begin + 1);
}
else
{
int keyi = PartSort2(a, begin, end);//挖坑法
QuickSort(a, begin, keyi - 1);//递归拆分基准值左半部分
QuickSort(a, keyi + 1, end);//递归拆分基准值右半部分
}
}
3.6.5 前后指针版本快速排序基本思想
前后指针版本在排序时会有一前一后两个指针（前指针prev，后指针cur），排序时初始前指针prev在基准元素位（数组首元素位），后指针cur在prev指针后一个元素位置。接着cur指针开始移动找到比基准元素小的元素停住（找到比基准元素大的元素就继续向前移动），此时prev指针向前移动一位后将所在位置元素与cur指针所在元素交换。接着cur指针继续向前移动，按上述规律遇到比基准元素小的元素就与prev指针向前移动一位后将所在位置元素交换，一直到cur指针遍历完整个数组。cur遍历完整个数组后再将基准元与prev指针所在元素位置继续交换。
这样单次遍历结束。接下来进行拆分数组一直进行此排序。
下面是对数组进行单次前后指针版本快速排序的基本思想举例图：
单次排序完成，接着就以基准元素对数组进行拆分继续排序，这里不再进行举例。
3.6.6 前后指针版本快速排序代码实现
int PartSort3(int* a, int begin, int end)
{
int prev = begin, cur = begin + 1, key = a[begin];
while (cur <= end)
{
while (cur <= end && a[cur] >= key)//一直找到比key小的元素
{
cur++;
}
Swap(&a[++prev], &a[cur++]);//找到了进行交换
}
Swap(&a[prev], &a[begin]);//最后进行基准元素与prev所在的元素进行交换
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)//递归判断
return;
if ((end - begin + 1) <= 10)//遇到小区间数组直接插入排序，10只是一种取值，取值视情况而定
{
InsertSort(&a[begin], end - begin + 1);
}
else
{
int keyi = PartSort3(a, begin, end);//前后指针版本
QuickSort(a, begin, keyi - 1);//递归拆分基准值左半部分
QuickSort(a, keyi + 1, end);//递归拆分基准值右半部分
}
}但是这样有一种特殊情况：prev和cur指针在同一位置进行交换是没有意义的，所以我们加上一个判断条件优化一下代码：
int PartSort3(int* a, int begin, int end)
{
int prev = begin, cur = begin + 1, key = a[begin];
while (cur <= end)
{
if (a[cur] < key && ++prev != cur)//找到比key小的元素并且prev和cur不在同一位置时进行交换
{
Swap(&a[prev], &a[cur]);//找到了进行交换
}
cur++;
}
Swap(&a[prev], &a[begin]);//最后进行基准元素与prev所在的元素进行交换
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)//递归判断
return;
if ((end - begin + 1) <= 10)//遇到小区间数组直接插入排序，10只是一种取值，取值视情况而定
{
InsertSort(&a[begin], end - begin + 1);
}
else
{
int keyi = PartSort3(a, begin, end);//前后指针版本
QuickSort(a, begin, keyi - 1);//递归拆分基准值左半部分
QuickSort(a, keyi + 1, end);//递归拆分基准值右半部分
}
}
看了上述代码，各位是不是有这样一种感觉：虽然前后指针版本相对抽像，但是代码更简洁呢？
3.7 快速排序（非递归）
在理解了快速排序的递归方法之后，我们进行递归方法来实现快速排序时会有栈溢出的风险。
为了规避这些风险提升快速排序效率我们现在来挑战一下非递归的写法：
3.7.1 非递归快速排序的基本思想
对于递归方法，递归时最重要的就是建立函数栈帧来一层一层来保存所要进行数组拆分的区间。
当不使用递归方法时，我们可以建立一个栈来保存这些所要进行拆分的区间，即在每一次单次排序完返回基准元素位置时将基准元素位置的两边的区间进行入栈，下一次排序时就出栈一个区间来进行排序，直到栈空时就不再单次进行排序了。
在这里我们需要一下对栈进行操作的基本函数：
// 支持动态增长的栈
typedef struct Stack
{
int* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = (int*)malloc(sizeof(int) * 4);
if (ps->_a == NULL)
{
perror("malloc");
exit(-1);
}
ps->_capacity = 4;
ps->_top = 0;
}
// 入栈
void StackPush(Stack* ps, int data)
{
assert(ps);//传入的指针不能为空
if (ps->_capacity == ps->_top)//判断栈是否已满，满了就扩容
{
int* temp = (int*)realloc(ps->_a, (ps->_capacity + 4) * sizeof(int));
if (temp == NULL)
{
perror("realloc");
exit(-1);
}
ps->_a = temp;
ps->_capacity += 4;
}
ps->_a[ps->_top] = data;//向栈内添加数据
ps->_top++;//栈顶增加1
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);//传入的指针不能为空
if (ps->_top <= 0)//栈空就不可出栈了
return;
ps->_top--;
}
// 获取栈顶元素
int StackTop(Stack* ps)
{
assert(ps);//传入的指针不能为空
assert(ps->_top > 0);//栈不能为空
return ps->_a[ps->_top - 1];//返回栈顶元素
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);//传入的指针不能为空
return ps->_top == 0;//判断栈是否为空
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);//传入的指针不能为空
free(ps->_a);//释放栈数据空间
ps->_capacity = 0;//初始栈容量为4
ps->_top = 0;//初始栈内元素为0
}
3.7.2 非递归快速排序的代码实现
void QuickSortNotR(int* a, int begin, int end)
{
//建栈
Stack s;
StackInit(&s);
//入栈
StackPush(&s, begin);
StackPush(&s, end);
while (!StackEmpty(&s))//栈不为空就进行排序
{
//出一个区间进行排序
int right = StackTop(&s);
StackPop(&s);
int left = StackTop(&s);
StackPop(&s);
int keyi = PartSort3(a, left, right);
//排序完判断是否继续进行拆分，如果满足条件就将区间入栈继续进行排序
if (keyi + 1 < right)
{
StackPush(&s, keyi + 1);
StackPush(&s, right);
}
if (keyi - 1 > left)
{
StackPush(&s, left);
StackPush(&s, keyi - 1);
}
}
StackDestroy(&s);//排序完成销毁栈
}3.8 归并排序（递归）
3.8.1 归并排序基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
就是将一个数组不断二分，直到不能再分为止，再将不能再分的数组两两排序成一个有序数组，再将排序的完的数组再两两排序成一个有序数组，安此方法一直排序合成一整个数组。
下面的是归并排序思路举例模拟图：
归并排序的时间复杂度为：O(N*㏒⑵N)
但是归并排序需要开辟一个临时数组来保存归并时的数据，所以空间复杂度为:O(N)
3.8.2 归并排序代码实现
void _MergeSort(int* a, int* temp, int begin, int end)
{
if (end <= begin)//判断是否要对数组进行二分
return;
//递归进行数组二分
int mid = (begin + end) / 2;
_MergeSort(a, temp, begin, mid);
_MergeSort(a, temp, mid + 1, end);
//归并二分后的数组
int begin1 = begin, end1 = mid, begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end)
{
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++];
}
memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));//将归并完的临时数组拷贝到原数组中
}
void MergeSort(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);//临时数组用来保存归并后的数组
if (temp == NULL)
{
perror("malloc");
exit(-1);
}
_MergeSort(a, temp, 0, n - 1);
free(temp);
temp = NULL;
}
3.9 归并排序（非递归）
3.8.1 非递归归并排序基本思想
在非递归中实现归并排序，我们可以直接先将数组按rangeN（每组归并元素的个数）来一一归并。rangN初始值为1，即将整个数组每个元素两两一一归并，这样归并后再将rangN乘以2再次归并，以此类推一直到rangN的值大于等于数组元素个数时结束归并，整个数组排序完成。
下面是非递归归并排序思路举例模拟图：
3.8.2 非递归归并排序代码实现
注意非2倍数元素个数的数组归并时存在数组越界的问题，要进行判断修正。
void MergeSortNotR(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);//临时数组用来保存归并后的数组
if (temp == NULL)
{
perror("malloc");
exit(-1);
}
int rangeN = 1;
while (rangeN < n)
{
for (int j = 0; j < n; j += 2 * rangeN)
{
int begin1 = j, end1 = j + rangeN - 1;
int begin2 = end1 + 1, end2 = begin2 + rangeN - 1;
//判断区间是否越界
if (end1 >= n)//end1,begin2,end2越界
{
break;//直接跳出
}
if (begin2 >= n)//begin2,end2越界
{
break;//直接跳出
}
if (end2 >= n)//end2越界
{
end2 = n - 1;//修正end2后继续归并
}
//将两组含rangN个元素的区间进行归并
int i = j;
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++];
}
//将归并完的临时数组拷贝到原数组中(归并一拷一组)
memcpy(a + j, temp + j, sizeof(int) * (end2 - j + 1));
}
rangeN *= 2;
}
free(temp);
temp = NULL;
}
3.9 计数排序
3.9.1 计数排序的基本思想
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
该排序先要开辟一个range（排序数组最大元素和最小元素之差再加一）大小的数组来统计相同元素出现次数，再根据统计的结果将序列回收到原来的序列中。
下面是计数排序思路举例模拟图：
该算法的时间复杂度为：O(N+range)
空间复杂度为：O(range)
从时间复杂度可以看出此方法适用于range比N小的数组排序（即元素值不分散的数组），并且只适用于整型（如浮点型就无能为力了），局限性较强。
3.9.2 计数排序代码实现
void CountSort(int* a, int n)
{
//统计排序数组中最大最小值之差加1
int max = a[0], min = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int range = max - min + 1;
//开辟新数组
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("calloc");
exit(-1);
}
//统计相同元素出现次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//将统计的结果将序列回收到原来的序列
int k = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[k++] = i + min;
}
}
free(count);
count = NULL;
}
四、所有排序算法总结
五、性能测试
理论上说说可不行，我们不能只限于纸上谈兵，下面我们来到了我们最激动人心的测试环结
5.1 测试代码
void TestOP(const int N)
{
srand(time(0));
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);
int* a9 = (int*)malloc(sizeof(int) * N);
int* a10 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand() + 1;
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];
a9[i] = a1[i];
a10[i] = a1[i];
}
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();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
BubbleSort(a5, N);
int end5 = clock();
int begin6 = clock();
QuickSort(a6, 0, N - 1);
int end6 = clock();
int begin7 = clock();
QuickSortNotR(a7, 0, N - 1);
int end7 = clock();
int begin8 = clock();
MergeSort(a8, N);
int end8 = clock();
int begin9 = clock();
MergeSortNotR(a9, N);
int end9 = clock();
int begin10 = clock();
CountSort(a10, N);
int end10 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("BubbleSort:%d\n", end5 - begin5);
printf("QuickSort:%d\n", end6 - begin6);
printf("QuickSortNotR:%d\n", end7 - begin7);
printf("MergeSort:%d\n", end8 - begin8);
printf("MergeSortNotR:%d\n", end9 - begin9);
printf("CountSort:%d\n", end10 - begin10);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
free(a8);
free(a9);
free(a10);
}
5.2 测试结果
排序算法哪家强？请看以下结果(以毫秒为单位)：
Debug环境下：
Release环境下：
六、排序算法全部代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<time.h>
//插入排序
void InsertSort(int *a,int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i, temp;//end记录已排完元素的个数
temp = a[end + 1];//temp保存插入元素
while (end >= 0)//找到合适的插入位置
{
if (temp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = temp;//插入
}
}
//希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
//gap不为1之前进行预排序
//gap值等于1时进行整体的直接插入排序
while (gap > 1)
{
gap = gap / 3 + 1;//不断改变gap值进行多次预排序，+1是为了保证gap值最后一次为1
for (int j = 0; j < gap; j++)//将整个数组分为gap组，每一组进行直接插入排序
{
for (int i = j; i < n - gap; i += gap)//一组进行直接插入排序
{
int temp, end = i;//end记录已排完元素的个数
temp = a[end + gap];//temp保存插入元素
while (end >= 0)//在组内找到合适的插入位置
{
if (temp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = temp;//插入
}
}
}
}
//直接交换排序
void Swap(int* a, int* b)//交换函数
{
int temp = *b;
*b = *a;
*a = temp;
}
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1, mini, maxi;
while (begin < end)
{
mini = begin;
maxi = begin;
for (int i = begin + 1; i <= end; i++)//找到最大与最小值
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[mini], &a[begin]);//交换
if (maxi == begin)//防止数据出现重叠,如果出现重叠需要进行位置更新
{
maxi = mini;
}
Swap(&a[maxi], &a[end]);//交换
begin++;
end--;
}
}
//堆排序
void AdjustDown(int* data, int n, int parent)//向下调整
{
int chlid = parent * 2 + 1;//找到其左孩子
while (chlid < n)//防止数组越界
{
if (data[chlid + 1] > data[chlid] && chlid + 1 < n)//判断左右孩子的大小，chlid + 1 < n要防止存在左孩子而无右孩子时的数组越界（想要按小堆调整需将前一个>改为<号）
{
chlid += 1;
}
if (data[chlid] > data[parent])//（想要按小堆调整需将 > 改为 < 号）
{
Swap(&data[chlid], &data[parent]);//将大的孩子元素与其替换
//继续向下比较替换
parent = chlid;
chlid = parent * 2 + 1;
}
else//如果孩子元素都没有其父元素大则直接跳出
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)//n-1是最后一个元素的物理位置（（n-1）-1）/2是其父节点的物理位置
{
AdjustDown(a, n, i);//向下调整
}
int end = n - 1;
while (end > 0)
{
Swap(&a[end], &a[0]);//每一次调整之后将最大的元素挪到堆的最后面
AdjustDown(a, end, 0);
end--;
}
}
//冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;//exchange判断排序时是否进行了交换
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
{
Swap(&a[j - 1], &a[j]);
exchange = 1;
}
}
if (exchange == 0)
{
break;//没有进行交换进行跳出
}
}
}
//递归快速排序
int GetMidIndx(int* a, int begin, int end)//三数取中
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
return mid;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[end] < a[mid])
return mid;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}
int PartSort1(int* a, int begin, int end)//Hoare版本
{
int mid = GetMidIndx(a, begin, end);//三数取中
Swap(&a[begin], &a[mid]);//取中后交换元素位置
int left = begin, right = end;
int keyi = begin;//确定基准元素下标
while (left < right)
{
while (left < right && a[right] >= a[keyi])//left<right是为了防止数组越界
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;//交换过后基准元素下标改变，需要更新
return keyi;
}
int PartSort2(int* a, int begin, int end)//挖坑法
{
int mid = GetMidIndx(a, begin, end);//三数取中
Swap(&a[begin], &a[mid]);//取中后交换元素位置
int left = begin, right = end;
int key = a[begin];
int hole = left;//记录空缺元素位置
while (left < right)
{
while (left < right && a[right] >= key)//left<right是为了防止数组越界
{
right--;
}
a[hole] = a[right];//填补空缺位置
hole = right;//更新空缺位置
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];//填补空缺位置
hole = left;//更新空缺位置
}
a[hole] = key;//最后将基准元素插入到空缺位置
return hole;
}
int PartSort3(int* a, int begin, int end)//前后指针版本
{
int prev = begin, cur = begin + 1, key = a[begin];
while (cur <= end)
{
if (a[cur] < key && ++prev != cur)//找到比key小的元素并且prev和cur不在同一位置时进行交换
{
Swap(&a[prev], &a[cur]);//找到了进行交换
}
cur++;
}
Swap(&a[prev], &a[begin]);//最后进行基准元素与prev所在的元素进行交换
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)//递归判断
return;
if ((end - begin + 1) <= 10)//遇到小区间数组直接插入排序，10只是一种取值，取值视情况而定
{
InsertSort(&a[begin], end - begin + 1);
}
else
{
//int keyi = PartSort1(a, begin, end);//Hoare版本
//int keyi = PartSort2(a, begin, end);//挖坑法
int keyi = PartSort3(a, begin, end);//前后指针版本
QuickSort(a, begin, keyi - 1);//递归拆分基准值左半部分
QuickSort(a, keyi + 1, end);//递归拆分基准值右半部分
}
}
// 支持动态增长的栈
typedef struct Stack
{
int* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = (int*)malloc(sizeof(int) * 4);
if (ps->_a == NULL)
{
perror("malloc");
exit(-1);
}
ps->_capacity = 4;
ps->_top = 0;
}
// 入栈
void StackPush(Stack* ps, int data)
{
assert(ps);//传入的指针不能为空
if (ps->_capacity == ps->_top)//判断栈是否已满，满了就扩容
{
int* temp = (int*)realloc(ps->_a, (ps->_capacity + 4) * sizeof(int));
if (temp == NULL)
{
perror("realloc");
exit(-1);
}
ps->_a = temp;
ps->_capacity += 4;
}
ps->_a[ps->_top] = data;//向栈内添加数据
ps->_top++;//栈顶增加1
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);//传入的指针不能为空
if (ps->_top <= 0)//栈空就不可出栈了
return;
ps->_top--;
}
// 获取栈顶元素
int StackTop(Stack* ps)
{
assert(ps);//传入的指针不能为空
assert(ps->_top > 0);//栈不能为空
return ps->_a[ps->_top - 1];//返回栈顶元素
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);//传入的指针不能为空
return ps->_top == 0;//判断栈是否为空
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);//传入的指针不能为空
free(ps->_a);//释放栈数据空间
ps->_capacity = 0;//初始栈容量为4
ps->_top = 0;//初始栈内元素为0
}
//非递归快速排序
void QuickSortNotR(int* a, int begin, int end)
{
//建栈
Stack s;
StackInit(&s);
//入栈
StackPush(&s, begin);
StackPush(&s, end);
while (!StackEmpty(&s))//栈不为空就进行排序
{
//出一个区间进行排序
int right = StackTop(&s);
StackPop(&s);
int left = StackTop(&s);
StackPop(&s);
int keyi = PartSort3(a, left, right);
//排序完判断是否继续进行拆分，如果满足条件就将区间入栈继续进行排序
if (keyi + 1 < right)
{
StackPush(&s, keyi + 1);
StackPush(&s, right);
}
if (keyi - 1 > left)
{
StackPush(&s, left);
StackPush(&s, keyi - 1);
}
}
StackDestroy(&s);//排序完成销毁栈
}
//递归归并排序
void _MergeSort(int* a, int* temp, int begin, int end)
{
if (end <= begin)//判断是否要对数组进行二分
return;
//递归进行数组二分
int mid = (begin + end) / 2;
_MergeSort(a, temp, begin, mid);
_MergeSort(a, temp, mid + 1, end);
//归并二分后的数组
int begin1 = begin, end1 = mid, begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end)
{
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++];
}
memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));//将归并完的临时数组拷贝到原数组中
}
void MergeSort(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);//临时数组用来保存归并后的数组
if (temp == NULL)
{
perror("malloc");
exit(-1);
}
_MergeSort(a, temp, 0, n - 1);
free(temp);
temp = NULL;
}
//非递归归并排序
void MergeSortNotR(int* a, int n)
{
int* temp = (int*)malloc(sizeof(int) * n);//临时数组用来保存归并后的数组
if (temp == NULL)
{
perror("malloc");
exit(-1);
}
int rangeN = 1;
while (rangeN < n)
{
for (int j = 0; j < n; j += 2 * rangeN)
{
int begin1 = j, end1 = j + rangeN - 1;
int begin2 = end1 + 1, end2 = begin2 + rangeN - 1;
//判断区间是否越界
if (end1 >= n)//end1,begin2,end2越界
{
break;//直接跳出
}
if (begin2 >= n)//begin2,end2越界
{
break;//直接跳出
}
if (end2 >= n)//end2越界
{
end2 = n - 1;//修正end2后继续归并
}
//将两组含rangN个元素的区间进行归并
int i = j;
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++];
}
//将归并完的临时数组拷贝到原数组中(归并一拷一组)
memcpy(a + j, temp + j, sizeof(int) * (end2 - j + 1));
}
rangeN *= 2;
}
free(temp);
temp = NULL;
}
//计数排序
void CountSort(int* a, int n)
{
//统计排序数组中最大最小值之差加1
int max = a[0], min = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int range = max - min + 1;
//开辟新数组
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("calloc");
exit(-1);
}
//统计相同元素出现次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//将统计的结果将序列回收到原来的序列
int k = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[k++] = i + min;
}
}
free(count);
count = NULL;
}
// 测试排序的性能对比
void TestOP(const int N)
{
srand(time(0));
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);
int* a9 = (int*)malloc(sizeof(int) * N);
int* a10 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand() + 1;
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];
a9[i] = a1[i];
a10[i] = a1[i];
}
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();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
BubbleSort(a5, N);
int end5 = clock();
int begin6 = clock();
QuickSort(a6, 0, N - 1);
int end6 = clock();
int begin7 = clock();
QuickSortNotR(a7, 0, N - 1);
int end7 = clock();
int begin8 = clock();
MergeSort(a8, N);
int end8 = clock();
int begin9 = clock();
MergeSortNotR(a9, N);
int end9 = clock();
int begin10 = clock();
CountSort(a10, N);
int end10 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("BubbleSort:%d\n", end5 - begin5);
printf("QuickSort:%d\n", end6 - begin6);
printf("QuickSortNotR:%d\n", end7 - begin7);
printf("MergeSort:%d\n", end8 - begin8);
printf("MergeSortNotR:%d\n", end9 - begin9);
printf("CountSort:%d\n", end10 - begin10);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
free(a8);
free(a9);
free(a10);
}本期博客到这里就全部结束了，代码量庞大若有纰漏还请大佬在评论区指出呀~
目前数据结构初阶的知识点已经全部结束了，下面会给大家带来一些经典例题的讲解，请各位看客不要走开哦~