手撕初阶数据结构之---排序

1.排序概念及运用

排序：所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的⼤⼩，递增或递减的排列起来的操作。

常见的排序算法

直接插入排序的时间复杂度是O(N^2)

这个是最差的情况下，就是大的在前面，小的在后面

希尔排序就是直接插入排序的优化版本

将时间复杂度优化为O(N^1.3)

时间选择排序是雷打不动的O(N^2)

堆排序是O(N logN)

冒泡排序是O(N^2)

在数组有序的情况下我们能优化成O(N)，但是这种情况很少见

2.常见排序算法

1.插入排序

1.直接插入排序

当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移

现在我们有一堆的数字，现在我们一个一个进行比较，只要我们发现后面的值比前面的值大，那么我们就把前面的值放到当前的位置，继续往前进行比较,那么这么就会导致前面遍历过的内容都是有序的，将后面乱序的数字一个个插入到前面有序的序列中，使其变得有序

这种思想和打牌是一样的

给出一个数组10 9 8 7 6 5 4 3 2 1

现在我们要变为升序

我们创建变量tmp

先将9存在tmp中，将9与10进行比较，如果9比10小的话，那么就将10挪到9的位置

然后用tmp为第一个位置重新赋值，那么第一个数字就是9

然后我们前两个数字就是有序的数列

然后依次从后面拿数字到前面进行比较

//2 5 8 1 5 6
//直接插入排序
void InsertSort(int* arr, int n)
{//i最后一次是n-2，对应数组中倒数第二个数字for (int  i = 0; i < n-1; i++){//i不能小于n，假设n=10//那么i<9//当end=8时，那么tmp就是9，那么就存在越界行为了int end = i;//end从0开始int tmp = arr[end + 1];//有序区间的后一个数字while (end>=0){//比较if (arr[end] > tmp)//end位置的数据大于tmp，那么tmp往前走{arr[end + 1] = arr[end];//将end位置的数据往后挪end--;}else//end位置的数小于tmp位置的，我们就跳出循环{break;}}//此时的end就小于0，跳出循环arr[end + 1] = tmp;}
}

在内层循环中

随着i的变化，交换的情况最差就是1 +2 +3 +（n-1）

那么内层循环的时间复杂度就是O(N)

外层循环的时间复杂度也是O(N)

那么这个直接插入法的时间复杂度就是O(N^2)

数组有序且为降序的情况下时间复杂度最差

最差的情况下时间复杂度为O(N^2)

如果是有序为升序下，那么时间复杂度就是O(N)

数组为降序序列时，直接插入排序能得到优化？

将N个数据划分成很多个段，每个段单独进行直接插入排序

那么这样我们就能减少时间复杂度了

那么我们将直接插入排序我们就得到了希尔排序

2.希尔排序

数组为降序序列时，直接插入排序能得到优化？

将N个数据划分成很多个段，每个段单独进行直接插入排序

那么这样我们就能减少时间复杂度了

那么我们将直接插入排序我们就得到了希尔排序

1.对每一段进行预排序

2.直接插入排序

预排序使数组接近有序

希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序。

它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算法的。

