”插入排序“”选择排序“

我们学过冒泡排序，堆排序等等。（回顾一下：排升序，建大堆；排降序，建小堆。）

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

在生活中也会遇到很多排序：购物筛选排序（按照价格、综合、销量、距离等排序）、百度热搜（根据热搜程度）、院校排名等等。

插入排序

1. 直接插入排序(O(n^2))

基本思想：将（待排序的记录）按照（关键码值的大小）逐个插入到（已经排好序的有序队列）中。直到所有的记录插入完为止，得到一个新的有序序列。

先将arr[end]指向：(有序队列的最后一个数据)，然后将(需要和有序数据进行比较的数据：即arr[end+1])暂时存储在tmp中，接下来将arr[end]和tmp里的数据进行比较。

注意在一次循环中，tmp的值是不变的(除非end++，才会使tmp的值改变(tmp=arr[end]))

举例1：

【假设想要排升序】

• 现在arr[end]的值大于tmp，应该排在后面，所以现在将end的值放在end+1的位置，这个时候会发现end+1位置的值被覆盖了，所以我们需要提前将它的值存储在tmp中(这就是将值存储在tmp中的原因)。接下来需要将tmp的值放在end的位置(这个是arr[end]的前面没有其他值的情况，我们可以直接将tmp的值赋给arr[end]）

在交换值之后，将end++，tmp的值为arr[end+1] (它不用修改，因为end已经修改了)

• 如果arr[end]<tmp，并不需要交换呢？（比如5和9）那就直接end++，紧接着tmp的值也变啦。

• 紧接着又是将9和6交换，按照之前的方法（将arr[end]的值赋给arr[end+1]，然后将tmp的值赋给arr[end]
  

• 为什么我们还需要将交换之后的arr[end]的值和这个序列前面的值比较呢？------防止它比前面已经排好序的值小

接下来按照前面的方法，再将9和2进行比较

举例2：

直插排序的"代码"

我们需要一个循环来控制end++，往后走；
还需要一个循环来控制：当把arr[end]赋值给arr[end+1]之后，需要将end- -,将前面的数值和tmp继续比较。

在这里插入代码片`void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++)  //为什么是i<n-1?{int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}`

• 为什么是i<n-1呢？
  因为tmp存储的是arr[end+1]，我们要确保它是最后一个不会越界，即end+1<n,又因为end=i，所以i+1<n，所以i<n-1。

直插排序的“时间复杂度”

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

不过O(n^2)是最差的情况。

最差：想将降序----->升序 O(n^2)
最好：升序------->升序 O(n)

2. 希尔排序(O(n^1.3))

希尔排序就是对直接插入排序的一种优化。想要改善降序---->升序的时间复杂度。

希尔排序分为两步：1.预排序 2.直接插入排序

我们可以将很长的一段数组序列变为n段较短的序列，然后对每段“单独”进行直接插入排序(这个叫做预排序)。预排结束之后，小的数据大部分都在前半部分了(只是不按顺序)，接着我们再对整体的数组(已经趋于有序的数组)序列进行一次直插排序，这样不仅完成了排序，还优化了时间复杂度。

方法一

• 首先我们需要决定一个值：gap，然后将大段分为n个小段（每段的首和尾相隔gap个元素，即第一个值往后数gap个，那个数据是这段的最后一个元素）。

什么情况下预排：当gap>1的时候
什么情况下整段直插：当gap==1的时候

1. 从上图可以知晓：要将一大段数据分为很多组数据，在寻找第二组数据时，需要将上次的首元素下标++。这一步由外层循环控制【遍历每个子序列的起始位置（从 0 到 gap-1）】，for(i=0;i<gap;i++)（为什么i<gap?)

2. 接下来是每组数据中，知道了首元素，然后找这组数据中的剩余数据，即end+gap，这个由第二层循环控制：for(int j=0;j<n-gap;j+=gap);(为什么内层的j<n-gap?)

3. 再里面的元素之间比较就没有什么特别了，使用的是直接插入排序(它也有循环)。

