希尔排序/选择排序

前言：

本篇重要对常见的排序算法进行扼要分析，代码中均以数组 arr[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 } 为例，进行升序分列。
常见的排序算法有如下：

选择排序中，直接选择排序没有任何实际与教育意义，而堆排序在先前文章中有提及，不在思量。

1：插入排序

1.1 ：直接插入排序

1.1.1 ：代码

1. void InsertSort(int* arr, int n)
2. {
3.         for (int i = 0; i < n-1; i++)
4.         {
5.                 int end = i;               
6.                 int tmp = arr[end + 1];     
7.                 while (end >= 0)            
8.                 {
9.                         if (arr[end] > tmp)     
10.                         {
11.                                 arr[end + 1] = arr[end];   
12.                                 end--;                                     
13.             }
14.                         else
15.                         {
16.                                 break;
17.                         }
18.                 }                  
19.                 arr[end + 1] = tmp;
20.                                
21.     }
22. }

复制代码

1.1.2：图例分析上述代码

初次进入 for 循环时，如图一所示：
注：end 对应数组下标，tmp 对应数组元素

图一

此时 end = 0，进入 while 循环；此时 arr[end] = 5 ，tmp = 3 ，满足 if  条件，将数组第一个元素的值赋值给第二个元素，end-- 后为 -1，不满足 while 循环条件，结束while 循环。
当第一次跳出while循环时，此时数组中的元素如图二

图二

此时并没有得到我们想要的数组，下标 0和1 的元素重复 ，我们需要将 tmp 的值传递到 下标0 处，而通过 end+1 便可以访问 下标0处，因此 arr[end + 1] = tmp;  该条语句的目的就是为了得到正确分列的数组。
第二次进入 for 循环时，如图三所示：

图三：

此时 end = i = 1，而 tmp = 9，进入while循环后，不满足 if 条件，因此直接结束。
第三次进入for循环时，如图四所示：

图四：

此时 end = i = 2 ，而 tmp = 6，进入while循环后，满足 if 条件，元素 6 会被 9 替代，而 end-- 指向前一个位置处，此时如图五所示

图五：

此时end = 1 再次进入while循环时，此时不在满足 if 条件 ，结束 while 循环，通过末了一步 end+1，我们可以访问被代替元素的前一个元素的下标位置处，即下标2处，再将 tmp 赋值给 arr[end+1]即arr[2]我们可以得到正确的分列如图六：

图六

第四次进入循环时，如图七所示：

图七：

此时 end = 3，tmp = 2，进入循环后，因为 2 小于 前面全部元素，因此不断循环直至end = -1，如图八所示：

图八：

再次将tmp的值赋值给 arr[end+1] 便可以得到正确的排序。
1.1.3：直接插入排序的特点

①、元素越接近有序，直接插入排序算法的时间效率越高
②、时间复杂度为O(N^2)
③、空间复杂度为O(1)


1.2：希尔排序

1.2.1：思路

希尔排序是在直接插入排序的根本进行的优化，前面所说，元素越接近有序，直接插入排序算法的时间效率越高，希尔排序正是按着这个特性，先尽可能的让数组元素有序，再进行排序。
因此希尔排序的思路为：
先将数组内的元素按间隔排序，这个间隔一样平常为 n/3+1，n为数组内元素个数，并且每排序完一次，gap = gap /3 +1 再按新的gap再次排序，直至 gap为1时，此时就酿成了直接插入排序，但这是的数组已接近有序，因此时间复杂度会大大降低。
1.2.2：代码：

1. void ShellSort(int* arr, int n)
2. {
3.         int gap = n;
4.         {
5.                 while (gap > 1)
6.                 {
7.                         gap = gap / 3 + 1;
8.                         for (int i = 0; i < n-gap; i++)
9.                         {
10.                                 int end = i;
11.                                 int tmp = arr[end + gap];
12.                                 while (end >= 0)
13.                                 {
14.                                         if (arr[end] > tmp)
15.                                         {
16.                                                 arr[end + gap] = arr[end];
17.                                                 end -= gap;
18.                                         }
19.                                         else
20.                                         {
21.                                                 break;
22.                                         }
23.                                 }
24.                                 arr[end + gap] = tmp;
25.                         }
26.                 }
27.         }
28. }

