鼠鼠来喽，今天鼠鼠带你玩转排序算法~
你间歇性的努力和蒙混过日子，都是对之前努力的清零！
一、排序的概念及其应用
1.1 排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起
来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记
录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍
在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2比较排序的分类
二、插入排序
2.1 插入排序
基本思想：直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。
void InsertSort(int arr[],int num)
{
for (int i=0;i <num-1;i++) {
//1.摸牌并保存
int end = i;
int tmp = arr[end + 1];
//2.比较挪动
for (;end >= 0;end--) {
if(arr[end]>tmp){
arr[end + 1] = arr[end];
}
else {
break;
}
}
//3.插入
arr[end + 1] = tmp;
}
}
2.1.1时间复杂度
1.数组逆序情况下，插入排序第一趟时间复杂度为O（N),第二趟为O（N-1)……成等差数列，所以整体为O（N^2)
2.已经排好的情况下，每一趟为O（1)，整体为O（N)
2.1.2 总结
元素集合越接近有序，直接插入排序算法的时间效率越高（比较次数少）
时间复杂度：O(N^2) 最好O（N）
空间复杂度：O(1)，它是一种稳定的排序算法
稳定性：稳定
2.2 希尔排序（优化版插入排序）
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有
记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重
复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
void ShellSort(int arr[],int num)
{
int gap=num;//数组元素个数决定分组幅度
while (gap > 1) {
gap = gap / 3 + 1;//控制分组幅度
//对前num-gap数据每个进行插入排序
for (int i = 0;i < num - gap;i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0) {
if (arr[end] > tmp) {
arr[end + gap] = arr[end];
end -= gap;
}
else {
break;
}
}
arr[end + gap] = tmp;
}
}
}
2.2.1时间复杂度
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。 一般认为其时间复杂度为O（N^1.3)！
《数据结构-用面相对象方法与C++描述》--- 殷人昆
2.2.2 总结
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比
希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3—
N^2）稳定性：不稳定 ，因为相同的值可能分到不同的组中，从而在预排阶段造成不稳定
三、选择排序
3.1 选择排序
基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
void SelectSort(int* a, int n)
{
int begin = 0,end=n-1;
while (begin < end)
{
//1.假设begin位置值最大、最小
int maxi = begin, mini = begin;
//2.遍历后续数组，寻找最大值、最小值下标
for (int i = begin + 1;i <= end;i++)
{
if (a[i] < a[mini])
mini = i;
if (a[i] > a[maxi])
maxi = i;
}
//3.交换值
swap(&a[begin], &a[mini]);
//防止最大值正好是begin位置，第一次交换导致最大值被换到mini位置
if (maxi == begin)
maxi = mini;
swap(&a[maxi], &a[end]);
//4.去除两个已经排好的值
begin++;
end--;
}
}
3.1.1 时间复杂度
第一趟比较为O（N），第二趟比较为O（N-1)……，成等差数列，所以整体为O（N^2)，无论数组是否有序，都要从头向后遍历比较，所以时间复杂度都是O（N^2)。
3.1.2总结
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定 比如原数组为**{ 8 5 8 5} 第一次选择将8与5交换，形成不稳定**
3.2堆排序
写的另一篇博客介绍堆和堆排序
总结：
堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定，比如数组**{1 1 1 1 1}**，每次首元素与最后一个交换，造成不稳定
四、交换排序
4.1 冒泡排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位
置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移
动。
void BubbleSort(int* a, int n)
{
//设立一个标识，判断原数组是否已经有序，
//当第一趟比较没有数据交换，flag保持不变,则已经有序
int flag = 0;
for (int i = 0;i < n - 1;i++)//控制趟数
{
for (int j = 0;j < n - 1 - i;j++) //控制比较次数
{
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
flag = 1;
}
}
//flag未变则已经有序，跳出循环
if (flag == 0)
break;
}
}
4.1.1 时间复杂度
当数组已经有序，第一趟比较没有值交换，flag未变直接结束循环，时间复杂度为O（N），如果数组不是有序，每一趟比较次数呈等差数列，时间复杂度为O（N^2) 。
4.1.2 冒泡排序的特性总结
- 冒泡排序是一种非常容易理解的排序
- **时间复杂度：O(N^2) 最好O(N) 平均O（N^2) ** 3. 空间复杂度：O(1)
- 稳定性：稳定
4.2 快速排序
其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式有：挖坑法、霍尔法、前后指针法
4.2.1 挖坑法单趟排序
基本思想：取数组第一个数为基准（key），并形成坑位（pivot) 。先从最后（end) 往前找比key小的数，找到后将该数覆盖至坑位，然后该数形成新的坑位。然后从前(begin)往后找，找比key大的数，找到后覆盖至坑位，然后自己成为新的坑位，就这样迭代直到(begin>=end) 结束，最后将key覆盖坑位。
int PartSort2(int arr[], int left, int right)
{
int begin = left, end = right;
//找基准，设定坑位
int pivot = begin;
int key = arr[pivot];
//排序
while (begin < end)
{
//从后往前，注意细节循环条件中也要加上begin<end
//即使满足最外面循环，但内循环end也可能越过begin，
while (begin<end && arr[end] > key) {
end--;
}
arr[pivot] = arr[end];
pivot = end;
//从前往后，循环也要加上begin<end
while (begin < end && arr[begin] < key) {
begin++;
}
arr[pivot] = arr[begin];
pivot = begin;
}
//用key覆盖最后坑位
arr[pivot] = key;
return pivot;
}
4.2.2 霍尔法单趟排序
基本思想：选定一个基准值，规定begin指向最左边的值，end指向最右边的值。先从end向前找第一个小于基准值的数，找到后，再从begin向后寻找第一个大于基准值的数，交换两个数，继续从此刻end的位置向前找第一个小于基准值的数，再从begin位置向后找第一个大于基准值的数，找到后，两数进行交换，重复如此，直到end和begin相遇，再交换end与begin相遇的值和基准值。
为什么先让后走？ 因为最后要keyi与小值交换！这就要求最后停下来的位置上是小值，而end是从后往前找小值，先走end最后与begin相遇位置的值一定是小值！
int PartSort1(int arr[], int left, int right)
{
int begin = left, end = right;
int keyi = begin;
while (begin <end) {
while (begin < end && arr[end] >= arr[keyi]) {
end--;
}
while (begin < end && arr[begin] <= arr[keyi]) {
begin++;
}
swap(&arr[begin], &arr[end]);
}
swap(&arr[keyi], &arr[begin]);
return begin;
}
4.2.3 前后指针法单趟排序
基本思想：先说明这里的指针指的是下标！前后指针（prev,cur) ,cur向后找小，找到后，prev前置++，并且判断++完后prev是否等于cur(这个步骤也可以不加，此时只是自己和自己交换），不等于则将两者数据进行交换，迭代直到cur遍历完数组。
为什么前置++，根据下图我们的目的是将5放到正确位置，前置++可以让5免于被交换，而最后被交换！
int PartSort3(int* a, int left, int right)
{
//定义前后指针
int begin = left, end = right;
int prev = begin, cur = begin + 1;
//遍历
while (cur <= end)
{
//判定交换
if (a[cur] < a[begin] && ++prev != cur)
{
swap(&a[prev], &a[cur]);
}
//迭代
cur++;
}
//最后将基准放入正确位置
swap(&a[begin], &a[prev]);
return prev;
}
4.2.4 递归实现全趟快排
我们已经快排单趟排序可以确定一个值放入正确位置，接下来就是对它的左右再次进行快排就行，只要每一次单趟排返回那个已经排好的值，就可以实现左右递归。递归返回条件是数组只有一个值，或者不存在值！
void QuickSort(int arr[], int left,int right)
{
//数组不存在或者只有一个值返回
if (left >= right)
{
return;
}
//三种单趟排序方法
//int IndexKey=PartSort1(arr, left, right);
//int IndexKey = PartSort2(arr, left, right);
//int IndexKey = PartSort3(arr, left, right);
//递归左
QuickSort(arr, left, IndexKey- 1);
//递归右
QuickSort(arr, IndexKey + 1, right);
}
4.2.5 快排优化（三数取中+插排减少递归）
1.三数取中（减少
现给一个递减数组（9，8，7，6，5，4）
当取得基准是9时，时间复杂度会是O（N*N），它的排序过程会是如下图
所以要换基准，不能让最大值最小值作基准！所以采取三数取中！让数组首元素变成三数中间值，这样就可以让每次单趟排完后左右值比较匀称！三数指的是首 尾 中
上代码~ 这个三数取中语法逻辑有点眼花缭乱，一定要耐住性子思考！
int GetIndex(int arr[], int left, int right)
{
int Mid = (left + right) / 2;
if (arr[Mid] > arr[left]) {
if (arr[Mid] > arr[right]) {
if (arr[left] > arr[right]) {
return left;
}
else {
return right;
}
}
else {
return Mid;
}
}
else {
if (arr[Mid] < arr[right]) {
if (arr[right] > arr[left]) {
return left;
}
else {
return right;
}
}
else {
return Mid;
}
}
}
现在上优化后的代码 ！
//优化后（以霍尔法为代表）
int PartSort1(int arr[], int left, int right)
{
int begin = left, end = right;
int Index = GetIndex(arr, left, right);
swap(&arr[begin], &arr[Index]);
int keyi = begin;
while (begin <end) {
while (begin < end && arr[end] >= arr[keyi]) {
end--;
}
while (begin < end && arr[begin] <= arr[keyi]) {
begin++;
}
swap(&arr[begin], &arr[end]);
}
swap(&arr[keyi], &arr[begin]);
return begin;
}
2.有限制条件的递归（插入排序+快速排序）
递归的展开像二叉树一般，越往下展开递归次数越多，递归要开展栈帧消耗栈空间，这样效率就越低，对于快排也就是越往下要排的数越小，我们可以判定当要排的个数小于一个数时，我们可以用另一种排序来解决。有人可能会说堆排序，不可！因为堆排序要建堆，建堆就需要O（N），然后又要排序。希尔？也不行，因为希尔针对的是大量数据，数据小Gap小，分组也不明显。冒泡、插入要O(N*N)，效率低，也不行。所以最好我们考虑插入排序，在接近有序的情况下，插入排序时间复杂度近O(N)!
void QuickSort(int arr[], int left,int right)
{
if (left >= right)
{
return;
}
//int IndexKey=PartSort1(arr, left, right);
//int IndexKey = PartSort2(arr, left, right);
int IndexKey = PartSort3(arr, left, right);
if (IndexKey - left < 8)
{
InsertSort(arr, IndexKey - left);
}
else {
QuickSort(arr, left, IndexKey - 1);
}
if (right - IndexKey - 1 < 8)
{
InsertSort(&arr[IndexKey + 1], right - IndexKey);
return;
}
else {
QuickSort(arr, IndexKey + 1, right);
}
}
4.2.6 快排非递归实现
这里我们需要数据结构的栈来模拟实现递归栈帧调用！我写的另一篇有关栈和队列的博客
我们创造的栈用来存区间参数！
void NonRecursiveQsort(int arr[], int left, int right)
{
//建立并初始化栈
ST st;
StackInit(&st);
//将数组区间入栈
StackPush(&st, right);
StackPush(&st, left);
//循环实现“递归”过程
while (IsStackEmpty(&st)) {//栈空间非空继续循环
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
int IndexKey=PartSort3(arr, left, right);
//这里需要注意，栈的后进先出原则，我们先处理左半区间，所以要先入右后入左
//还有就是我们之前先是取了区间的左值，后取区间的右值，所以区间，我们要先入右值，后入左值
if (IndexKey+1<right) {
StackPush(&st, right);
StackPush(&st, IndexKey+1);
}
if (left < IndexKey-1) {
StackPush(&st, IndexKey-1);
StackPush(&st, left);
}
}
}
4.2.7 快速排序总结
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定 比如数组{ 3 1 3 1 5 6 7} 第一趟排完-->{1 1 3 3 5 6 7}
五、归并排序
5.1递归实现归并排序
基本思路：利用分治的思路，先递归将区间不断缩短直至不能递归（分解），然后归并使左右子区间有序（合并），然后返回合并成新序表。
归并处理方面：归并即利用两个指针，比较左右区间两边数大小尾插形成新序表，这里强调尾插！需要我们开辟一个临时数组，尾插到临时数组然后拷贝回原数组。为什么不能考虑直接在原数组比较覆盖？因为覆盖会造成原数组被覆盖位置元素的丢失，又需要建立临时变量存储数据，比较麻烦，不能一步到位！尾插到临时数组是一目了然的。
void _Mergesort(int* arr, int left, int right, int* tmp)
{
//当区间只有一个数或者没有数返回
if (left >= right) {
return;
}
//递归缩小区间
int Mid = (left + right) >> 1;
_Mergesort(arr, left, Mid,tmp);
_Mergesort(arr, Mid + 1, right, tmp);
//比较左右区间，尾插
int begin1 = left, end1 =Mid;//左区间
int begin2 = Mid + 1, end2 = right;//右区间
int Index = left;//记录尾插位置
//1.遍历比较，当有一个区间走到尾，结束比较
while (begin1 <=end1 && begin2 <= end2) {
if (arr[begin1] < arr[begin2]) {
tmp[Index++] = arr[begin1++];
}
else {
tmp[Index++] = arr[begin2++];
}
}
//2.将未遍历完的数组直接尾插至临时数组
while (begin1 <= end1)
{
tmp[Index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[Index++] = arr[begin2++];
}
//拷贝回原数组
for (int i = left;i <= right;i++) {
arr[i] = tmp[i];
}
}
void MergeSort(int* arr,int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
int left = 0, right = n - 1;
_Mergesort(arr, left, right, tmp);//再写一个函数，如果重复递归原函数会重复开辟空间
free(tmp);
tmp = NULL;
}
5.2 循环实现非递归归并排序
基本思路：利用gap控制每次归并的元素个数，先左右区间元素为1个归并，然后左右区间元素为2个并，即每次归并完后gap每次乘以2，依此循环直到gap>=整个数组元素。归并过程不变，尾插临时数组。
归并处理细节：如果数组元素个数正好是2的整数幂，左右区间元素正好匹配。如果不是，利用原算法会造成越界，越界分成三种情况，要特别处理 。
拿数组举例 { 9,6,3,2,4,8,1,0,7,5 } n=10
**1.左区间右端点越界 ** gap=4时
2.右区间左端点越界（右区间不存在） gap=2时
3.右区间右端点越界(左右区间元素个数不匹配，左>右）gap=8时
**对应上面上图~ **
解决：前两种右区间不存在，所以不能归并，而左区间是有序的，可以不动。后一种是左右区间元素个数不匹配，但依旧可以比较尾插，拷贝。
修改后，上图~
void NonMergeSort(int* arr, int n, int* tmp)
{
int gap = 1;
//gap控制归并次数
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;
int Index = i;
//1.左区间右端点越界，直接结束
if (end1 >= n)
{
printf("[%d,%d]", begin1, n-1);
break;
}
//2.右区间左端点越界，直接结束
if (begin2 >= n)
{
printf("[%d,%d]", begin1, end1);
break;
}
//3.右区间右端点越界，修正右端点，左右区间仍可以继续归并
if (end2 >= n)
end2 = n - 1;
printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);//查看归并左右区间
//比较尾插
while (begin1 <= end1 && begin2 <= end2) {
if (arr[begin1] < arr[begin2]) {
tmp[Index++] = arr[begin1++];
}
else {
tmp[Index++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[Index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[Index++] = arr[begin2++];
}
//拷贝
memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
printf("\n");
//扩大归并区间
gap *= 2;
}
}
void MergeSort(int* arr,int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
int left = 0, right = n - 1;
NonMergeSort(arr, n,tmp);
free(tmp);
tmp = NULL;
}
5.3 计算时间复杂度
对循环思路，外循环是logN，内循环整体是每次遍历整个数组，为N，所以整个时间复杂度是O（N*logN)。
5.4 总结
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2.** 时间复杂度：O(NlogN)*
3. 空间复杂度：O(N)
4. 稳定性：稳定
六、非比较排序
6.1 计数排序
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。** 当然这是一种牺牲空间换取时间的做法*，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序。
排序细节：
计数数组是根据原数组数组值相对大小开辟的，比如一个数组为**{ 5 3 10 3 2 4 5 3}，最大值为10，如果不考虑相对大小，计数数组需要一个大小为MAX+1字节的数组，即11，但如果考虑相对大小，只需要Max-Min+1字节大小的数组，即9个字节，以小见大，如果数组最大值很大，不考虑相对大小，开辟的字节数很大，空间和时间复杂度就会变大**。
再往下，既然是相对大小个数的数组，计数数组下标也是相对的，怎么将原数组计数呢？拿数组值为2和10的数举例，我们之前开辟了9个字节的空间，2应当放入下标为0的位置，10应当计入下标为8的位置，不难看出：下标=数组值-Min
那又怎么利用计数数组排序放回原数组呢？
通过上面推导出来的关系，我们可以知道数组值=下标+Min
** 上代码~**
void CountSort(int arr[],int num)
{
//1.寻找数组最大值最小值
int max = arr[0], min = arr[0];
for (int i = 0;i < num;i++) {
if (arr[i] > max) {
max = arr[i];
}
}
for (int i = 0;i < num;i++) {
if (arr[i] < min) {
min = arr[i];
}
}
//2.求出相对大小开辟空间
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
memset(count, 0, sizeof(int) * range);
//3.计数
for (int i = 0;i < num;i++) {
count[arr[i] - min]++;
}
//4.排序
for (int i = 0,j=0;i < range;i++) {
while (count[i]--) {
arr[j++] = i + min;
}
}
free(count);
count = NULL;
}
6.1.1 时间复杂度
第一次遍历原数组，时间复杂度为O（N)，计数的时间复杂度为O（N)，最后排序遍历计数数组的时间复杂度为O（K)，K为相对数组大小，所以时间复杂度为O（N+K)或者表示为O(MAX(N,K))。
6.1.2 计数排序总结
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
- 稳定性：稳定
七、排序特点总结
八、小结
排序算法是校招、公司招聘的必考项目，是重中之重，以上总结写得也是呕心沥血，反复琢磨写的，希望大家能给个三连，如果你发现其中哪里有问题，也希望您能及时向我反馈一下，大家一起进步哈~
版权归原作者 不到满级不改名 所有， 如有侵权，请联系我们删除。