【gap不能太大(若太大的话，会导致每组的数据比较少，但组数比较多)，也不能太小(那样的话每组数据会有很多，那这样的话时间复杂度又变高了)】我们可以让gap由元素个数决定，gap=n/3+1，为什么最后还要+1呢？（如果遇到2/3的情况，那商就是0，也就是gap=0，那间距为0，谁和谁比呢？）而我们最后需要让gap=1，让已经预排之后的整段数据进行直插排序，所以需要+1.

【gap等于多少，这段数据最终就会被分为几组数据】如果n特别特别大，n/3之后也特大，先将+1给忽略掉

• 之前我们说到为什么外层循环中i<gap而不是i<n呢？
  
  我们第一组数据的第二个元素是arr[end+gap]也就是arr[0+gap]，既然arr[gap]在第一组数据中已经进行比较过一次，那之后就没必要再将它比较一次了。大家观察上图会发现每个数据都进行比较过，如果外层用 i < n，会导致重复处理同一子序列，效率降低。

• 还有一个问题是：为什么第二层循环需要j<n-gap，按照方法一个组中，每个数据它们都相邻gap个（n=8,gap=3第一组元素下标：0，3，6，下标为6的元素后面还有1个元素，但是剩余元素个数不够gap个，那就只能在这次的循环中将后面的元素舍弃。所以在找每组的数据时（即在第二层循环），循环结束的条件是最后一个元素后面的元素个数小于gap个(有剩余的元素或者剩余个数为0(也就是刚好后面没有元素了))，也就是它的下标小于n-gap

第一组的数据：7，4，1
第二组的数据：6，3
第三组的数据：5，2
…

• 然后，先排第一组的数据，再排2，3组的数据

(1)初始情况：arr[end]指向第一个元素，tmp指向(与第一个相隔gap的元素).即tmp=arr[end+gap]

• 若arr[end]>tmp，那么将arr[end]的值赋给tmp所指向的那个值，即arr[end+gap]=arr[end],赋值之后，将end=end-gap
• 若arr[end]>tmp,不用修改值。直接将end+=gap
  对于每组数据的值比较的注释
  (2)排完第二组的数据之后，外层的i++，到第二个数据【下标为1】(它作为第二组的首元素)，然后进入第二层循环，在进行比较。

到此为止，这个进行了一趟比较

