【数据结构】八大排序算法详解
1.排序的概念及其运用
1.1 排序的概念
- 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
- 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 内部排序：数据元素全部放在内存中的排序。
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序运用
1.3 常见的排序算法
2.排序算法之一：直接插入排序
2.1 基本思想
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
实际中我们玩扑克牌时，就用了插入排序的思想
2.2 排序原理
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
动图：https://pic3.zhimg.com/v2-91b76e8e4dab9b0cad9a017d7dd431e2_b.webp
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
2.3 实现思路
我们假设[0,end]是有序的，那么我们需要把end+1的值插入到有序数组中去，然后end++
我们以升序为例：
- 定义一个end，tmp存a[end+1]的值
- 从end的位置开始判断tmp大于还是小于end的值，如果tmp<a[end]，则将a[end]的值向后移动，end--接着对比前一个，否则跳出循环
- 如果end走到-1，那就将tmp存到a[end+]即a[0]；否则就将tmp存到a[end]的后面，即a[end+1]=tmp
- 我们用for循环控制多趟循环，从0开始，一直比较到n-1
直接插入排序的时间复杂度为O(N^2)
2.4 实现代码
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = tmp;
}
}3.排序算法之二：冒泡排序
3.1 基本思想
冒泡排序是交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
- 第一趟：将最大的值排到最后
- 第二趟：将次大的值排到倒二
- ......
- 第n-1趟：将最小的排到第一
冒泡排序动图：https://pic4.zhimg.com/v2-33a947c71ad62b254cab62e5364d2813_b.webp
由于冒泡排序的时候，大的沉地，小的浮上来，所以得名冒泡排序
3.2 冒泡排序的特性
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
3.3 实现代码
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
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]);
}
}
/*for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j+1])
Swap(&a[j], &a[j+1]);
}
}*/
}4.排序算法之三：希尔排序
4.1 基本思想
希尔排序法又称缩小增量法
希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序
4.2 希尔排序的特性
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序；当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
- 稳定性：不稳定
4.3 实现代码
希尔排序分为预排序和直接插入两个阶段
4.3.1 预排序-单组排
4.3.2 预排序-多组并排
gap==3；
- i==0，排①
- i==1，排②
- i==2，排③
4.3.3 gap取值
关于gap的取值：
- gap越大，大的值更快调到后面，小的值可以更快调到前面，但是gap越大，越不接近有序
- gap越小，调的越慢，但是越接近有序，gap==1，直接插入排序
int gap=n；gap随着n变化
- while(gap>1) { gap/=2; ... } //不断变小
- while(gap>1) { gap=gap/3+1; ... }
gap/=2和gap=gap/3+1都是为了保证最后一次gap==1
4.3.4 代码示例
//void ShellSort(int* a, int n)
//{
// int gap = 3;
// while (gap > 1)
// {
// gap = gap / 3 + 1;
// for (int j = 0; j < gap; j++)
// {
// for (int i = j; i < n - gap; i += gap)
// {
// int end = i;
// int tmp = a[end + gap];
// while (end >= 0)
// {
// if (tmp < a[end])
// {
// a[end + gap] = a[end];
// end -= gap;
// }
// else
// break;
// }
// a[end + gap] = tmp;
// }
// }
// }
//}
void ShellSort(int* a, int n)
{
int gap = 3;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = tmp;
}
}
}5.排序算法之四：直接选择排序
5.1 基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
- 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
- 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
直接选择排序动图：https://pic1.zhimg.com/v2-1c7e20f306ddc02eb4e3a50fa7817ff4_b.webp
5.3 直接选择排序的特性
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
5.4 实现思路
我们在这个思想上再优化一步，一次遍历选出两个数，最大的maxi和最小的mini
遍历n/2遍数组，找到最小的值和左边换，找到最大的值和右边换，每遍历一次范围就缩小2
如果遍历之后最大的还是在begin位置，当swap一次之后，maxi已经换到了mini的位置，需要更新 一下maxi的位置
5.5 实现代码
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[mini])
mini = i;
if (a[i] > a[maxi])
maxi = i;
}
Swap(&a[begin], &a[mini]);
if (maxi == begin)
maxi = mini;
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}6.排序算法之五：堆排序
6.1 基本思想
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据
需要注意的是排升序要建大堆，排降序建小堆
堆排序的动图演示：
6.2 堆排序的特性
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
6.3 堆排序的实现
为什么我们要选择堆排序呢
它的效率相比于冒泡排序要高出不少
6.3.1 交换函数
6.3.2 向上调整
大堆向上调整，找大的往根节点排，找小的往叶子节点排
所以对比孩子节点和父亲节点，如果孩子节点大于父亲节点，则交换两个节点，然后child走到parent，parent走到（child-1）/ 2
6.3.3 向下调整
这就是堆的删除思路，根节点是最大的值，根节点和最后一个叶子节点交换，size--，然后继续大堆排序
6.3.4 建堆
建大堆，从数组第一个值 a[0] 开始插入建堆
6.4.5 选数排序
就是堆的访问，用while循环控制
6.4.6 实现代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void Swap(int* p1, int* p2);
void AdjustUp(int* a, int child);
void AdjustDown(int* a, int size, int parent);
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
void AdjustDown(int* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if ((child + 1) < size && a[child + 1] > a[child])
++child;
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int* a, int n)
{
//建堆
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}
//排序
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
int main()
{
int a[] = { 4,6,2,1,5,8,2,9 };
int sz = sizeof(a) / sizeof(a[0]);
HeapSort(a, sz);
for (int i = 0; i < sz; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}7.排序算法之六：快速排序
7.1 快速排序（递归）
7.1.1 基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法
其基本思想为：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
// 假设按照升序对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左右区间的不同，整体快排的思想是递归
7.1.2 hoare方法
https://img-blog.csdnimg.cn/07ddcfdc56874b2a9d12f585534ac87e.gif#pic_center
7.1.1.1 图示
定义left和right来找大和找小
right先走找大，left再走找小，找到交换
继续找大找小
相遇停下来，和key交换
7.1.1.2 为什么相遇位置一定比key小
这里我们有一个问题：为什么相遇位置一定比key小？
因为右边先走
相遇有两种情况：
- right遇left -> left先走，right没有遇到比key小的，一直走，直到遇到left停下来，left存的是比key小的值
- left遇right -> right先走，left没有遇到比key大的，一直走，直到遇到right停下来，right存的是比key大的值
- 所以我们得出一个结论，左边做key，右边先走；右边做key，左边先走
如果左边有序，右边也有序，整体就有序了
那么如何让左右有序呢？
类似二叉树，递归左树和右树
第一遍排序后的left和right的范围是：[begin,keyi-1]，keyi，[keyi+1,end]
然后继续递归，直到这个区间只有一个值或者不存在
7.1.1.3 代码示例
//hoare方法
int PartSort1(int*a,int begin,int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int left = begin, right = end;
int keyi = begin;
while (left < right)
{
//右边找小
while (left < right && a[right] >= a[keyi])
{
--right;
}
//左边找大
while (left < right && a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
return keyi;
}7.1.3 挖坑法
https://img-blog.csdnimg.cn/c2dde0e21f32461fb43db524559ca36d.gif#pic_center
7.1.3.1 图示
right找小，left找大，right先走，找到小和坑位交换，然后left走，left找到大之后和坑位交换，交替进行直到相遇
他们一定会相遇到坑的位置
相遇之后将key的值放到坑位中，这时候key左边就是比key小的，key右边就是比key大的
7.1.3.2 代码示例
我们写一个挖坑法的函数来排keyi左右的数据
先用三数取中方法得到keyi，定义一个key保存keyi的值，定义一个坑位holei先放到begin
- 右边找小，填到左边的坑里，右边成为新的坑
- 左边找大，填到右边的坑里，左边成为新的坑
- 相遇后将key放到坑里，返回坑的下标
//挖坑法
int PartSort2(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int key = a[begin];
int holei = begin;
while (begin < end)
{
//右边找小
while (begin < end && a[end] <= key)
--end;
a[holei] = a[end];
holei = end;
//左边找大
while (begin < end && a[begin] >= key)
++begin;
a[holei] = a[begin];
holei = begin;
}//相遇
a[holei] = key;
return holei;
}7.1.4 前后指针法
https://img-blog.csdnimg.cn/8baec430614e47dfa382926553830c14.gif#pic_center
7.1.4.1图示
prev要不就是紧跟cur，要不prev和cur之间就是比key大的值
7.1.4.2 代码示例
//前后指针法
int PartSort3(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
//if (a[cur] < a[keyi])
//{
// ++prev;
// Swap(&a[prev], &a[cur]);
// ++cur;
//}
//else
// ++cur;
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}7.1.5 快速排序优化
- 三数取中法选key
- 递归到小的子区间时，可以考虑使用插入排序
7.1.5.1 三数取中方法
这里我们的key默认取的是第一个数，但是这种情况有个弊端，不能保证key一定是那个中间值，可能是最小的，也可能是最大的
但是理想情况下，key选中间值是效率最高的，每次都是二分
这里就有一个方法能很好的解决这个问题：三数取中
我们写一个取中函数，将中间值与begin交换，还是将key给到begin
int GetMidi(int* a, int begin, int end)
{
int midi = (begin + end) / 2;
if (a[begin] < a[midi])
{
if (a[midi] < a[end])
return midi;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[midi] > a[end])
return midi;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}三数取中可以排除掉最坏的情况，相对而言可以提高效率
7.1.5.2 小区间优化
如果是满二叉树，最后一层占50%的节点，倒数第二层占25%，倒数第三层占12.5%
假设我们要对这五个数排序，就需要调用六次递归，这代价是非常大的
我们可以使用插入排序，插入排序对局部的适应性是很好的，所以我们在这个区间缩小的一定范围的时候就可以使用插入排序
一般选择最后三到四层，因为最后三层就占据了将就90%的递归，将最后三层的递归消除是能够明显提高效率的
剩下的区间不一定是从0开始的，也有可能是后半段，所以这里插入排序从begin开始
7.1.6 总代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = tmp;
}
}
int GetMidi(int* a, int begin, int end)
{
int midi = (begin + end) / 2;
if (a[begin] < a[midi])
{
if (a[midi] < a[end])
return midi;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[midi] > a[end])
return midi;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}
//hoare方法
int PartSort1(int*a,int begin,int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int left = begin, right = end;
int keyi = begin;
while (left < right)
{
//右边找小
while (left < right && a[right] >= a[keyi])
{
--right;
}
//左边找大
while (left < right && a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
return keyi;
}
//挖坑法
int PartSort2(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int key = a[begin];
int holei = begin;
while (begin < end)
{
//右边找小
while (begin < end && a[end] <= key)
--end;
a[holei] = a[end];
holei = end;
//左边找大
while (begin < end && a[begin] >= key)
++begin;
a[holei] = a[begin];
holei = begin;
}//相遇
a[holei] = key;
return holei;
}
//前后指针法
int PartSort3(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
//if (a[cur] < a[keyi])
//{
// ++prev;
// Swap(&a[prev], &a[cur]);
// ++cur;
//}
//else
// ++cur;
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
//快排
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
if (end - begin + 1 <= 10)
InsertSort(a + begin, end - begin + 1);
else
{
//hoare法
//int keyi = PratSort1(a, begin, end);
//int keyi = PartSort2(a, begin, end);
int keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}
int main()
{
int a[] = { 9,8,7,6,6,5,4,3,2,1,10,14,12,11,15 };
int n = sizeof(a) / sizeof(a[0]);
QuickSort(a, 0, n - 1);
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}7.2 快速排序（非递归）
快速排序是非常适合使用递归的，但是同时我们也要掌握非递归的算法
因为操作系统的栈空间很小，如果递归的深度太深，容易造成栈溢出
递归改非递归一般有两种改法：
- 改循环
- 借助栈（数据结构）
7.2.1图示算法
不是递归，我们模拟递归的过程
7.2.2 代码示例
创建一个栈s，先入end，再入begin，先出左再出右
然后找这个区间的keyi，找到之后左区间就是[left,keyi-1]，右区间就是[keyi+1,right]
如果区间不止一个值，那就继续入栈，单趟排序，入栈的顺序应与前面保持一致
7.2.2.1 stack
stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
int* a;
int top;//标识栈顶位置
int capacity;
}ST;
//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//返回栈顶元素
STDataType STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的元素个数
int STSize(ST* pst);stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
//初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->capacity = 0;
pst->top = 0;
}
//销毁
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType * )realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
//出栈
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
//返回栈顶元素
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst -> a[pst->top - 1];
}
//判空
bool STEmpty(ST* pst)
{
assert(pst);
/*if (pst->top == 0)
{
return true;
}
else
{
return false;
}*/
return pst->top == 0;
}
//栈的元素个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}7.2.2.2 QuickSortNonR
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = tmp;
}
}
int GetMidi(int* a, int begin, int end)
{
int midi = (begin + end) / 2;
if (a[begin] < a[midi])
{
if (a[midi] < a[end])
return midi;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[midi] > a[end])
return midi;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}
//前后指针法
int PartSort3(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
//if (a[cur] < a[keyi])
//{
// ++prev;
// Swap(&a[prev], &a[cur]);
// ++cur;
//}
//else
// ++cur;
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
void QuickSortNonR(int* a, int begin, int end)
{
ST s;
STInit(&s);
STPush(&s, end);
STPush(&s, begin);
while (!STEmpty(&s))
{
int left = STTop(&s);
STPop(&s);
int right = STTop(&s);
STPop(&s);
int keyi = PartSort3(a, left, right);
if (left < keyi - 1)
{
STPush(&s, keyi - 1);
STPush(&s, left);
}
if (keyi + 1 < right)
{
STPush(&s, right);
STPush(&s, keyi + 1);
}
}
STDestroy(&s);
}递归相当于把这些数据存到栈帧里边，而非递归是将核心区间存存到数据结构栈里面
7.3 快速排序的特性总结
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
8.排序算法之七：归并排序
8.1 归并排序（递归）
8.1.1 基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
8.1.2 核心步骤
归并排序动图：https://pic3.zhimg.com/v2-cdda3f11c6efbc01577f5c29a9066772_b.webp
先分割，再归并
数组的左边有序，右边也有序，那么怎么数组整体有序呢：取小的尾插到新数组
8.1.3 实现代码
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, end1 = mid;//左区间
int begin2 = mid + 1, 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 fail");
return;
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}8.1.4 归并排序的特性
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
8.2 归并排序（非递归）
8.2.1.非递归实现思路
我们之前学习了递归实现的归并排序，是分治的思想，即先分解，再归并
这篇文章我们讲一下非递归的实现
非递归实现的思路是模拟递归的过程，在递归过程中，我们找key将数组分成左右数组，然后递归子数组，知道该数组剩一个元素，然后归并：两个两元素数组归并为四元素数组，两个四元素数字归并为八元素数组
而非递归的实现不需要递归子数组进行分解，我们可以将n个元素的数组看作n个数组，直接进行下面的合并
我们先设gap为1，表示先控制一个元素的数组进行归并，malloc一个临时数组tmp，归并到tmp数组；一整趟归并结束后gap*=2，同时将归并完成的数组拷贝到原数组，继续控制两元素的数组进行归并，直到gap>=n则停止归并，此时原数组已经有序了
8.2.2 图示归并
归并的过程和递归方式的归并排序一样
每次归并的时候，两个数组中找小的排到前面，排空一个数组之后将另外一个数组尾插到后面即可
8.2.3 实现代码
函数代码和测试代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
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, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
int j = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
tmp[j++] = a[begin1++];
else
tmp[j++] = a[begin2++];
} //[begin1,end1][begin2,end2]归并->tmp[]
while (begin1 <= end1)
tmp[j++] = a[begin1++];
while (begin2 <= end2)
tmp[j++] = a[begin2++];
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}
int main()
{
int i = 0;
int a[] = { 10,10,2,5,7,9,3,4,5,4,1,0 };
int n = sizeof(a) / sizeof(a[0]);
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
MergeSortNonR(a, n);
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}9.排序算法之八：计数排序
9.1 基本思想
计数排序，顾名思义就是计算数据的个数
计数排序又称非比较排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
计数排序的特性总结：
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
9.2 实现思路
首先统计每个数据出现了多少次
假设有这么一个数组，下面的数组就是统计数据个数的
如果1出现，则对1位置++，如果3出现，则对3位置++，即
这里的代码核心稍微比较抽象，是在统计a数组中数据个数
接下来的操作是这样，对比count数组，0出现了0次，那就是0个0，1出现了3次，那就是3个1，其余同理，图示如下：
对比下来效率是非常高的，遍历一遍数组
同样，他也有局限性：
- 不适合分散的数据，更适合集中的数据
- 不适合浮点数、字符串、结构体数据排序，只适合整数
9.3 实现代码
先求最大值max和最小值min，然后遍历原数组统计次数，最后排序
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
printf("calloc fail!");
return;
}
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
int i = 0;
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
}
int main()
{
int a[] = { 10,11,10,11,15,1,2,3,5,4,2,1,0 };
int n = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
CountSort(a, n);
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}腾讯云开发者