//希尔排序
//时间复杂度为O(N^1.3)
void ShellSort(int* arr, int n)
{int gap = n;while (gap>1)//控制gap的变化{gap =gap/3+1;//保证最后一次gap一定为1//当我们的gap为1的时候那么就是直接插入排序for (int i = 0; i < n - gap; i ++)//每一组的几个数据之间进行比较{/*如果最后一次的话i为n-2,那么end为n-2那么tmp=n-2+gap   那么就会存在越界现象所以我们的条件是i<n-gap那么end=n-gap-1tmp=n-gap-1+gap=n-1那么tmp最后一次取到的数据就是最后一个数据*/int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp)//那么说明tmp小，那么小的就要往前面放{arr[end + gap] = arr[end];//我们现将end这个位置的数挪到end+gap这个位置end -= gap;}else//就说明tmp对应的数大于end对应的数，那么对于跳出循环的代码我们是相当于tmp是不动的{break;}}//跳出循环之后我们的tmp应该放在end+gap这个位置arr[end + gap] = tmp;}}}
/*
9 1 2 5 7 4 8 6 3 5
现在我们的gap为3
那么就是隔三个为一组
那么第一组就是9 5  8  5
因为5小于9
那么先将9放到5的位置，然后end-=gap
因为一开始的end为0，那么end-=gap之后那么end就变为了-3
然后因为end<0那么跳出循环
然后我们end+gap=-3+3=0
那么arr[3]这个位置就放tmp的值
这个位置就是第一个位置
那么就完成了end和end+gap这两个位置的数据的置换5 1 2 9 7 4 8 6 3 5
我们外循环的条件改为i+=gap
每次递增gap
那么我们的end就到了9的位置，tmp到了8的位置因为tmp小于end
那么我们就将tmp位置的数覆盖为end的值,tmp位置上面就变成了9了
然后end-=gap
此时的end=3，经过了end-=gap操作之后end=0
我们再拿出tmp中的8和end对应的5进行比较，那么我们就break了循环那么我们就将tmp里面的8放到end+gap 的位置
那么就是下标为3的位置
5 1 2 8 7 4 9 6 3 5那么我们再次进入循环
end就走到了9的位置，tmp就走到了end+gap就是最后的5的位置了因为5比9小，那么先将9覆盖到tmp 的位置
然后end-=gap
那么end就走到了现在8的位置
然后再次进入循环，那么8于tmp中的5进行比较
那么5<8
那么8放到9的位置，9的位置就是end+gap
将8放完之后end-=gap
那么end就回到了0
那么5和5进行比较
那么我们就break出来
然后我们将tmp中存的5放到end+gap这个位置5 1 2 5 7 4 8 6 3 5 9
我们之前的第一组是9 5 8 5  就是每隔gap个就是一组
那么现在就是5 5 8 9 那么现在我们控制的是一组
那么我们还要在外面进行一个for循环我们定义的gap是3
那么就是定义的3组
第一组是9 5 8 5
第二组是1 7 6
第三组是2 4 3
那么第二组换完就是1 6 7
那么第二组换完就是2 3 4 那么经过这么一趟排序
我们的数组就变成了5 1 2 5 6 3 7 4 9
那么数组又接近有序了然后gap/3=1
那么就是1个为1组
那么就变成了直接插入排序了 那么对于希尔排序来说，预排序的条件是gap>1
直接插入排序的话是gap==1
那么最后我们的一次直接插入排序我们就得到了1 2 3 4 5 5 6 7 9那么通过预排序小的在前，大的在后
那么我们通过直接插入排序的话就可以减少次数我们现在从4层循环优化成3层循环现在我们是
第一次我们先排第一组的前两个数据
因为将之前的for循环删除了
那么现在我i++
那么我们接着排第二组的前两个数据
然后i++
那么我们就接着排第三组的前两个数据然后我们i++
我们就进行第一组的第三个数据和前两个数据进行比较
*/

希尔排序是三层循环

n/3

n/3/3

……

除到1

log3 n=x

x是次数

那么3^x=n

如果n=9的话，那么x=2

假设一组里面的数据是8 5 2

那么我们的交换次数最差是3次

8和5进行交换一次

2和8 和5分别交换一次

那么总共就是三次

当gap=1的时候，数组基本有序，直接插入排序时间复杂度为O(N)

我们推荐在使用希尔排序的时候使用gap=gap/3

如果是gap/2的话那么循环的次数就太多了

2.选择排序

1.直接选择排序

在元素集合 array[i]--array[n-1] 中选择关键码最⼤(⼩)的数据元素
若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交换
在剩余的 array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素

//直接选择排序优化版本
//直接选择排序的时间复杂度是O(N ^ 2)
void SelectSort02(int* arr, int n)
{int begin=0;//指向第一个数据int end = n - 1;//指向最后一个数据//遍历整个数组找到最小的数保存到mini中while (begin < end)//当begin=end的时候那么这个时候我们就调整完了整个数组了{//一开始将最大的和最小的都定义在begin这个位置int mini = begin, maxi = begin;for (int  i = begin+1; i <=end; i++){//起始的条件取决于begin,我们每次从begin+1这个位置进行找大的和找小的数据if (arr[i] > arr[maxi]){maxi = i;//重新定义最大的值的下标}if (arr[i] < arr[mini]){mini = i;//重新定义最小的值的下标}}//跳出循环之后我们用最小值和begin这个位置的值进行交换//最大值和end进行交换//优化：避免maxi begin都在同一个位置，begin和mini交换之后，maxi数据变成了最小的数据if (maxi == begin){//因为此时的maxi和begin指向的是同一个数字//那么我们直接为maxi重新赋值//我们将maxi的值赋值到mini这个位置maxi = mini;}/*9 5 1在这个数组中，我们的maxi和begin指向的都是同一个数那么就满足了这个条件语句了此时的maxi指向的是9mini指向的是1那么我们将maxi重新进行赋值，复制为mini那么此时的maxi和mini同时指向的是1我们在下面的交换函数中我们先将mini和begin进行交换那么就是将1和9进行交换那么现在的数字就是1 5 9那么此时我们就完成了最小值的交换了然后进行最大值的交换此时的end和maxi都指向的是9那么相当于不进行操作那么最后我们就得到了我们想要的排序了*/Swap(&arr[mini], &arr[begin]);Swap(&arr[maxi], &arr[end]);//交换完成之后我们继续往中间进行找大小的操作begin++;end--;}
}
/*
在外层的while循环中,
n  n-2  n-4  n-6   …………2
每次减少首尾两个数据进行比较那么while循环的时间复杂度就是O(N)内层的for循环
n-1  n-2  n-3  ………… 1
这里的for循环时间复杂度也是O(N)那么这个直接选择排序的时间复杂度是O(N^2)
和冒泡排序是一样的
*/

2.堆排序

HeapSort

//堆排序
//期望空间复杂度是O(1) ，不额外的开辟空间
//时间复杂度是O(n*log n)
void HeapSort(int* arr, int n)
{//根据数组来建堆,那么我们就需要便利数组//建小堆---降序// 向上调整算法建堆//for (int i = 0; i < n; i++)//{//  AdjustUp(arr, i);//我们给的参数是i,就是开始 调整数字的 下标，我们是从数组第一个元素进行调整的，i=0开始的//}//向下调整算法建堆//我们需要通过最后一个元素的下标n-1找到他的父节点，从这个点开始进行操作//父节点：（n-1  -1）/2for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdhustDown(arr, i, n);//我们从i这个位置开始向下调整//i一开始的位置就是最后一个数据的父节点，我们从这个父节点开始向下操作}//循环将堆顶数据跟最后位置的数据（会变化，每次减小一个数据）进行交换int end = n - 1;//n是数组的有效个数，那么最后一个数据的下标是n-1while (end > 0)//end会一直--，但是end必须大于0{Swap(&arr[0], &arr[end]);//将第一个数据和最后一个数据进行交换//那么我们就要对现在的剩下的堆进行调整//我们采用向下调整的方法AdhustDown(arr, 0, end);//我们从根进行调整，那么第二个参数就是0//n-1=end,就是我们只需要对剩下的n-1个数据进行向下调整，那么第三个参数就是我们调整的有效数据n-1个end--;}
}

堆排序使用时需要的向下调整算法AdhustDown以及交换函数Swap

//向下调整
void AdhustDown(int* arr, int parent, int n)
//第一个数据是我们要调整的数组，第二个参数是父节点，就是我们开始进行调整的位置的下标对应的元素，第三个是数组中有效的元素个数
{//我们已知Parent，那么我们能够通过2i+1或者2i+2找到这个父节点的左右子节点int child = parent * 2 + 1;//左孩子while (child < n)//我们不能让child因为++操作导致越界{//找左右孩子中最小的那个，我们与父节点进行交换操作if (child + 1 < n && arr[child] > arr[child + 1]){//假设我们的子节点只有一个左节点的话，那么我们就可以通过child+1<n      //这个条件避免child++，避免了越界访问，我们直接让左节点和父节点进行交换//child+1必须小于n我们才能往下进行调整操作，避免越界访问//假设左边的是56，右边的是15child++;//我们进行child++操作，然后child就跑到了15的位置，然后我们将15和父节点进行交换}if (arr[child] < arr[parent])//如果子节点小于父节点的话我们就进行交换{Swap(&arr[child], &arr[parent]);//交换完成之后我们让parent走到child的位置parent = child;//child走到当前位置的左孩子的位置child = parent * 2 + 1;}else//如果Parent比child小的话，那么我们就没必要向下进行调整了{break;//我们直接跳出}}
}

//交换函数
void Swap(int* x, int* y)//一定要传地址才能进行交换了
{int tmp = *x;*x = *y;*y = tmp;
}

3.交换排序

1.冒泡排序

//冒泡排序
//时间复杂度为O(N^2)
void BubbleSort(int* arr, int n)//数组以及数组中的有效数据个数
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){//<就是降序if (arr[j] < arr[j + 1])//大的在后面，那么我们就进行交换{exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){//那么就说明我们经历了一趟内循环，我们的exchange并没有改变，就说明这个数组可能之前就是有序的break;}}
}