void ShellSort(int* arr, int n)
{int gap = n / 3 + 1;for (int i = 0; i < gap; i++){int j = i;for (j =i; j < n - gap; j += gap){int end = j;int tmp = arr[end + gap];while (end>=0)  //将这组数据的每个数据比较，while结束的条件：end>=0;{if (arr[end] > tmp){arr[end + gap] = arr[end];//想继续和前面有序的数据比较，将end-gapend -= gap;}//到这里，arr[end]<tmp,那就不用赋值，直接将下标+gap，tmp的值随之改变，继续比较else {break;}}//在循环中，我们只是将大的数据往后赋值，那当初那个比较小的tmp赋给谁呢？//这组数据如何能比较结束(break)呢？肯定是此时的arr[end]并没有tmp大，不需要交换了//所以，我们把tmp值赋值给之前一个比较的值(由于是end-=gap,所以上一个是end+gap)arr[end + gap] = tmp;}}
}

之后我们将gap不断缩小，继续比较，直至最后gap==1时，进行最后的，对整段进行直插

void ShellSort(int* arr, int n)
{int gap = n;while (gap>1){gap = gap / 3 + 1;for (int i = 0; i < gap; i++){int j = i;for (j = i; j < n - gap; j += gap){int end = j;int tmp = arr[end + gap];while (end >= 0)  //将这组数据的每个数据比较，while结束的条件：end>=0;{printf("%d ", gap);if (arr[end] > tmp){arr[end + gap] = arr[end];//想继续和前面有序的数据比较，将end-gapend -= gap;}//到这里，arr[end]<tmp,那就不用赋值，直接将下标+gap，tmp的值随之改变，继续比较else {break;}}//在循环中，我们只是将大的数据往后赋值，那当初那个比较小的tmp赋给谁呢？//这组数据如何能比较结束(break)呢？肯定是此时的arr[end]并没有tmp大，不需要交换了//所以，我们把tmp值赋值给之前一个比较的值(由于是end-=gap,所以上一个是end+gap)arr[end + gap] = tmp;}}}
}

注意：为什么gap>1还可以对整段进行直插排序呢？
大家先想一想gap==1的条件：肯定是上一个gap>1因而进入了循环，进行了gap=gap/3+1，而gap/3=0，gap/3+1=1，接下来进行了直插。不会有其他意外。

n=10：
第一次，gap=n=10，大于1，进入循环之后，gap=gap/3+1=4，之后进行排序。
第二次，gap=4,大于1，进入循环，gap=gap/3+1=4/3+1=2，之后进行排序
注意gap=2的时候它仍然大于1 ，进入循环了，然后才进行的gap=gap/3+1,得到了gap=1，进行最后的直插

方法二(时间复杂度更优)

在上面的基础上进行优化：
之前是将一组一组比，现在仍然是相隔gap个的两个元素进行比较，但是当它俩比较完之后，我们不用找arr[0+gap]再隔gap的值。我们直接找arr[0]的下一个:arr[1]，再找arr[1+gap]，将他俩比较。那到什么时候停止呢？当i<n-gap时。

void ShellSort(int* arr, int n)
{int gap = n;while (gap>1){gap = gap / 3 + 1;for (int i=0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0)  //将这组数据的每个数据比较，while结束的条件：end>=0;{if (arr[end] > tmp){arr[end + gap] = arr[end];//想继续和前面有序的数据比较，将end-gapend -= gap;}//到这里，arr[end]<tmp,那就不用赋值，直接将下标+gap，tmp的值随之改变，继续比较else {break;}}//在循环中，我们只是将大的数据往后赋值，那当初那个比较小的tmp赋给谁呢？//这组数据如何能比较结束(break)呢？肯定是此时的arr[end]并没有tmp大，不需要交换了//所以，我们把tmp值赋值给之前一个比较的值(由于是end-=gap,所以上一个是end+gap)arr[end + gap] = tmp;}}
}

希尔排序的时间复杂度是：O(n^1.3)

选择排序

堆排序

这是堆排序的文章，点击链接即可跳转

直接选择排序

这个名字中的“选择”已经暴露了它的方法，直接选择排序是从整个数组中(arr[0]到arr[n-1])选出来min或者max的元素，然后放在整个数组的第一个位置。然后再从arr[1]到arr[n-1]选出来min或max，放在第二个位置。【将min/max放在第一个位置，那原本的数据怎么办，所以不是直接将这个值放在第一个位置，而是将两个值交换】

• 思路：

• 1. 先设定两个变量，begin和mini（它俩是下标），begin作为min或者max放置的位置的下标。mini作为遍历数组时此时位置的下标。[需要知道跳出循环的条件，即放的位置<n]
     

• 但是又一个bug是：每找一次最大/最小值，就需要将数组遍历一遍(和冒泡排序一样费时间O(n^2))，时间复杂度很大，我们进行优化。

在遍历一遍数组的时候，我们可以将min和max同时找出来，将它们放在数组的两端。这样就可以省略一半的时间。【但需要注意的是，这个上面那个的循环结束条件就不一样了，我们不用再遍历后半部分，就是已经放好特定值的那部分】

void SelectSort(int* arr, int n)
{int begin=0;for (begin = 0; begin < n/2; begin++) //为什么begin<n/2呢？因为begin是前半部分的下标，只用占整个数组的一半{int maxi = begin;int mini = begin;//确定了这趟mini要放的位置，接下来这个循环用来遍历找最小值/最大值，用j来遍历int j = begin;for (j = begin+1; j < n-begin; j++)  //为什么j<n-begin//第一遍遍历的时候，需要遍历所有的//第二次遍历，就不用遍历最后一个，已经放了特定的值//第三次遍历，倒数两个都不用遍历了{if (arr[j] < arr[mini])mini=j;if (arr[j] > arr[maxi])maxi=j;}//这一步是什么作用？if (maxi == begin){maxi = mini;}Swap(&arr[begin], &arr[mini]);Swap(&arr[n - 1 - begin], &arr[maxi]);}
}

其中这一步的作用是什么呢？

if (maxi == begin)
{maxi = mini;
}

举个例子：

这个的问题就在于：maxi刚好和begin重合了，而arr[begin]先一步和arr[mini]交换了，所以我们需要在交换之前处理一下：如果它俩重合了，那就先让maxi走到mini的位置。

if(maxi==begin)maxi=mini;