复制代码

分析：
在直接插入排序的根本上，在外层又嵌套了一层while循环，这个while循环就是用来对gap进行限定，当gap较大时，此时每个元素间的间距(gap)比较大，当gap = 4 时，如下图

当外层while第一次循环结束时，如图所示，此时较原来相比，已接近有序，此时 gap = 2 再次循环。

当外层while第二次循环结束时，如图所示，数组元素变得更加有序。

末了当gap = 1时，此时就为直接插入排序。
1.2.3：希尔排序的特点：

时间复杂度 O(N^1.3)

2:交换排序

2.1：冒泡排序

2.1.1：代码

1. void BubbleSort(int* arr, int n)
2. {
3.         for (int i = 0; i < n; i++)
4.         {
5.                 int exchange = 0;
6.                 for (int j = 0; j < n - i - 1; j++)
7.                 {
8.                         //升序
9.                         if (arr[j] < arr[j + 1])
10.                         {
11.                                 exchange = 1;
12.                                 swap(&arr[j], &arr[j + 1]);
13.                         }
14.                 }
15.                 if (exchange == 0)
16.                 {
17.                         break;
18.                 }
19.         }
20. }

复制代码

分析：
有着一定的教育意义，能够让初学者开端认识代码，时间复杂度为O(N^2)，在有序的环境下，时间复杂度为O(N);


2.2：快速排序

快速排序一共有四种实现方式，前三种实现方式都是基于递归的思想，在找基准值上存在着区别，而第四种方法是借助堆，通过循环模拟递归的思想来实现。
2.2.1：基于递归思想实现快速排序

先前说到，递归实现快速排序只在找基准值的方法上存在区别，那么什么是基准值？我们所要找的基准值，以升序为例，就要是在数组中找到这样一个位置，他的左边的元素都小于它，右边的元素都大于它，这个元素对应的下标巨细就为基准值
2.2.1.1：hoare法

找基准值的代码：

1. int _QuickSort3(int* arr, int left, int right)
2. {
3.         int keyi = left;
4.         left++;
5.         while (left <= right)
6.         {
7.                 while (left <= right && arr[right] > arr[keyi])
8.                 {
9.                         right--;
10.                 }//while循环结束时，此时right下标处对应为较小元素
11.                 while (left <= right && arr[left] < arr[keyi])
12.                 {
13.                         left++;
14.                 }//while循环结束时，此时left下标处对应为较大元素
15.                 if (left <= right)//当满足条件时，将left 和 right 对应下标的元素交换，得到相对有序数组
16.                 {
17.                         swap(&arr[left++], &arr[right--]);
18.                 }
19.         }//上述循环结束时，此时right对应较小元素
20.         swap(&arr[keyi], &arr[right]);//将假设值与较小值交换
21.         return right;//返回基准值
22. }

复制代码

图例分析：


未进入第一个while循环前，各变量对应关系如图一所示，以keyi作为参考值

图一：

当进入外层while循环后，right开始向右找较小值，left开始向左找较大值，当内层的两个while循环结束时，此时各变量对应关系如图二所示：

图二：

此时 left < right 交换两者下标对应元素后 left++，right--，各变量对应关系如图三所示：

图三：

此时left和while仍满不测层while循环条件，继续重复上述步调直至如图四所示。

图四：

此时已经跳出外层循环，将 keyi 与 right 对应下标元素交换后，此时 right 左侧元素均小于 5，右侧元素均大于5，而right就是我们所找的基准值。
递归实现部分代码：

1. void QuickSort3(int* arr, int left, int right)
2. {
3.         if (left >= right)
4.         {
5.                 return;
6.         }
7.         int key = _QuickSort3(arr, left, right);
8.         QuickSort3(arr, left, key - 1);
9.         QuickSort3(arr, key+1, right);
10. }

复制代码

递归过程：

对于初学者而言，在分析过程中容易忽略 left值 和 right值 的变化，在上述递归的过程中，可以看到，key的改变会影响下次递归 left 和 right 的值，正是 left 和 right 改变，才能使递归满足停止条件，从而返回。
注：其他题目。
1、为什么外层的 while 要去等号？
分析：
以下图为案例：

