八大排序详解
一、前言
本章主要讲解：
八大排序的基本知识及其实现
注：这里的八大排序指直接插入，希尔，选择，堆排，冒泡，快排，归并，计数
- 八大排序汇总图：
二、排序概念及应用
1、概念
- 排序：
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
- 稳定性：
假设在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的(记录的相对次序保持不变)；否则称为不稳定的
- 内部排序：
数据元素全部放在内存中的排序
- 外部排序：
数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序
2、排序应用
- 示例：搜索电影时
三、排序算法接口展示
// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
// 计数排序
void CountSort(int* a, int n)
四、插入排序
1、直接插入排序
直接插入排序是一种简单的插入排序法
- 基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
- 动图展示：
- 实现代码：
//直接插入排序
void InsertSort(int* a, int n)
{
assert(a);//传入数组不为空指针
int i;
for (i = 0; i < n - 1; i++)
//注意：最后一个要插入数据的下标为n-1，此次插入有序数列的end下标为n-2
{
int end = i;//标记当前有序数列的最后一个位置下标
int x = a[end + 1];//要插入的数据为有序数列的后一个位置
while (end >= 0)//进行当前趟次的插入排列
{
//升序
if (a[end] >x)//有序数列的数据比插入数据大，则往后挪动
{
a[end + 1] = a[end];
end--;//向前找，进行排列数据
}
else//遇到不大于要插入数据，则不再往前找
{
break;
}
}
a[end + 1] = x;//将要插入数据插入到不大于该数据的后一个位置
}
}
- 直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
2、希尔排序
- 基本思想：
对于直接插入排序在面对一些特殊情况时，效率非常低（例如：将降序排成升序），而对于已经接近排好的序列，效率非常高
希尔排序在直接排序之前，进行预排列，将某些极端数据更快的排列到数列前面，构成一个接近排列好的序列，最后再进行一次直接插入排序
预排列的原理也是插入排列，只不过这里的将数组分成了gap组，分别对每一个小组进行插入排序
如下动图：对于升序，当gap从5 – 2 – 1的过程中，排在后面的数值小的数能更快排到前面，当gap为1的时候实际上就是进行了一次插入排序
- 动图展示：
// 希尔排序
void ShellSort(int* a, int n)
{
//多组预排（一锅炖）+插排
int gap = n;
while (gap > 1)
{
gap /= 2;//保证最后一次分组gap==1,即最后一次为直接插入排序
//gap = gap / 3 + 1;//也可以写成这样，除3预排的效率相比于除2的好点
for (int i = 0; i < n - gap; i++)
{
int end = i;
int x = a[end + gap];
while (end >= 0)
{
if (a[end] > x)
{
a[end + gap] = a[end];
end-=gap;
}
else
break;
}
a[end + gap] = x;
}
}
}
- 希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，一般来说为O(n^1.3)
- 稳定性：不稳定
五、选择排序
1、直接选择排序
- 基本思想：
每一次遍历待排序的数据元素从中选出最小（或最大）的一个元素，存放在序列的起始（或者末尾）位置，直到全部待排序的数据元素排完
- 动图展示：
- 实现代码：
// 选择排序
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;//记录下标
while (begin < end)
{
int mini = begin;
for (int i = begin; i <= end; i++)
{
//遍历找到最小数据并记录下标
if (a[i] < a[mini])
mini = i;
}
Swap(&a[begin], &a[mini]);//交换
begin++;//缩小范围
}
}
这里我们还可以对直接选择排序做一个优化：每次遍历待排序数据找出最大和最小的数据，分别排列到序列起始和末尾
- 优化代码：
// 选择排序（优化版）
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int maxi = begin, mini = begin;
for (int i = begin; i <= end; i++)//遍历找到最大最小的下标
{
if (a[i] > a[maxi])
maxi = i;
if (a[i] < a[mini])
mini = i;
}
Swap(&a[begin], &a[mini]);//交换
//当最初始位置begin与对大数据下标重合的情况
if (begin == maxi)//修正下标位置
maxi = mini;
Swap(&a[end], &a[maxi]);
begin++;//缩小范围
end--;
}
}
- 直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
2、堆排序
堆排序是指利用堆（数据结构）进行选择数据的一种排序算法
- 基本思想:
- 原则：
先将原数组建成堆，需要注意的是排升序要建大堆，排降序建小堆
注：以大堆为例- 建堆：
一个根节点与子节点数据如果不符合大堆结构，那么则对根节点数据进行向下调整，而向下调整的前提是左右子树也符合大堆结构,所以从堆尾数据的根节点位置开始向下调整建大堆- 排序：
大堆堆顶数据一定是待排数据中最大的，将堆顶数据与堆尾数据交换,交换后将除堆尾数据看成新堆，对现堆顶数据进行向下调整成大堆,以此循环直至排列完毕- 向下调整：
找到子节点中的较大数据节点比较，如果父节点数据比大子节点小则交换，直到不符合则停止向下交换，此时再次构成了一个大堆结构
具体堆排序详解：堆排序超详解
- 动图展示：大堆排序
- 实现代码：
void Adjustdown(int* a, int n,int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
//找到数据大的子结点
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
//父节点数据小于子节点就交换
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
//更新下标
parent = child;
child = parent * 2 + 1;
}
else//否则向下调整完毕
break;
}
}
// 堆排序(升序)建大堆
void HeapSort(int* a, int n)
{
int i;
//建大堆
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
Adjustdown(a, n, i);
}
//交换调整
for (i = n - 1; i >= 0; i--)
{
Swap(&a[0], &a[i]);//与当前堆尾数据交换
Adjustdown(a, i, 0);//对交换后堆顶数据进行向下调整
}
}
- 直接选择排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
六、交换排序
1、冒泡排序
- 基本思想：
每次遍历待排序数组，对相邻数据进行比较，不符合排序要求则交换
- 动图展示：
- 实现代码：
// 冒泡排序
void BubbleSort(int* a, int n)
{
int i, j;
for (i = 0; i < n - 1; i++)//遍历趟数
{
for (j = 0; j < n - 1 - i; j++)//比较次数
{
if (a[j] > a[j + 1])//升序
Swap(&a[j], &a[j + 1]);//交换
}
}
}
- 冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
2、快速排序
- 基本思想为：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列
左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值 然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
- 按基准值划分左右的方式有：
1）hoare
注：基本操作过程如图示
- 实现代码：
// 按基准划分hoare版本
int PartSort1(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);//三数取中（优化取基准值，后面会解释）
Swap(&a[mid], &a[left]);//使得中间值永远在最左，便于决定谁先走
int key = left;
while (left < right)
{
//Key设在左边，先从右边寻找小于a[key]的
while (left < right && a[right] >= a[key])
{
right--;
}
//再从左边寻找大于a[key]的
while (left < right && a[left] <= a[key])
{
left++;
}
//找到后交换
Swap(&a[left], &a[right]);
}
//最后相遇时将key与相遇点交换
Swap(&a[key], &a[left]);
return left;//返回相遇点下标
}
- key的位置与左右下标谁先走的关系：
注：对于排升序来说
一般来说在三数取中后得到中等值key，我们让该值与待排序数组的最左边起始位置交换，使得key永远在最左边，并且之后会让右下标先走找小于key的值，找到后再让左下标走找大于key的值，都找到则交换，相遇后再将key与相遇位置的值交换
- 右下标先走的话，对于两下标相遇的的情况只有两种：
- 右下标走着走着遇到左下标，此时左下标的值一定是小于key的值（交换后左下标是原来右下标的小于key的值）
- 左下标走着走着遇到右下标，此时右下标的值一定是小于key的是（右下标找小于key的值）
- 所以这样保证了最后下标相遇与key交换后，key左边区间一定小于key，右边区间一定大于key
2）挖坑法
注：基本操作过程如图示
- 实现代码：
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[mid], &a[left]);//使得中间值永远在最左，便于决定谁先走
int key = a[left];//保存key值（基准值）
int pivot = left;//保存坑下标
while (left < right)
{
//右边先找
while (left<right && a[right]>=key)
{
right--;
}
//填坑
a[pivot] = a[right];
pivot = right;
//再从左边找
while (left < right && a[left] <= key)
{
left++;
}
//填坑
a[pivot] = a[left];
pivot = left;
}
//相遇
a[pivot] = key;
return pivot;
}
3）前后指针法
注：基本操作过程如图示
- 实现代码：
// 快速排序前后指针法（推荐）
int PartSort3(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[mid], &a[left]);
//初始化前后指针
int cur = left, prev = left-1;
while (cur < right)
{
if(a[cur]<a[right] )//找到比基准值小的
Swap(&a[++prev], &a[cur]);
cur++;
}
Swap(&a[++prev], &a[right]);//遍历结束将基准值放在定位点
return prev;
}
注：推荐掌握，简单易于操控
4）优化
- 三数取中：
- 如果基准值取到的是待排序列中的中位数，对于快排来说效率是最优的
- 如果基准值取到的是待排序列中的最大或最小，对于快排来说效率是最差的
为了优化这种特殊情况，我们在取基准值时会采取三数取中，即堆待排序序列的开始处，末尾处和中间处位置的数据进行比较，得到排中的数据，尽量使得快速排序的效率达到理想状态O(N*logN)
- 实现代码：
int GetMidIndex(int* a, int left, int right)//优化快排(避免特殊情况造成效率降低)
{
int mid = right + (left - right) >> 1;//获取中间下标（注意避免和溢出）
if (a[mid]>a[left])//返回中等数据的下标
{
return a[mid] < a[right] ? mid : right;
}
else//a[mid]<=a[left]
{
return a[left] < a[right] ? left : right;
}
}
整体实现代码：
//快排
void QuickSort(int* a, int left, int right)
{
//当区间只有一个元素或没有元素时不需要排序了
if (left >= right)
return;
//遍历一趟进行交换排序
int mid=PartSort3(a, left, right);
//递归排序左右区间
QuickSort(a, left, mid - 1);
QuickSort(a, mid+1, right);
}
- 小区间优化：
当待排序数组的区间很小时，递归开辟的函数栈帧数量时很大的，很多时甚至可能造成栈溢出
为了解决这一问题，当区间小到一定程度时，我们选择使用希尔排序，小到一定程度时待排序数列已经快接近有序，而希尔排序对于接近有序数列的排序时非常高效的
- 实现代码：
//快排+局部优化
void QuickSort1(int* a, int left, int right)
{
if (left >= right)//当区间只有一个元素或没有元素时递归结束
return;
if (right - left + 1 <= 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
int mid = PartSort3(a, left, right);//进行一趟交换排序
QuickSort1(a, left, mid - 1);//递归交换排序
QuickSort1(a, mid + 1, right);
}
}
- 快速排序的特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
3、快排非递归
- 基本思想;
对于递归函数在内存实际上是在栈中进行开辟函数栈帧，这里我们使用数据结构中的栈来模拟内存中的栈，从而实现快排的非递归
- 实现代码：
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
//首先构建一个栈（C语言来说需要自己实现）
ST st;
StackInit(&st);
StackPush(&st, left);//将左右区间入栈
StackPush(&st, right);
while (!StackEmpty(&st))
{
int end = StackTop(&st);//读取区间数据
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
int mid = PartSort3(a, begin, end);//排序（排好基准值）
//划分基准值的左右区间
int begin1 = mid + 1, end1 = end;
//先入右边区域（栈的特点是先入后出）
if (end1 - begin1 + 1 > 1)
{
StackPush(&st, begin1);
StackPush(&st, end1);
}
//再将左边区域入栈
int begin2 = begin, end2 = mid-1;
if (end2 - begin2 + 1 > 1)
{
StackPush(&st, begin2);
StackPush(&st, end2);
}
}
//到空栈则排序结束
StackDestroy(&st);//栈销毁
}
七、归并排序
归并排序是建立在归并操作上的一种有效的排序算法，采用分治法
1、归并排序
1）递归归并
- 基本思想：
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序
-
核心步骤：
-
动图展示：
-
实现代码：
//归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)//只有一个元素或没有元素为有序，则返回
return;
int mid = (right + left) / 2;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid+1, right, tmp);
//左区间和右区间有序后开始归并
int begin1 = left, end1 = mid;
int begin2 = mid+1, end2 = right;
int p = left;//记录下标
while (begin1<=end1&&begin2<=end2)//归并排序
{
if (a[begin1] < a[begin2])//升序
{
tmp[p++] = a[begin1++];
}
else
{
tmp[p++] = a[begin2++];
}
}
while (begin1 <= end1)//剩下部分
{
tmp[p++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[p++] = a[begin2++];
}
//拷贝回数组a
for (int i = left; i <= right; i++)
{
a[i] = tmp[i];
}
void MergeSort(int* a, int n)
{
//创建暂存数据数组（保存归并好的数据）
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("nalloc fail\n");
exit(-1);
}
//归并排序
_MergeSort(a, 0, n - 1, tmp);
//释放
free(tmp);
tmp = NULL;
}
- 归并排序的特性总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
2）非递归归并
- 基本思路：
对于归并的非递归来说可以用栈也可以用循环，这里主要讲解循环（比较简单，直接从合并步骤开始）
- 实现代码：
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
int gap = 1;//数组归并距离
//（初始gap为1即每个数组只有一个元素，此时每个数组都为有序数组）
while (gap < n)//归并趟次
{
for (int i = 0; i < n; i += gap * 2)//分组归并
{
//划分区间
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 p = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[p++] = a[begin1++];
}
else
{
tmp[p++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[p++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[p++] = a[begin2++];
}
//拷贝排序后数据到原数组
for (int j = i; j <= end2; j++)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);//释放
tmp = NULL;
}
八、计数排序
计数排序是一种非比较排序，又称为鸽巢原理，是对哈希直接定址法的变形应用
1、计数排序
- 基本思想：
在排序数组中找到最大最小的数据，算出对应范围并创建对应长度个数组用来计数，遍历排序数组，根据每个出现的数据值与计数数组下标构建的相对映射关系进行统计数据出现次数，最后将统计的出的数据按次序赋值给原数组
- 动图展示：
- 实现代码：
void CountSort(int* a, int n)
{
//遍历找出数组最大最小值（算出范围）
int max = a[0], min = a[0];
for (int i = 1; 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*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail");
exit(-1);
}
//初始化数组计数为0
memset(count, 0, sizeof(int)*range);
//遍历计数据出现次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
//a[i] - min：数据与下标构成的相对映射关系
}
//排入原数组
int p = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[p++] = i + min;
}
}
free(count);//释放
count = NULL;
}
- 计数排序的特性总结：
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限（只能对整数排序）
- 时间复杂度：O(MAX(N,range))
- 空间复杂度：O(range)
- 稳定性：稳定
九、性能分析
- 排序算法复杂度及稳定性总结：
- 性能测试代码：
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];
}
//数组排序并计算时间花费
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();
int begin8 = clock();
CountSort(a8, N);
int end8 = 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("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
printf("BubbleSort:%d\n", end7 - begin7);
printf("CountSort:%d\n", end8 - begin8);
//释放数组
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
free(a8);
}
int main()
{
TestOP();
return 0;
}
注：在Release版本下测试比Debug好一点，Release会对测试具有优化，更好的体现排序算法性能
- 测试结果：
- 总结：
总体来说插入排序，选择排序，冒泡排序是低一级水平的排序算法，希尔排序，堆排序，归并排序和快速排序是高一级别的排序，而计数排序效率非常高，但有一定局限