常见的排序方法
本期的内容是排序，这里的排序方法都是排升序，把特定条件反过来就是排降序
文章目录
- 前言
- 插入排序
- 直接插入排序
- 希尔排序( 缩小增量排序 )
- 选择排序
- 直接选择排序
- 堆排序
- 交换排序
- 冒泡排序
- 快速排序（快排）
- hoare版本
- 单趟排序的价值
- 优化1
- 优化2
- 挖坑法
- 前后指针法
- 快速排序（非递归）
- 测试排序性能对比
- 全部代码
前言
我们前面已经学习了堆排序，接下来就来看看剩下的排序。并且了解每个排序的优缺点。
栈
插入排序
基本思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为
止，得到一个新的有序序列 。
举个简单的例子：扑克牌
直接插入排序
当插入第i(i>=1 )个元素时，前面的array[0],array[1 ],…,array[i-1 ]已经排好序，此时用array[i]的排序码与 array[i-1 ],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
简单的说就是如果排升序：插入数据小于前面的数据就把插入的数据放到前面，把大的数据调到后面去
代码如下：
void InsertSort(int* a, int n)//插入排序
{//在[0，end]插入end+1 [0,end+1]有序
//时间复杂度O（N）--顺序有序
//时间复杂度O（N^2）--逆序
for (int i = 0; i < n - 1; ++i)//i下标最大为倒数第二个元素的下标
{
int end = i;//内部最好不改变i的值，用end进行操作
int tmp = a[end + 1];//tmp是i的下一个元素
while (end >= 0)//等于0时就是第一个数据
{
if (tmp < a[end])//如果end后一个数据小于end
{
a[end + 1] = a[end];//把end的数据挪动到后一个位置
--end;//end自减1
}
else
break;//如果end后一个数据大于end数据，那么就跳出循环
}
a[end + 1] = tmp;//不管是插入成功了end+1数据，还是end自减为负数了，都执行该代码
}
}
直接插入排序的特性总结：
1 . 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度： O(N^2)
3. 空间复杂度： O(1 )，它是一种稳定的排序算法
4. 稳定性：稳定
希尔排序( 缩小增量排序 )
希尔排序是在直接插入排序的基础上进行的一系列优化
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
希尔排序的主要过程分两步：
1、预排序——目的：让数据接近有序
2、直接插入排序——目的：让数据有序
也就是说，希尔排序先进行预排序，这个过程要把数据大体上处理完成，最后使用直接插入排序就完成希尔排序
这里有一个关键变量：
gap。一般情况下，数据少，gap小；数据多，gap大
对于升序：
gap越大，大的数据越快的跳到后面，小的数据越快跳到前面,但是不是很接近有序
gap越小，跳的越慢，但是接近有序
gap的取值方法很多样，这就导致了许多希尔排序的时间复杂度并不是特别的精准，我们只需大概了解即可
预排序就是把数据间隔为gap的分为一组数据，然后进行插入排序
我们来看看图片：
可能有许多人对于上面的图片似懂非懂，其实简单一点就是：
从第一个数据开始，把每间隔gap个数据分为一组，一直到到间隔小于gap；
就再从第二个数据开始，每间隔gap个数据分为一组，一直到到间隔小于gap；
就再从第三个数据开始…依此类推下去
我们来看看希尔排序的代码：
void ShellSort(int* a, int n)//希尔排序
{
//gap > 1就是预排序
//gap == 1就是直接插入排序
int gap = n;
while (gap > 1)//gap大于1表示预排序没有完成
{
//这里gap要保证最后一次的值计算之后等于1进行直接插入排序
gap = gap / 3 + 1;//当gap走到这里除等2，或者除3加1 等于1 表示gap已经预排序完成了，可以直接进行插入排序了
//gap /= 2;//除2预排序次数要多一些
for (int j = 0; j < gap; ++j)//多少次预排序
{
for (int i = j; i < n - gap; i += gap)//一次希尔预排序
//for (int i = 0; i < n - gap; ++i)//让两个for循环变成一个for循环，这里多组预排序共同进行
{
int end = i;//不能在循环内部直接改变i的值
int tmp = a[end + gap];//记录end的后一个数据
while (end >= 0)//如果end<0表示所有数据都比tmp大
{
if (tmp < a[end])//如果tmp小于end
{
a[end + gap] = a[end];//把end数据赋值给end后一个位置，这里end原来后面的数据是tmp，覆盖不影响tmp
end -= gap;//end一次减gap个位置
}
else
break;//如果tmp大于end跳出循环
}
a[end + gap] = tmp;//不管是所有数据都小于tmp还是tmp插入成功了，都把tmp的值给到end+gap的位置都是正确的
}
}
}
}
关于希尔排序的时间复杂度因为种种原因算不出具体值，但是是接近O（N*logN）的
希尔排序的特性总结：
1 . 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定：
《数据结构(C语言版)》 — 严蔚敏
《数据结构-用面相对象方法与C++描述》 — 殷人昆
因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：
4. 稳定性：不稳定
选择排序
基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。
直接选择排序
先说一下这个排序的缺点：时间复杂度永远为O（N^2），不管数据有没有序，选择排序的时间复杂度都不会变。由此可知这个排序与其他排序相比确实拉跨了点
在元素集合array[i]–array[n-1 ]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换 在剩余的array[i]–array[n-2]（array[i+1 ]–array[n-1 ]）集合中，重复上述步骤，直到集合剩余1个元素
void ChoiceSort(int* a, int n)
{
/*for (int i = 0; i < n - 1; ++i)
{
int m = i;
for (int j = i + 1; j < n; ++j)
{
if (a[m] > a[j])
m = j;
}
Swap(&a[i], &a[m]);
}*/
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
if (a[i] > a[j])
Swap(&a[i], &a[j]);
}
}
}
直接选择排序的特性总结：
1 . 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度： O(N^2)
3. 空间复杂度： O(1 )
4. 稳定性：不稳定
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
因为我们之前讲过了，所以就不再过多介绍了
void Swap(int* n, int* m)//传值调用不会交换外面的两个值，所以说用传址调用
{
int tmp = *n;
*n = *m;
*m = tmp;
}
void Justdown(int* a, int size, int parent)//向下转换
{
int midchild = parent * 2 + 1;//我们假设左节点为两个节点中的小节点，那么左节点的下标就是父节点下标乘以2加上1
while (midchild < size)//这里不要用父节点判断是否向下调整完毕，如果没有下面的break会判断失误，出不了循环
{
//if (midchild + 1 < size && a[midchild + 1] > a[midchild])//求取大堆最上面的节点。大于就是升序，上面是最小值
if (midchild + 1 < size && a[midchild + 1] < a[midchild])//小节点的坐标加1要小于size，不然就相当于越界了
//如果右节点的值小于左节点，那么midchild下标加1，得到两个节点中的小节点
{
midchild++;
}
//if (a[midchild] > a[parent])//求取大堆最上面的节点。大于就是升序，上面是最小值
if (a[midchild] < a[parent])
//如果小节点的值小于父节点的值就进去开始向下调整
{
Swap(&a[midchild], &a[parent]); //交换父节点与小节点的值
parent = midchild;//把小节点的下标赋给父节点
midchild = parent * 2 + 1;//此时新的小节点下标就为父节点乘以2加上1
}
else
{
break;//如果小节点的值大于等于父节点就不用进行操作（这是针对小根堆的注释）
}
}
}
void HeapSort(int* a, int n)//堆排序
{//logN
for (int i = (n - 1 - 1) / 2; i >= 0; --i)//创建堆
{
Justdown(a, n, i);//向下调整
}
int i = 1;
while (i < n)//N
{
Swap(&a[0], &a[n - i]);//小堆就是降序，大堆就是升序
Justdown(a, n - i, 0);
++i;
}
}
堆排序最下面一层排序的调整次数（时间复杂度）是：N/2logN
倒数第二层的调整次数（时间复杂度）是：N/4logN
倒数第三层的调整次数（时间复杂度）是：N/8logN
…
和起来的结果用大O渐进法就是：NlogN
这个就是堆排序的时间复杂度
交换排序
基本思想：
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序
这个是我们的老朋友了
void BubbleSort(int* a, int n)//冒泡排序
{
for (int i = 0; i < n - 1; i++)//n个数据要排序n-1躺
{
int flag = 0;
for (int j = 0; j < n - i - 1; j++)//每一趟排一个数据的过程
{
if (a[j + 1] < a[j])//如果j后一个数据小于j就交换
{
Swap(&a[j], &a[j + 1]);
flag = 1;//如果flag改变就表示数据不是有序的，就要继续进行排序
}
}
if (flag == 0)//如果flag没有改变，就表示数据有序，不用排序直接退出
break;
}
}
冒泡排序的特性总结：
1 . 冒泡排序是一种非常容易理解的排序
2. 时间复杂度： O(N^2)
3. 空间复杂度： O(1 )
4. 稳定性：稳定
快速排序（快排）
快速排序是Hoare于1 962年提出的一种二叉树结构的交换排序方法
基本思想：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
// 假设按照升序对array数组中 [ left, right )区间中的元素进行排序
void QuickSort ( int array [ ] , int left, int right )
{
if( right - left <= 1)
return;
// 按照基准值对array数组的 [ left, right )区间中的元素进行划分
int div = partion (array, left, right ) ;
// 划分成功后以div为边界形成了左右两部分 [ left, div) 和 [div+1, right )
// 递归排[ left, div)
QuickSort (array, left, div) ;
// 递归排[div+1, right )
QuickSort (array, div+1, right ) ;
}
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉
树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式（单趟排序的方法）有：
hoare版本
简单点来说：我们选中第一个或者最后一个数据为key，单趟排序之后，key左边都是比key小的数据，右边都是比key大的数据
如下图：
R从右边开始找小于key的数据，L从左边开始找比key大的数据，两个数据都找到之后直接交换，直到L和R相遇，将相遇的值与key的值交换
重要问题：相遇位置一定比key要小吗？
解决方案：R先走，找小。如果找不到就说明key就是最小值，否则肯定找的到比key小的值
同理，如果是右边数据为key，那么左边的L就要先走
单趟排序的价值
1、key的值所在位置就是正确的位置
2、key分开了区间，key左边的数据都是比key小的，右边的数据都是比key大的，[left,key-1] ，key ，[key+1,right] 这里key的位置是确定了，但是左右区间数据没有确定，所以用递归的方法来处理
代码：
int PartSort1(int* a, int left, int right)//hoare第一种方法单趟的排序
{
int key = left;//如果key是最左值，那么就先动right;如果key是最右值，那么先动left
while (left < right)
{
while (left < right && a[right] >= a[key])//确定key为左值，那么R先走
//这里需要要left<right——因为while不是一个判断语句，如果特殊情况：
//1、a的所有值都比key要大，那么right会一直减减，直到越界成为负数
//2、right减减不会停下来，会与left错过了
//所以left要小于right
//如果左值或者右值等于key就继续找
{
--right;
}
while (left < right && a[left] <= a[key])//L后走
{
++left;
}
if (left < right)//如果R和L没有相遇
Swap(&a[left], &a[right]);//把左边大于key的值与右边小于key的值进行交换
}
//到这里left和right已经相遇了
//mid = right;//这里left和right的值是一样的
mid = left;//这个时候mid下标对应的值是L和R相遇的值
Swap(&a[mid], &a[key]);//将left或者right（也就是left和right相遇的地点）与key进行交换
return mid;//这个时候mid下标对应的值就是key了
}
单趟排序完之后，key值的位置就是确定的，那么[left,key-1]和 [key+1,right]两个区间内数据的位置没有确定，我们和二叉树一样使用递归的方法，对左右区间就行key值确定，直到找不到区间（比如下面的【2，1】就是不存在区间）就停止该次单趟排序
优化1
key取值的缺陷
key如果是中位数，那么就是左区间小，右区间大。但是，如果数据是有序或者接近有序的，那么key就是最大值、最小值或者接近最大值、接近最小值，这种情况下直接使用最左边或者最右边的数据key效率都很低。这个时候就要就行优化了，方法就是——
三数取中
三数取中
从第一个值，中间值和最后一个值中，选出三个数据的中间值与key进行交换
这里三个数找中间值没有其他办法，只能两两比较
int GetMid(int* a, int left, int right)//三数取中
{//这里快排的层数是logN层，不会产生栈溢出
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
{
if (a[mid] < a[right])
return mid;
else if (a[left] > a[right])
return left;
else
return right;
}
}
那么hoare单趟排序法也要加入一些代码
int PartSort1(int* a, int left, int right)//hoare第一种方法单趟的排序
{
int mid = GetMid(a, left, right);//接收三数取中的结果
Swap(&a[mid], &a[left]);//将两个三数取中的值与最左值就行交换
int key = left;//如果key是最左值，那么就先动right;如果key是最右值，那么先动left
while (left < right)
{
while (left < right && a[right] >= a[key])//确定key为左值，那么R先走
//这里需要要left<right——因为while不是一个判断语句，如果特殊情况：
//1、a的所有值都比key要大，那么right会一直减减，直到越界成为负数
//2、right减减不会停下来，会与left错过了
//所以left要小于right
//如果左值或者右值等于key就继续找
{
--right;
}
while (left < right && a[left] <= a[key])//L后走
{
++left;
}
if (left < right)//如果R和L没有相遇
Swap(&a[left], &a[right]);//把左边大于key的值与右边小于key的值进行交换
}
//到这里left和right已经相遇了
//mid = right;//这里left和right的值是一样的
mid = left;//这个时候mid下标对应的值是L和R相遇的值
Swap(&a[mid], &a[key]);//将left或者right（也就是left和right相遇的地点）与key进行交换
return mid;//这个时候mid下标对应的值就是key了
}
优化2
小区间优化
当我们一次次递归确定key值后，如果左右区间都只剩下8个、9个或者10个值的时候再调用递归就有些浪费了，这个时候我们直接使用插入排序更好
if (right - left <= 8)//小区间优化
{
//a+left是插入排序的起始地址，right-left+1是数据个数
InsertSort(a + left, right - left + 1);//插入排序（数据少）
}
挖坑法
int PartSort2(int* a, int left, int right)//第二种方法单趟的排序
{
int mid = GetMid(a, left, right);
Swap(&a[mid], &a[left]);
int keyi = a[left];//将数组第一个数据赋值给keyi
int hole = left;//hole也就是坑初始为第一个位置
while (left < right)
{
while (left < right && a[right] >= keyi)
--right;
a[hole] = a[right];//右边先走，找到小于keyi的数据就将该位置变成坑
hole = right;
while (left < right && a[left] <= keyi)
++left;
a[hole] = a[left];//左边后走，找到大于keyi的数据就将该位置变成坑
hole = left;
}
a[hole] = keyi;
//最后把坑位置的数据与keyi交换，那么hole数据的位置就是正确的，且左边数据都小于hole位置数据，右边数据都大于hole位置数据
return hole;
}
前后指针法
cur先走，找比key小的值，找到之后++prev，看看prev等不等于cur，等于cur继续走，不等于就交换cur和prev的值，cur再继续走
int PartSort3(int* a, int left, int right)//第三方法单趟的排序
{
int mid = GetMid(a, left, right);
Swap(&a[mid], &a[left]);
int key = left;//key是第一个元素位置
int cur = left + 1;//cur在前面找比a【key】小的数据
int prev = left;//prev在后面
while (cur <= right)//cur到right就走到最后了
{
//if (a[cur] < a[key] && ++prev != cur)
// Swap(&a[cur], &a[prev]);
if (a[cur] < a[key])
{
++prev;
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[key], &a[prev]);
return prev;
}
快速排序（非递归）
这里要使用到数据结构——栈
在栈里面存放区间，进行确定key值
void QuickSortNonR(int* a, int left, int right)//快排（非递归）
{
ST p;
StackInit(&p);
StackPush(&p,left);//先入栈最左边（0）
StackPush(&p, right);//再入栈最右边（9）
while (!StackEmpty(&p))
{
int right2 = StackTop(&p);//取到栈顶数据（9）
StackPop(&p);//弹出栈顶数据
int left2 = StackTop(&p);//再次取到栈顶数据（0）
StackPop(&p);//再弹出
//if (left2 >= right2)//如果只有一个值或者不存在了就回到前面继续
// continue;
int key = PartSort3(a, left2, right2);//找到key值
//这个时候栈里面就是一个区间了[left2,key-1] key [key+1,right2]
if (key + 1 < right2)//大于等于就是只有1个或者没有中间数据，这个时候不用入栈
{
StackPush(&p, key + 1);//先入栈key右边数据
StackPush(&p, right2);
}
if (left2 < right2 - 1)//小于表示有两个或者两个以上的值
{
StackPush(&p, left2);//再入栈key左边数据
StackPush(&p, key - 1);
}
}
StackDestory(&p);
}
快速排序的特性总结：
1 . 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(logN)
4. 稳定性：不稳定
测试排序性能对比
这里的代码可以测试出每一个排序方法对相同数据进行排序的时间
每一个end-begin的结果就是该排序所花费的时间
void TestOP()
{
srand(time(0));
const int N = 10000000;
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);
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];
}
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();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
//MergeSort(a6, N);
int end6 = clock();
int begin7 = clock();
//BubbleSort(a7, N);
int end7 = 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", end7 - begin7);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
全部代码
sort.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void PrintSort(int* a, int n);//打印
void InsertSort(int* a, int n);//插入排序
void ShellSort(int* a, int n);//希尔排序
void HeapSort(int* a, int n);//堆排序
void SelectSort(int* a, int n);//选择排序
void BubbleSort(int* a, int n);//冒泡排序
void QuickSort(int* a, int begin, int end);//快排（递归）
void QuickSortNonR(int* a, int left, int right);//快排（非递归）
sort.c
#define _CRT_SECURE_NO_WARNINGS
#include"Sort.h"
#include"Stack.h"
void PrintSort(int* a, int n)//打印
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void InsertSort(int* a, int n)//插入排序
{//在[0，end]插入end+1 [0,end+1]有序
//时间复杂度O（N）--顺序有序
//时间复杂度O（N^2）--逆序
for (int i = 0; i < n - 1; ++i)//i下标最大为倒数第二个元素的下标
{
int end = i;//内部最好不改变i的值，用end进行操作
int tmp = a[end + 1];//tmp是i的下一个元素
while (end >= 0)//等于0时就是第一个数据
{
if (tmp < a[end])//如果end后一个数据小于end
{
a[end + 1] = a[end];//把end的数据挪动到后一个位置
--end;//end自减1
}
else
break;//如果end后一个数据大于end数据，那么就跳出循环
}
a[end + 1] = tmp;//不管是插入成功了end+1数据，还是end自减为负数了，都执行该代码
}
}
void ShellSort(int* a, int n)//希尔排序
{
//gap > 1就是预排序
//gap == 1就是直接插入排序
int gap = n;
while (gap > 1)//gap大于1表示预排序没有完成
{
//这里gap要保证最后一次的值计算之后等于1进行直接插入排序
gap = gap / 3 + 1;//当gap走到这里除等2，或者除3加1 等于1 表示gap已经预排序完成了，可以直接进行插入排序了
//gap /= 2;//除2预排序次数要多一些
for (int j = 0; j < gap; ++j)//多少次预排序
{
for (int i = j; i < n - gap; i += gap)//一次希尔预排序
//for (int i = 0; i < n - gap; ++i)//让两个for循环变成一个for循环，这里多组预排序共同进行
{
int end = i;//不能在循环内部直接改变i的值
int tmp = a[end + gap];//记录end的后一个数据
while (end >= 0)//如果end<0表示所有数据都比tmp大
{
if (tmp < a[end])//如果tmp小于end
{
a[end + gap] = a[end];//把end数据赋值给end后一个位置，这里end原来后面的数据是tmp，覆盖不影响tmp
end -= gap;//end一次减gap个位置
}
else
break;//如果tmp大于end跳出循环
}
a[end + gap] = tmp;//不管是所有数据都小于tmp还是tmp插入成功了，都把tmp的值给到end+gap的位置都是正确的
}
}
}
}
void Swap(int* n, int* m)//传值调用不会交换外面的两个值，所以说用传址调用
{
int tmp = *n;
*n = *m;
*m = tmp;
}
void Justdown(int* a, int size, int parent)//向下转换
{
int midchild = parent * 2 + 1;//我们假设左节点为两个节点中的小节点，那么左节点的下标就是父节点下标乘以2加上1
while (midchild < size)//这里不要用父节点判断是否向下调整完毕，如果没有下面的break会判断失误，出不了循环
{
//if (midchild + 1 < size && a[midchild + 1] > a[midchild])//求取大堆最上面的节点。大于就是升序，上面是最小值
if (midchild + 1 < size && a[midchild + 1] < a[midchild])//小节点的坐标加1要小于size，不然就相当于越界了
//如果右节点的值小于左节点，那么midchild下标加1，得到两个节点中的小节点
{
midchild++;
}
//if (a[midchild] > a[parent])//求取大堆最上面的节点。大于就是升序，上面是最小值
if (a[midchild] < a[parent])
//如果小节点的值小于父节点的值就进去开始向下调整
{
Swap(&a[midchild], &a[parent]); //交换父节点与小节点的值
parent = midchild;//把小节点的下标赋给父节点
midchild = parent * 2 + 1;//此时新的小节点下标就为父节点乘以2加上1
}
else
{
break;//如果小节点的值大于等于父节点就不用进行操作（这是针对小根堆的注释）
}
}
}
void HeapSort(int* a, int n)//堆排序
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i)//创建堆
{
Justdown(a, n, i);//向下调整
}
int i = 1;
while (i < n)
{
Swap(&a[0], &a[n - i]);//小堆就是降序，大堆就是升序
Justdown(a, n - i, 0);
++i;
}
}
void SelectSort(int* a, int n)//选择排序
{//不管数据顺序怎么样，选择排序时间复杂度永远都是O(N^2)
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
if (a[i] > a[j])
Swap(&a[i], &a[j]);
}
}
}
void BubbleSort(int* a, int n)//冒泡排序
{
for (int i = 0; i < n - 1; i++)//n个数据要排序n-1躺
{
int flag = 0;
for (int j = 0; j < n - i - 1; j++)//每一趟排一个数据的过程
{
if (a[j + 1] < a[j])//如果j后一个数据小于j就交换
{
Swap(&a[j], &a[j + 1]);
flag = 1;//如果flag改变就表示数据不是有序的，就要继续进行排序
}
}
if (flag == 0)//如果flag没有改变，就表示数据有序，不用排序直接退出
break;
}
}
int GetMid(int* a, int left, int right)//三数取中
{//这里快排的层数是logN层，不会产生栈溢出
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
{
if (a[mid] < a[right])
return mid;
else if (a[left] > a[right])
return left;
else
return right;
}
}
int PartSort1(int* a, int left, int right)//hoare第一种方法单趟的排序
{
int mid = GetMid(a, left, right);//接收三数取中的结果
Swap(&a[mid], &a[left]);//将两个三数取中的值与最左值就行交换
int key = left;//如果key是最左值，那么就先动right;如果key是最右值，那么先动left
while (left < right)
{
while (left < right && a[right] >= a[key])//确定key为左值，那么R先走
//这里需要要left<right——因为while不是一个判断语句，如果特殊情况：
//1、a的所有值都比key要大，那么right会一直减减，直到越界成为负数
//2、right减减不会停下来，会与left错过了
//所以left要小于right
//如果左值或者右值等于key就继续找
{
--right;
}
while (left < right && a[left] <= a[key])//L后走
{
++left;
}
if (left < right)//如果R和L没有相遇
Swap(&a[left], &a[right]);//把左边大于key的值与右边小于key的值进行交换
}
//到这里left和right已经相遇了
//mid = right;//这里left和right的值是一样的
mid = left;//这个时候mid下标对应的值是L和R相遇的值
Swap(&a[mid], &a[key]);//将left或者right（也就是left和right相遇的地点）与key进行交换
return mid;//这个时候mid下标对应的值就是key了
}
int PartSort2(int* a, int left, int right)//第二种方法单趟的排序
{
int mid = GetMid(a, left, right);
Swap(&a[mid], &a[left]);
int keyi = a[left];//将数组第一个数据赋值给keyi
int hole = left;//hole也就是坑初始为第一个位置
while (left < right)
{
while (left < right && a[right] >= keyi)
--right;
a[hole] = a[right];//右边先走，找到小于keyi的数据就将该位置变成坑
hole = right;
while (left < right && a[left] <= keyi)
++left;
a[hole] = a[left];//左边后走，找到大于keyi的数据就将该位置变成坑
hole = left;
}
a[hole] = keyi;
//最后把坑位置的数据与keyi交换，那么hole数据的位置就是正确的，且左边数据都小于hole位置数据，右边数据都大于hole位置数据
return hole;
}
int PartSort3(int* a, int left, int right)//第三方法单趟的排序
{
int mid = GetMid(a, left, right);
Swap(&a[mid], &a[left]);
int key = left;//key是第一个元素位置
int cur = left + 1;//cur在前面找比a【key】小的数据
int prev = left;//prev在后面
while (cur <= right)//cur到right就走到最后了
{
//if (a[cur] < a[key] && ++prev != cur)
// Swap(&a[cur], &a[prev]);
if (a[cur] < a[key])
{
++prev;
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[key], &a[prev]);
return prev;
}
void QuickSort(int* a, int left, int right)//快排（递归）
{
if (left >= right)//如果只有一个值（相等）或者不存在了（left>right）就返回
return;
if (right - left <= 8)//小区间优化
{
//a+left是插入排序的起始地址，right-left+1是数据个数
InsertSort(a + left, right - left + 1);//插入排序（数据少）
}
//单趟排序的价值：
//1、key的值所在位置就是正确的位置
//2、key分开了区间，key左边的数据都是比key小的，右边的数据都是比key大的
//[left,key-1] key [key+1,right] 这里key的位置是确定了，但是左右区间数据没有确定，所以用递归的方法来处理
//int key = PartSort1(a, left, right);//第一种方法
//int key = PartSort2(a, left, right);//挖坑法
int key = PartSort3(a, left, right);//前后指针法
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
void QuickSortNonR(int* a, int left, int right)//快排（非递归）
{
ST p;
StackInit(&p);
StackPush(&p,left);//先入栈最左边（0）
StackPush(&p, right);//再入栈最右边（9）
while (!StackEmpty(&p))
{
int right2 = StackTop(&p);//取到栈顶数据（9）
StackPop(&p);//弹出栈顶数据
int left2 = StackTop(&p);//再次取到栈顶数据（0）
StackPop(&p);//再弹出
//if (left2 >= right2)//如果只有一个值或者不存在了就回到前面继续
// continue;
int key = PartSort3(a, left2, right2);//找到key值
//这个时候栈里面就是一个区间了[left2,key-1] key [key+1,right2]
if (key + 1 < right2)//大于等于就是只有1个或者没有中间数据，这个时候不用入栈
{
StackPush(&p, key + 1);//先入栈key右边数据
StackPush(&p, right2);
}
if (left2 < right2 - 1)//小于表示有两个或者两个以上的值
{
StackPush(&p, left2);//再入栈key左边数据
StackPush(&p, key - 1);
}
}
StackDestory(&p);
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include"Sort.h"
void TestInsertSort()//插入排序测试
{
int a[10] = { 53,26,46,76,85,90,64,34,50,33 };
int n = sizeof(a) / sizeof(a[0]);
InsertSort(a, n);//插入排序
PrintSort(a, n);
}
void TestShellSort()//希尔排序测试
{
int a[10] = { 53,26,46,76,85,90,64,34,50,33 };
int n = sizeof(a) / sizeof(a[0]);
ShellSort(a, n);//希尔排序
PrintSort(a, n);
}
void TestHeapSort()//堆排序测试
{
int a[10] = { 53,26,46,76,85,90,64,34,50,33 };
int n = sizeof(a) / sizeof(a[0]);
HeapSort(a,n);//堆排序
PrintSort(a, n);
}
void TestSelectSort()//选择排序测试
{
int a[10] = { 53,26,46,76,85,90,64,34,50,33 };
int n = sizeof(a) / sizeof(a[0]);
SelectSort(a,n);//选择排序
PrintSort(a, n);
}
void TestBubbleSort()//冒泡排序测试
{
int a[10] = { 53,26,46,76,85,90,64,34,50,33 };
int n = sizeof(a) / sizeof(a[0]);
BubbleSort(a,n);//冒泡排序
PrintSort(a, n);
}
void TestQuickSort()//快排测试
{
int a[10] = { 53,26,46,76,85,90,64,34,50,33 };
int n = sizeof(a) / sizeof(a[0]);
//给出区间
//QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);//快排
QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);//快排(非递归)
PrintSort(a, n);
}
void TestOP()
{
srand(time(0));
const int N = 10000000;
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);
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];
}
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();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
//MergeSort(a6, N);
int end6 = clock();
int begin7 = clock();
//BubbleSort(a7, N);
int end7 = 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", end7 - begin7);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
TestInsertSort();
TestShellSort();
TestHeapSort();
TestSelectSort();
TestBubbleSort();
TestQuickSort();
//TestOP();
return 0;
}
本期内容就到这里了，剩下的归并排序等下一期再发布，希望大家一键三连！