我们顺着上述代码，终极第一次循环会来到如下位置：

此时left = right跳出循环，再将right对应的值与key对应值交换，此时得到如下图所示数组：

显然上图的基准值是不符合条件的，因此外层需要加上等号。
2、为什么内层交换两个元素前，需要加该 if 条件
分析：
以下图数组为例：

顺着代码，当第一次循环结束前，各个变量对应关系如图所示

此时若没有该 if 条件，right 和 left 的对应元素会再交换一次，这样就不符合基准值的条件，因此需要有该 if 条件，代码才能够正常运行。
2.2.1.2：挖坑法

前面所说，三种递归实现快速排序的方法只在找基准值的方法上有所不同，因此这里不再对其他代码过多追叙，直接分析找基准值部分的代码：
找基准值代码：

1. int _QuickSort2(int* arr, int left, int right)
2. {
3.         int hole = left;
4.         int keyi = arr[left];
5.        
6.         while (left < right)
7.         {
8.                 while (left < right && arr[right] > keyi)
9.                 {
10.                         right--;
11.                 }
12.                 arr[hole] = arr[right];
13.                 hole = right;
14.                
15.                 while (left < right && arr[left] < keyi)
16.                 {
17.                         left++;
18.                 }
19.                 arr[hole] = arr[left];
20.                 hole = left;
21.                
22.         }
23.         arr[hole] = keyi;
24.         return hole;
25. }

复制代码

图例分析：

起始时，各个变量对应关系如图所示：

假设坑（hole）的位置在 left 处，并且将 left 处对应的元素临时存放在 keyi 中，我们先从 right 开始向左找比keyi小，找到第一个位置处时，将 hole 位置处的值赋为 right 位置处的值，同时将 hole 移动到 right 位置处，此时新坑位于 right 处，此时各变量对应关系如下图所示：

然后我们再从 left 向右开始找比keyi大的值，找到第一个位置处 9 时，我们重复上述的过程，把元素 9 赋值给 hole 位置处，然后把 hole 移到 left 位置处，此时各变量对应关系如下图所示：

注：其实此时我们能够发现，left 和 right 位置对应的值已经发生改变，第二次循环开始时，已然满足内层循环的 while 条件，因此 right 可以继续向左减减找小值，而 left 也能够向右加加找大值。
重复上述过程，终极各个变量对应关系如下图：

注：为什么内层循环要多一个 left < right 的判断条件?
分析：可以看到，如果没有这个条件，left 会继续向右找大值，即到下标为5的位置处，会让 hole 多一次变化，而这一次变化，会导致所找的基准值发生错误，因此内层的 while 循环需要多这一个条件。当while循环结束时，我们再把临时值 keyi 赋值给 hole 位置处，此时 hole 位置就是对应基准值的位置，各个变量关系如下图所示

2.2.1.3：lumoto法

找基准值代码：

1. int _QuickSort(int* arr, int left, int right)
2. {
3.         int prev = left;
4.         int keyi = left;
5.         int cur = prev + 1;
6.         while (cur <= right)
7.         {
8.                 if (arr[cur] < arr[keyi] && ++prev != cur)
9.                 {
10.                         swap(&arr[cur], &arr[prev]);
11.                 }
12.                 cur++;
13.         }
14.         swap(&arr[keyi], &arr[prev]);
15.         return prev;
16. }

复制代码

图例分析：

起始时，各变量对应关系图下图：

界说一个前后变量 prev 和 cur，同时界说临时值 keyi = 5 。当 cur 中对应的值小于 keyi时，同时 ++prev 不等于 cur 时，我们让 prev 对应的值与 cur 对应的值交换，内层循环的 if 隐含着一些码字菜鸟（我）容易忽略的信息，为什么++prev 而不是 prev++，首先这个条件是为了克制重复交换，其次 ++prev 后此时虽然不满足 if 条件，但是 prev 的值照旧 +1 了，因此此时 prev 和 cur 已经指向了同一个位置，只不过不会发生交换而已，各个变量关系如下图所示： 

判断完 if 条件后，让 cur 持续++。观察上述数组，能够发现，3 背面的两个元素均大于临时值 keyi，此时 prev会来到元素 2 的位置处，而 2 已经满足内层 if 条件，因此我们将 prev+1 后 与 cur 位置对应的元素交换，此时各个变量关系对应如图所示：

