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

 

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=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= 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进行比较那么51直接插入排序的话是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.直接选择排序

1. 在元素集合 array[i]--array[n-1] 中选择关键码最⼤(⼩)的数据元素

2. 若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交换

3. 在剩余的 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  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指向的是9 mini指向的是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 = 0; i--) { AdhustDown(arr, i, n);//我们从i这个位置开始向下调整 //i一开始的位置就是最后一个数据的父节点，我们从这个父节点开始向下操作 } //循环将堆顶数据跟最后位置的数据（会变化，每次减小一个数据）进行交换 int end = n - 1;//n是数组的有效个数，那么最后一个数据的下标是n-1 while (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  arr[child + 1]) { //假设我们的子节点只有一个左节点的话，那么我们就可以通过child+1<n  //这个条件避免child++，避免了越界访问，我们直接让左节点和父节点进行交换  //child+1必须小于n我们才能往下进行调整操作，避免越界访问  //假设左边的是56，右边的是15 child++;//我们进行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 (leftarr[keyi])//对应的值大于基准值 { right--;//从右往左换写一个数字进行寻找 } //走到这里说明right找到了比基准值小/等于？ while (left <= right && arr[left] < arr[keyi]) { left++;//还没有找到比基准值大的数据，那么我们就往右接着找 } //说明我们的right和left都找好了 if (left <= right)//交换的前提是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  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，第二次取到的就是right int 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 + 1begin)//如果是[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 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是2end2是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  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数组中现在全是0 memset(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,数组大小是range int index = 0; for (int i = 0; i < range; i++) { while (count[i]--) { arr[index++] = i + min; } } /* 100 101 102 105 101 100 2 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)

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

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

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

3.排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的

相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之

前，则称这种排序算法是稳定的；否则称为不稳定的。

6 2 4 9 1 2

1 2 2 4 6 9

对于原先数组的第一个2的话，如果在排序之后这个2还是第一个二的话，那么这两个二的相对次序保持不变

相对次数保持不变的话，那么我们就称这个排序为稳定排序

相反，相对次数发生变化的话，那么这个排序就是不稳定的排序

直接选择排序是不稳定的

通过找大找小，交换的过程中就会导致相对次序的变化

直接插入排序就是将后面待排序的数据一个一个往前面插入，和打扑克牌一样的

这里是不存在相对位置发生改变的

那么直接插入排序是稳定的

希尔排序我们是会对数据进行分组的，每个组进行独立的排序，就可能导致原本在后面的数字排在前面

那么次序就会发生变化，那么希尔排序是不稳定的

举例：5 8 2 5 9

gap=2

那么5 2 9 是一组，8和5一组

我们先排第一组、

排完了就是2 8 5 5 9

再排第二组

2 5 5 8 9

可以发现之前在后面的5跑到前面去了，那么相对次序就发生了改变

堆排序的思想：将堆顶的数据和堆尾的数据进行交换

那么这里的相对位置就发生了交换了

归并排序是从中间位置划分，两两一排序，相对位置是不会发生变化的

快排：在找基准值的过程中会导致数据发生次序的变化，那么快排就是不稳定的

回忆：栈的底层是数组

队列是链表实现的