2.快速排序

Hoare版本

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素

序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩

于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列

在相应位置上为⽌。

简单意思就是说：我们在数组中去一个数当作基准值，然后，整个数组被分为两个部分

左边的一个部分小于基准值，右边的部分大于基准值

那么这就相当于一个二叉树了

基准值是根节点，左边的是左子树，右边的是右子树

然后重复上面的操作，将左序列和右序列单独取出来，重复上面的操作

数组是左和右这个区间，在这个区间之中我们要找基准值mid

那么我们的左子序列的递归的右边界是mid-1

右子序列：mid+1,right

如何找基准值呢？

我们先将数组中第一个数据定义为基准值

right:从右到左找基准值小的数据

left：从左到右找比基准值大的数据

6 1 2 7 9 3

一开始的基准值Keyi指向的是6

left指向的是1

right指向的是3

那么我们先进行right的行动，找到了3

然后left往右找到了7

然后将两个指针指向的值进行交换

那么我们得到了

6 1 2 3 9 7

然后left指向的是3，right指向的是7

交换完成之后再重复刚才的过程

right左走找到3

left右左找到9

那么right就到了left的左边了

这个时候我们将keyi指向的6和right指向的3进行交换

那么我们得到了3 1 2 6 9 7

此时我们的基准值在right的位置