重复上述过程，终极各个变量的对应关系如图所示：

当外层 while 循环结束时，我们交换 下标0 与 prev位置对应的元素，即得到了我们想要的数组，同时 prev 为基准值对应的位置处。
2.2.1.4：递归版本快速排序的特性：

1.时间复杂度为：O(nlogn)
2.空间复杂度为：O(logn)  —— 这个空间复杂度来源与递归的层数，每次递归会像体系申请新的空间，同时原空间会被保留。


2.2.2：非递归版本的快速排序的实现

前言：非递归版本的快速排序是借助栈的方式来实现的，将数组首尾下标入队后，取栈内两个数据作为数组尾和头再出栈，通过lumoto方法找到该数组对应的基准值key，再将 left ~ key-1 的下标，以及 key+1 ~ right 的下标入堆，重复上述过程，直至堆中不再有任何元素。
注：因为传递的是数组的地址，入栈的也只是数组对应的下标，当出栈时，固然可以通过下标去访问原先的数组，同时令原先数组发生改变。
代码：

1. void QuickSortNonR(int* arr, int left, int right)
2. {
3.         ST s;
4.         STInit(&s);
5.         STPush(&s, left);
6.         STPush(&s, right);
7.         while (!BoolEmpty(&s))
8.         {
9.                 int end = STTop(&s);
10.                 STPop(&s);
11.                 int begin = STTop(&s);
12.                 STPop(&s);
14.                 int prev = begin;
15.                 int keyi = begin;
16.                 int cur = prev + 1;
17.                 while (cur <= end)     //找基准值同时对数组进行排序
18.                 {
19.                         if (arr[cur] < arr[keyi] && ++prev != cur)
20.                         {
21.                                 swap(&arr[cur], &arr[prev]);
22.                         }
23.                         cur++;
24.                 }
25.                 swap(&arr[keyi], &arr[prev]);
26.                 int key = prev;
27.                 if (key - 1 > begin)   //模拟返回的过程，若不满足条件则不入栈
28.                 {
29.                         STPush(&s, begin);
30.                         STPush(&s, key-1);
31.                 }
32.                 if (key + 1 < end)
33.                 {
34.                         STPush(&s, key+1);
35.                         STPush(&s, end);
36.                 }
37.         }
38. }

复制代码

图例演示一下这个while循环的过程：

初始时，将下标 0 和下标 8 入栈

由此我们开始分析while循环部分，以栈为空作为外层 while 循环的结束条件
进入外层 while 循环后取栈顶元素并且出栈，这种取元素再出栈的操纵包管了我们能够取到我们想要的元素，同时将这两个元素作为 lumoto法找基准值中的 cur 的结束位置和 prev 初始巨细。
注：注意入栈的次序，入栈次序会影响后续读取栈顶元素时，begin 和 end 的取值。
当我们取到下标 0 和 8 时，通过下标访问数组元素，同时基于lumoto法实现找基准值的方法，这里不在过多追叙，此时各变量关系如图所示：

此时显然满足 begin < key - 1、 key+1 < end ，因此将下标 begin、key-1、key+1、end 分别入栈，当第二次进入循环时，首两次出栈会取到下标 key+1 和 end ，这正对应了2.2.2.1中提到的递归过程一样，left的值发生变化的过程，（编者菜，会觉得left一直等于0，其实正如刚才的递归过程一样，每个子节点的向右递归left值会发生改变），于是我们先对这对范围内的数组进行找基准值和分列操纵，操纵完成后，再次向栈中，push下标，直至不在满足 if 条件为止，不过此时栈中元素不为空，因为原先找的基准值 4 左边的数组尚未进行排序，接下来从栈中取出的元素，正是对左半部分进行找基准值和排序的操纵，如此循环往复直至结束。

上图为对基准值右半部分的循环过程，可以看到当不满足 begin < key - 1、 key+1 < end 时，不再入栈，右半部分循环结束，此时栈中还保存着基准值左半部分的下标位置，取出栈内元素后，可以对左半部分进行找基准值和分列操纵。




免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。