希尔排序/选择排序

前言：

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

常见的排序算法有如下：

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

1：插入排序

1.1 ：直接插入排序

1.1.1 ：代码

void InsertSort(int* arr, int n)
{for (int i = 0; i < n-1; i++){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; }
}

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：代码：

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){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}}
}

分析：

在直接插入排序的基础上，在外层又嵌套了一层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：代码

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){break;}}
}

分析：

有着一定的教育意义，能够让初学者初步熟悉代码，时间复杂度为O(N^2)，在有序的情况下，时间复杂度为O(N);

2.2：快速排序

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

2.2.1：基于递归思想实现快速排序

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

2.2.1.1：hoare法

找基准值的代码：

int _QuickSort3(int* arr, int left, int right)
{int keyi = left;left++;while (left <= right){while (left <= right && arr[right] > arr[keyi]){right--;}//while循环结束时，此时right下标处对应为较小元素while (left <= right && arr[left] < arr[keyi]){left++;}//while循环结束时，此时left下标处对应为较大元素if (left <= right)//当满足条件时，将left 和 right 对应下标的元素交换，得到相对有序数组{swap(&arr[left++], &arr[right--]);}}//上述循环结束时，此时right对应较小元素swap(&arr[keyi], &arr[right]);//将假设值与较小值交换return right;//返回基准值
}

图例分析：

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

图一：

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

图二：

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

图三：

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

图四：

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

递归实现部分代码：

void QuickSort3(int* arr, int left, int right)
{if (left >= right){return;}int key = _QuickSort3(arr, left, right);QuickSort3(arr, left, key - 1);QuickSort3(arr, key+1, right);
}

递归过程：

对于初学者而言，在分析过程中容易忽略 left值 和 right值 的变化，在上述递归的过程中，可以看到，key的改变会影响下次递归 left 和 right 的值，正是 left 和 right 改变，才能使递归满足停止条件，从而返回。

注：其他问题。

1、为什么外层的 while 要去等号？

分析：

以下图为案例：

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

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

显然上图的基准值是不符合条件的，因此外层需要加上等号。

2、为什么内层交换两个元素前，需要加该 if 条件

分析：

以下图数组为例：

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

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

2.2.1.2：挖坑法

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

找基准值代码：

int _QuickSort2(int* arr, int left, int right)
{int hole = left;int keyi = arr[left];while (left < right){while (left < right && arr[right] > keyi){right--;}arr[hole] = arr[right];hole = right;while (left < right && arr[left] < keyi){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = keyi;return hole;
}

图例分析：

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

假设坑（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法

找基准值代码：

int _QuickSort(int* arr, int left, int right)
{int prev = left;int keyi = left;int cur = prev + 1;while (cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[keyi], &arr[prev]);return prev;
}

图例分析：

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

定义一个前后变量 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 的下标入堆，重复上述过程，直至堆中不再有任何元素。

注：因为传递的是数组的地址，入栈的也只是数组对应的下标，当出栈时，当然可以通过下标去访问原先的数组，同时令原先数组发生改变。

代码：

void QuickSortNonR(int* arr, int left, int right)
{ST s;STInit(&s);STPush(&s, left);STPush(&s, right);while (!BoolEmpty(&s)){int end = STTop(&s);STPop(&s);int begin = STTop(&s);STPop(&s);int prev = begin;int keyi = begin;int cur = prev + 1;while (cur <= end)     //找基准值同时对数组进行排序{if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[keyi], &arr[prev]);int key = prev;if (key - 1 > begin)   //模拟返回的过程，若不满足条件则不入栈{STPush(&s, begin);STPush(&s, key-1);}if (key + 1 < end){STPush(&s, key+1);STPush(&s, end);}}
}

图例演示一下这个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 时，不再入栈，右半部分循环结束，此时栈中还保存着基准值左半部分的下标位置，取出栈内元素后，可以对左半部分进行找基准值和排列操作。