right指向的位置的左边都比基准值小，右侧都比基准值大

那么对于左序列的话3 1 2

我们找基准值

right一开始就找到了比基准值小的数，但是left一直++，直到比right大了

然后我们就将right指向的数据和keyi指向的数据进行交换

2 1 3

那么此时的right是基准值

我们再对当前序列进行划分

左子序列就是2 1，右序列为空

我们再对左序列进行判断

我们的right指向的1

left指向的是1

keyi指向的是2

此时的right和left是重合的，那么就不影响我们找基准值，相等的话我们继续进行循环

那么right刚好找到的就是1比2小

right找好了

接下来找left，left++,越界了，已经比right大了，那么我们就跳出循环，

那么我们就将key和right指向的值进行交换

那么最后就得到了

1 2

那么此时我们的左序列就剩一个序列了

right和Left都是空了，就是left和right相等了

那么我们就没必要找基准值了

那么对于这个数组的话，我们的左子序列已经递归完了

那么我们还要递归右子序列

那么我们通过快排不断地找基准值，根据基准值划分左右区间，一直进行递归操作

我们要创建log n个函数栈帧

那么空间复杂度就是O(log n)

一层递归循环的时间复杂度是O(N)

但是我们要递归logN层

时间复杂度是O(N logN)

//块排子方法
//right:从右到左找基准值小的数据//left：从左到右找比基准值大的数据//hoare版本找基准值
int _QuickSort(int* arr, int left, int right)//找基准值，返回Int
{int keyi = left;//一开始的left是最左边的，那么我们就先临时将第一个数据定义为基准值//我们从left+1,right这个范围进行寻找left++;//我们要让right走到left的左边while (left<=right)//一定要=，//left和right相遇的位置的值比基准值大{while (left<=right&& arr[right]>arr[keyi])//对应的值大于基准值{right--;//从右往左换写一个数字进行寻找}//走到这里说明right找到了比基准值小/等于？while (left <= right && arr[left] < arr[keyi]){left++;//还没有找到比基准值大的数据，那么我们就往右接着找}//说明我们的right和left都找好了if (left <= right)//交换的前提是left<=right{//那么我们将这两个下标对应的数据进行交换操作Swap(&arr[left++], &arr[right--]);}}//只要lefy大于right了，那么我们就跳出循环走到这里了// 将right指向的值和key指向的值进行交换//跳出循环，那么就是right走到了left的左边，那么我们将right指向的值和keyi指向的值进行交换Swap(&arr[keyi], &arr[right]);//那么交换完成之后，那么right指向的数据就是我们的基准值了return right;
}//快速排序
void QuickSort(int* arr, int left, int right)//左右位置的下标
{if (left >= right)//left走到了right的右边或者重叠（只有一个数据的话）{return;}//找基准值int keyi = _QuickSort(arr, left, right);//左子序列：[left,keyi-1]QuickSort(arr, left, keyi - 1);//右子序列：[keyi+1,right]QuickSort(arr, keyi +1 ,right);}

挖坑法

思路：

创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）

不断地挖坑不断地填坑

一开始我们是不知道坑在哪里的，那么我们就随便定义一个坑

6 1 2 7 9 3 4 5 10 8

我们将6定为坑hole

我们再定义一个基准值key=6指向坑所指向的位置

一开始的left指向6，right指向8

先让right往左走找比基准值小的

找到了5

那么我们直接将5拿挖走去填我们之前定义的坑

那么此时的right的指向的位置就是一个坑

那么数组就变成这样了

5 1 2 7 9 3 4 hole 10 8

接下来left从左往右找比基准值大的

找到了7

那么我们将7挖出来去填坑

那么left这个位置就是一个新的坑

5 1 2 hole 9 3 4 7 10 8

然后right再找小

找到了4

那么我们将4挖出去填坑，那么此时的right成为新的坑

5 1 2 4 9 3 hole 7 10 8

左边继续找大，找到了9

将9挖出来，去填坑

那么此时的left的位置就是坑

5 1 2 4 hloe 3 9 7 10 8

然后right继续找小

找到了3

把3拿去填坑

那么此时的right的位置就是坑

5 1 2 4 3 hole 9 7 10 8

然后left接着走

然后left和right已经重合了

那么我们将之前的基准值填到坑里面

5 1 2 4 3 6 9 7 10 8

那么基准值6的左边比基准值小，右边比基准制度大

//挖坑版
int _QuickSort2(int* arr, int left, int right)//找基准值，返回Int
{int hole = left;int key = arr[hole];while (left<right)//只要left和right重合那么我们就跳出循环{while (left < right && arr[right] > key)//没有找到比基准值小的,后面的条件我们就不用加等号了，因为可能存在这个数组的元素都是一样的情况{right -- ;}//那么这里我们找到了小的，那么我们就将这个数字拿去填坑，那么此时right指向的位置就是新的坑arr[hole] = arr[right];hole = right;while (left < right && arr[left] < key)//没有找到比基准值小的{left++;}//走到这里就说明找到了要拿去填坑的数字arr[hole] = arr[left];hole = left;}//走到这里说明我们的left和right可能重合了//那么我们将基准值放到坑位arr[hole] = key;return hole;//将坑位返回，此时的坑位就是基准值
}

lomuto前后指针

创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。

定义两个变量prev和cur

cur指向位置的数据跟key值比较，若arr[cur]<arr[keyi]

那么prev向后走一步并和cur交换数据

若arr[cur]≥arr[keyi]

那么cur继续往后走

直到cur越界，那么我们将此时的prev和key的值进行交换

那么此时prev指向的位置就是我们要的基准值

//lomuto前后指针法
int _QuickSort3(int* arr, int left, int right)//找基准值，返回Int
{int prev = left, cur = left + 1;int keyi = left;while (cur<=right)//当我们的cur越界了我们就不进行循环{if (arr[cur] < arr[keyi]&&++prev!=cur)//两个指针相等的话，那么我们就不进行交换{//只要cur找到小的，就让prve++然后进行交换Swap(&arr[cur], &arr[prev]);}cur++;}//cur越界了//将之前定义的基准值和现在prev指向的值进行交换Swap(&arr[keyi], &arr[prev]);return prev;}

快排的非递归版本

上面介绍到的都是递归版本的

那么我们接下来就介绍下快排的非递归版本

那么非递归的快速排序的需要借助数据结构：栈

我们将区间right和left依次入栈

那么我们再依次取出来，得到的就是0和5

假设我们经过依次寻找，那么这里的基准值是

那么我们就能得到左区间和右区间

左区间[left,keyi-1]

右区间[keti+1,right]

总结下来我们就是先将区间入栈

先是right再试left

我们再出一次栈

那么我们根据这个区间找基准值

前面介绍的三种方法

我们是right先入栈，left先出栈，那么取出来的时候就是left先出栈，right再出栈

那么第一次的话我们的左区间是[0,2],右区间是[4,5]

我们先将右区间入栈，再将左区间入栈

那么我们进行出栈操作，取到的是left=0,right=2

那么在这个区间我们的keyi=0,这里的是下标

那么我们再重复上面的左右区间的方法继续找基准值

左区间[left,keyi-1] [0,-1]

右区间[keti+1,right] [1,2]

这里的基准值是不需要继续去找基准值的，因为这里的keyi-1已经小于0了

那么我们就不用入栈了

就是非有效区间不入栈

但是右区间是有效的区间，那么我们进行入栈操作

那么我们接着对右区间进行递归操作

我们将left和right取出来

left=1,right=2

我们对这个右区间找基准值

那么我们这里的基准值keyi=1，就是数组中对应的3

那么根据当前的基准值我们又能划分区间了

左区间[left,keyi-1] [1,0] 非有效区间不进行入栈

右区间[keti+1,right] [2,2] 只有一个数据不进行入栈

那么此时我们的左区间所有的内容都递归完了

这里其实是循环，不是递归，我们循环取栈的数据模拟的递归

我们排右区间

我们将栈中的left和right取出

left=4,right=5 我们找到的基准值keyi=4,指向6这个数字

那么我们再次根据这个基准值划分左右区间

左区间[left,keyi-1] [4,3]非有效区间，不入栈

右区间[keti+1,right] [5,5] 只有一个有效数据，不如栈

那么我们的右区间就已经找好基准值了

那么这个数组的右区间已经递归完了

通过栈来实现快速排序

//非递归版本的快速排序
//借助数据结构---栈
void QuickSortNonR(int* arr, int left, int right)
{ST st;STInit(&st);//栈的初始化//先将右区间入栈，再就是左区间SrackPush(&st, right);SrackPush(&st, left);//栈只要不为空，那么我们就取栈顶元素while (!StackEmpty(&st))//取两次，作为左右区间{//取栈顶元素--两次//那么第一次取到的就是left，第二次取到的就是rightint begin = StackTop(&st);SrackPop(&st);//取完栈顶元素接着进行出栈操作//取出来的左右区间int end= StackTop(&st);SrackPop(&st);//利用取出来的左右区间创建新的区间//[begin,end]---找基准值//双指针找基准值int prev = begin;int cur = begin + 1;int keyi = begin;while (cur<=end)//当我们的cur越界了我们就不进行循环{//要确保prev++完成之后的值不等于cur我们才能进入循环进行操作if (arr[cur] <= arr[keyi]&&++prev!=cur){Swap(&arr[cur], &arr[prev]);}cur++;}//跳出循环的时候说明cur已经越界了Swap(&arr[keyi], &arr[prev]);//那么此时的prev指向的位置就是基准值的位置keyi = prev;//解下来我们根据这个基准值再对左右区间进行操作//根据基准值划分左右区间//左区间：[begin,keyi-1]//右区间：[keyi+1,end]//如果我们根据这个begin和end找基准值的话那么这两个量是不会越界的//我们是需要对下面的keyi+1和keyi-1进行判断是不是有效的值if(keyi + 1<end)//等于end的话就是说明有效数据只有一个//如果是大于的话，那么就是越界情况了，比end还大//如果满足这个条件的话那么我们就入栈{//先入右区间，SrackPush(&st, end);//右区间内的右区间SrackPush(&st, keyi + 1);//右区间内的左区间}if (keyi - 1>begin)//如果是[0,-1]就不是一个有效的区间{//再入左左区间SrackPush(&st, keyi - 1);//左区间内的右区间SrackPush(&st, begin);//左区间内的左区间}}STDestory(&st);//栈的销毁
}
/*
一开始我们传的left是0，right是5
我们进行入栈操作
先入的是5，再入的是0入完栈之后，判断栈是否为空
不为空的话就进入循环取栈顶元素
先取0，再取5
那么0和5组成了一个空间
那么我们对这个区间找基准值keyi
第一次的基准值我们找的是3，这里是下标
那么我们使用双指针法进行基准值的寻找
找到基准值之后我们根据这个基准值进行新区间的划分
划分左右区间
因为keyi=3
那么左区间就是[0,2] 右区间是[4,5]
那么这两个区间都是有效区间，那么就都进入了if条件语句中
那么进行条件语句中将左右区间进行入栈的操作
先入的是右区间
再就是左区间
先入的是5 4
再就是 2 0
那么现在这个栈从上到下看就是0 2 4 5
因为此时的栈不是空的，所以我们还继续循环
然后我们将栈顶元素取出来[0,2]
我们再根据这个区间进行基准值的寻找
那么这个区间的基准值是0
那么对于[0,2]这个区间的话我们分出的区间是[0,-1]和[1,2]
那么我们对这段区间进行判断是否为有效的区间
对于[1,2]满足条件，那么就入栈
但是[0,-1]这个不满足，那么就不入栈
那么此时的栈中我们入的是 2 1 
那么此时的栈中元素从上到下看就是2 1 4 5然后因为栈不为空，那么继续进行循环
将2 1 取出找基准值
那么对于 [1,2]这个区间来说的话
我们又分出两个区间
[1,0]和[2,2]
两个区间都不是有效的区间
那么就都不入栈那么我们就进行4和5的出栈了
[4,5]
我们对[4,5]找基准值
基准值是4
那么分出的区间都是无效区间
那么此时的栈就是空的
那么我们对于每个区间我们都找好了基准值了
那么我们就退出了循环
*/

4.归并排序

归并排序算法思想：

归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divideand Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。归并排序核⼼步骤：

对于图中这8个数据，我们实现二分，从中间一分为二

如果我们单看分解的那部分，这个图长得很像二叉树

那么我们可以参考二叉树递归的过程对他进行分解

分解到只有一个数据的时候

合并的时候两两一合并

两个有序的数组合并

8个有序数组两两一合并成为4个数组

4个有序数组两两已合并成为2个数组

//归并排序void _MergeSort(int* arr, int left, int right,int*tmp)//左下标和右下标求中间值,还要将开辟的空间的指针进行接收，进行合并数据的存储
{//递归结束的条件，就是刚好被分的数组中只剩下一个元素，那么我们就没必要往下进行递归了if (left >= right){return;}//我们需要根据left和right不断进行中间下标的寻找int mid = (left + right) / 2;//根据mid得到两个区间，不断地进行二分，将数据分成两组//[left,mid]  [mid+1,right]_MergeSort(arr, left, mid, tmp);//左区间_MergeSort(arr, mid + 1, right, tmp);//右区间//能够走到这里说明我们已经分解完了，那么我们就开始进行合并的操作了//[left,mid]  [mid+1,right]int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;//比较两个序列中的数据的大小//序列中可能是一个数字，也可能是4个数字while (begin1 <= end1 && begin2 <= end2)//那么此时的这些下标都是有效的{if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else//说明begin2小{tmp[index++] = arr[begin2++];}}//要么begin1越界，要么begin2越界while (begin1<=end1)//begin2越界，那么我们就将begin剩下的元素安排到数组中{tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//[left,mid]  [mid+1,right]//把tmp中的数据拷贝回arr中for (int i = left; i < right; i++){arr[i] = tmp[i];}}void MergeSort(int* arr, int n)
{//开辟一个和原数组大小一样的数组用于存储合并后的数组//动态开辟n个整型空间int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0,n - 1,tmp);free(tmp);tmp = NULL;
}
/*
对于这个归并排序的子函数进行解释
在第一步分解中
假如我们传的left=0，right=7
数组原先的数据是这样的
10 6 7 1 3 9 4 2
那么我们根据左右下标将mid求出
为3
那么我们就分出了两个区间
[0,3]   [4,7]
然后我们下面又对着两个区间进行递归
那么我们最后就实现了将这个数组分解的效果了那么我们将这么一个完整的数组分成多个单独的序列
10  6  7  1  3  9  4  2  
那么就是这8个单独的序列
我们两两合并
一开始的begin1和end1都是0
begin2和end2都是1
那么我们先在第一个while循环中间进行比较并进行赋值到tmp中
因为10>6那么我们进入到else中
那么tmp[index++] = arr[begin2++];
将begin2的值赋值到tmp中第一个位置
然后begin++,index++但是现在我们只是将6放到tmp中，10还没有放
那么我们在后面的while就进行了处理了
因为我们的begin1此时已经比end1大了，就是越界了
那么我们就进入到第一个条件语句中
tmp[index++] = arr[begin1++];
此时的index就是指向的tmp数组中的第二个位置了
那么我们的第二个位置就复制成之前的begin1
那么第二个就是10了
然后begin1++那么总结：
在分解为一个个的元素之前，我们的10和6是一个区间的
这个区间求中间值分左右区间，合并完成之后我们完成另一个区间的合并我们在逐渐的合并过程中，这个begin1  begin2 end1  end2
都在变化，   当分解之后的第一个合并的时候，begin1和end1都是0 
begin2和end2都是1     那么将6和10合并之后  
我们就回到了上一级 上一级的左区间已经合并完成，
但是右区间没有合并，那么我们按照6和10的步骤合并1和7    
合并完成之后返回上一级，那么我们就进行现有的（6 10）（ 1  7 ）
这两个区间的合并    此时的begin1是0，end1是1     begin2是2
end2是3   那么我们逐次进行比较并为tmp中进行赋值    
那么最后我们就合并出了    1 6 7 10   那么我们会到上一级   
上一级的左区间合并完成，现在完成右区间的合并后，合并之后就是 
2 3 4 9   那么最后这两个区间合并之后就是1 2 3 4 6 7 9 10这个归并排序可以想成二叉树，从叶子到根，从最下面合并到最上面
*/

可以想成一个二叉树，我们分解之后进行合并的操作我们可以想象从下面到上面逐次合并

空间复杂度：logn 根据层数来定的

时间复杂度：在归并的子函数中的第一个while循环中就是相当于n个数进行比较

那么这个循环的时间复杂度是O(N)

那么第二个循环的话，进行完第一个循环之后应该是剩下不了几个数据的

那么最大的情况就是n/2

下面的for循环拷贝数组中的值，那么时间复杂度也是n

那么单次递归时间复杂度就是O*(N)

但是递归的深度是logN

那么这里的时间复杂度就是O(N log n)

那么时间效率和快排是一样的

5.非比较排序

计数排序

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。

操作步骤：

1）统计相同元素出现次数

2）根据统计的结果将序列回收到原来的序列中

我们需要先找到数组中的最大值，然后将数据中的个数变为下标

根据数组中最大值来开辟对应的空间

新数组的大小如何确定？

原数组中最大的值来确定（如果数组中存在负数的话是不行的）（未考虑到最小值）

将负数变为正数，取绝对值是否可行？

正负数绝对值相同的情况下是无法区分正数和负数的

假如我们的给到的值很大，既然我们要用这个当做数组的下标

那么我们是不是要开创这么大的数组呢

其实没有必要的

最大的值-最小的值+1就是这个数组的大小了

举例子：100 101 109 105 101 105

我们数组中的每个元素减去这个数组的最小值，那么不就是这个新数组的下标吗

100-100=0 那么100对应的下标就是0 出现的次数就是1 那么下标为0对应的数据就是1

100对应的下标就是0，下标对应的数据就是100出现的次数

那么其他的也一样

这个计数排序的原理其实就是通过计数

在新的数组中将这个以这个数据出现的次数为元素

我们依次进行打印

比如说在上面那个代码里面

100出现了1次，那么我们打印1次

101出现两次，那么我们打印两次

那么这样我们就达到了排序的目的了

最大值-最小值就是我们要开辟的空间大小

但是这个适用于数组中存在负数的情况吗？

-5 -5 9 5 1

那么这个数组的大小就是9-（-5）+1=15

那么我们就申请下标为15的空间

下标就是从0到14

那么我们应该将这些数据怎么放？

就是这个数据减去这个数组中最小的值

-5的对应的下标就是-5-（-5）=0

那么这个0对应的数据就是-5出现的次数2

然后放9 9-（-5）=14

那么9对应的下标就是14，那么14对应的就是9出现的次数1

那么我们通过这种思想的话那么空间就不会过多浪费

通过测试，这个计数排序是现有的排序算法中最牛逼的

单位ms

[InsertSort:663 ShellSort:9 SelectSort:4300 HeapSort:5 QuickSort:6 MergeSort:5 BubbleSort:12451 CountSort:1](InsertSort:663 ShellSort:9 SelectSort:4300 HeapSort:5 QuickSort:6 MergeSort:5 BubbleSort:12451 CountSort:1)

//计数排序
void CountSort(int* arr, int n)
{//我们需要一个count数组来保存我们每个元素的出现次数//我们先需要直到数组中最大值和最小值，在这之后我们才方便数组的开辟//根据最大值最小值确定数组大小int max = arr[0], min = arr[0];//通过遍历找最小值for (int  i = 0; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}int range = max - min + 1;//数组元素的个数//申请range个整型大小的空间存放每个数据出现的次数int* count = (int*)malloc(sizeof(int) * range);if (count == NULL)//开辟失败的话我们就报个错{perror("malloc fail!");exit(1);}//初始化，让count数组中现在全是0memset(count, 0, range * sizeof(int));//第一个参数是要被填充的数组的指针//第二个参数是要被填充的数据//第三个参数就是填充的字节的大小//我们的想法是将这个新数组中现在存储的数据都是0、//那么我们要填充的字节大小就是rang*sizeof(int)//现在统计数组中每个数据出现的次数，然后将次数放到对应的下标for (int  i = 0; i < n; i++){count[arr[i] - min]++;//这个arr[i]-min就是我们我们数据映照在新数组的下标，//后面的++就能将count这个数对应的下标进行计数//就是这个数据的出现次数通过这个代码就能存进新数组中}//取count中的数据往arr中放//我们现在遍历的是count,数组大小是rangeint index = 0;for (int  i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}/*100   101   102   105   101   1002   2   1   0   0   1     数据出现的次数0   1   2   3   4   5在上面的for循环中，当i=0时，count[i]=2那么arr[0]=100+0这里是内循环两次的，因为循环条件是count[i]--那么第二次内循环就是arr[1]=100那么原数组中的前两个数据我们就打印好了当i=1时，我们内循环的次数就是这个数出现的次数count[i]=2那么我们就内循环两次那么我们就将下标为2和3的位置都赋值上101了、那么最后我们的arr中的数据就是这样的100 100 101 101 105*/}

空间复杂度是O(range)

我们在第一个循环中的时间复杂度是O(N)

第二个循环是外层循环是O(range)

内层循环的循环次数还是取决于实际的数据n

那么这里的这个循环的时间复杂度是range+n

那么总的时间复杂度就是O(range+n)

那么我们总结一下计数排序的特性：

计数排序在数据范围集中时，效率很高，但是使用范围及场景有限

只适用于整数排序，不能用小数排序