排序算法（一）
- 2020 年 4 月 8 日
- 筆記
数组排序算法
数组排序算法是一个经典的算法问题，这类排序算法非常多，比如我们熟知的冒泡排序、插入排序、快速排序等算法。这篇文章主要说一下五种排序算法：
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 希尔排序
排序方式是从小到大排列。
还需要一个交换函数，它很有用，它接收一个数组，两个数组的索引，通过索引交换对应元素的位置，在排序算法中会多次用到：
function swap(array: any[], a: number, b: number): void{ var temp = array[a]; array[a] = array[b]; array[b] = temp; }
1. 冒泡排序
冒泡排序的思路是：比较所有相邻的两个项，如果第一个比第二个大，则交换它们。
代码：
function bubbleSort<T>(array: T[]): T[]{ var len: number = array.length; for(let i = 0;i < len;i ++){ for(let j = 0;j < len - 1;j ++){ if(array[j] > array[j + 1]) // 当前值比它下一个要大就交换 swap(array, j, j + 1); } } return array; }
假如有这样一个数组：[2, 4, 7, 5, 6, 1, 3]，它第一轮（内层循环完毕一次）的冒泡排序过程为：
2 and 4: [2, 4, 7, 5, 6, 1, 3]; 4 and 7: [2, 4, 7, 5, 6, 1, 3]; 7 and 5(swap): [2, 4, 5, 7, 6, 1, 3]; 7 and 6(swap): [2, 4, 5, 6, 7, 1, 3]; 7 and 1(swap): [2, 4, 5, 6, 1, 7, 3]; 7 and 3(swap): [2, 4, 5, 6, 1, 3, 7];
一轮循环完毕后会发现，最大的元素被排到了最右端，冒泡排序的每一轮循环结束后都会有一个大的元素“冒泡”到右端，下面是每一轮的冒泡过程：
initial: [2, 4, 7, 5, 6, 1, 3]; // start: [2, 4, 5, 6, 1, 3, 7]; [2, 4, 5, 1, 3, 6, 7]; [2, 4, 1, 3, 5, 6, 7]; [2, 1, 3, 4, 5, 6, 7]; [2, 1, 3, 4, 5, 6, 7]; [1, 2, 3, 4, 5, 6, 7]; [1, 2, 3, 4, 5, 6, 7];
优化
上面的冒泡排序代码中，第二层的循环语句可以优化。
for(let i = 0;i < len;i ++){ for(let j = 0;j < len - 1;j ++){ if(array[j] > array[j + 1]) // 当前值比它下一个要大就交换 swap(array, j, j + 1); } }
每一轮循环我们都要比较相邻的两项，第一轮循环后最右边的元素变成了最大的元素，第二轮循环时就没有必要再与它做比较了（倒数第二个元素与倒数第一个元素）。而第三轮循环时，最后两个元素已经排好，也没必要在与这两个元素作比较了。因此内层循环可以写成：
// 只在前 len - 1 - i 个元素中作比较 for(let j = 0;j < len - 1 - i;j ++){ if(array[j] > array[j + 1]) // 当前值比它下一个要大就交换 swap(array, j, j + 1); }
2. 选择排序
选择排序的思路是：选择出数组中最小的一个元素，然后把它放在第一位，接着找出数组中第二小的元素将其放在第二位。
这种排序方法我们很容易能想到，在日常生活中我们可以先挑小的，最后挑选大的。在数组中如何从众多元素中选到小的元素然后放入指定的位置是个难题。
我们可以假定第一个元素就是最小的元素，然后将它与其他的元素对比，如果有其他的元素比它还要小，就把我们假定的最小元素变成这个元素，直到遍历完整个数组，最后就能找到最小的元素了，然后将最小的元素与第一个元素调换位置就 OK 了！
实现代码：
function selectionSort<T>(array: T[]): T[]{ var len = array.length; var min: number; // 因为 min 要与后面的元素作比较，因此 i 应小于 len - 1，这样 min 后面才有元素 for(let i = 0;i < len - 1;i ++){ // 让 min = i，当前 n 个元素排好之后，就不再关注这前 n 个元素了 min = i; // 假定最小的元素就是数组中还没有排序的第一个元素 for(let j = i + 1;j < len;j ++){ if(array[min] > array[j]){ // 设定的“最小”元素却比其它元素大，就把更小的元素的索引赋给 min min = j; } } // 判断 min 与 i 是不是相等，要是相等说明内层循环的条件语句没有执行 // i 与 min 相等就不需要交换了，数组索引相同嘛 if(i !== min){ swap(array, i, min); } } return array; }
判断一个排序算法是不是选择排序也很到判断，选择排序每一轮总会把最小的元素找到并排好，因此如果一个数组原来是 [2, 3, 7, 5, 1, 4]，那么它每一轮的元素顺序是：
initial: [2, 3, 7, 5, 1, 4] // start: 1: [1, 3, 7, 5, 2, 4]; // 1 与 2 交换（数组第一项就排好了，第一项不再参与排序） 2: [1, 2, 7, 5, 3, 4]; // 2 与 3 交换（数组前两项就排好了，前两项不再参与排序） 3: [1, 2, 3, 5, 7, 4]; // 3 与 7 交换（数组前三项就排好了，前三项不再参与排序） 4: [1, 2, 3, 4, 7, 5]; // 4 与 5 交换 ...... 5: [1, 2, 3, 4, 5, 7]; // 5 与 7 交换 ......
3. 快速排序
快速排序是一个很常用的排序算法，它的复杂度很小。冒泡排序、选择排序都是双层循环排序算法，它们的时间复杂度都是 O(n^2)，而快速排序的时间复杂度为 O(nlog(n))。
快速排序时间复杂度小，但其排序算法比较复杂。这里直接说一下思路，然后再解释为什么要这样做。
快速排序在排序时会选定一个元素作为 主元，在排完一轮后，我们可以把这个主元放到排序好后的位置上。也就是说通过一轮排序，我们选定的这个元素就会找到数组排好序之后相应的位置。然后我们就不用再排它了。这如何做到呢？
假如我们有这么一个数组：[6, 23, 36, 4, 29, 44, 11, 10, 66]，我们选定的主元是数组中间的元素：29。选好后，把这个主元与数组最后一个元素交换，把主元放到最后。
然后弄两个指针，一个指针指向数组最左侧，另一个指针指向主元的前一个元素。
quick-pointer
当把小于主元的元素都放到它左边，大于主元的元素都放到它右边，这样主元的位置也就确定了。
这两个指针的运动规则：首先判断左侧指针对应的值是不是小于主元，如果小于，指针就往右移动，直到移动到大于主元的位置并暂停。然后开始移动右侧的指针，知道移动到这个元素小于主元暂停。然后交换左右指针的元素。交换完后重复之前的操作，开始移动左侧指针…..
quick-swap
每次移动指针时，我们都要判断两个指针的位置,当左侧指针的索引大于等于右侧指针的索引时，就停止，说明我们已经把主元对应的位置找到了。
quick-position
然后主元与两指针指向的元素，这时就会发现，主元左侧的元素都小于等于它，主元右侧的元素都大于等于它。
交换主元
这样一个元素就确定了位置，如何把别的元素也确定出正确的位置呢？我们剩余的元素分为较小的数组，继续通过上面的方法来确定位置（可以使用递归）。快速排序运用了分而治之的思想，把复杂的长数组分割成小的数组来管理。
分而治之
选取主元
主元应如何选取呢？最简单的做法就是选择数组最右端的元素作为主元。直接选定最右端的值作为主元有可能这个值刚好是最大的元素或者最小的元素，这样效率就会降低。
另一个选定主元的方法是抽出数组的最左边的元素、中间元素、最右端的元素，然后让它们作比较，谁是中间值就让它作为主元。我们可以这么写：
// left: 最左端的索引值，right：最右端的索引值 function getMedian<T>(left: number, right: number): T{ // T 是数组中的元素 var center = Math.floor((left + right) / 2); if(array[left] > array[center]){ swap(array, left, center); // left 应比 center 值小，不然就交换 } if(array[center] > array[right]){ swap(array, center, right); } if(array[left] > array[right]){ swap(array, left, right); } // 交换完毕后，把中间的值移动到右端 // 把 center 对应的值移动到 right - 1 即可 // 这是因为经过上面交换算法之后，right 索引对应的元素一定比 center 对应的值要大 // 因此 right 就不再需要操作了，它比主元要大，本来就应在主元右端 swap(array, center, right - 1); // 返回主元 return array[right - 1]; }
整体代码：
// 最外层的函数接收数组 function quickSort<T>(array: T[]): T[]{ quick(0, array.length - 1); // 调用 quick 核心函数 function getMedian(left: number, right: number): T{ var center: number = Math.floor((left + right) / 2); // 左侧节点比中间节点值要大，需要交换 if(array[left] > array[center]){ swap(array, left, center); } // 左侧节点比右侧节点值要大，需要交换 if(array[left] > array[right]){ swap(array, left, right); } // 中间节点比右侧节点值要大，需要交换 if(array[center] > array[right]){ swap(array, center, right); } // 别忘了交换，把主元与倒数第二个元素交换 swap(array, center, right - 1); return array[right - 1]; } // 快速排序算法核心函数 function quick(left: number, right: number): void{ // quick 函数是个递归函数，需要有一个出口 if(left >= right) return; // left 等于 right 时表明 left 与 right 指向同一个元素 var provit: T = getMedian(left, right); // right - 1 是因为主元不在倒数第一的位置，而是在倒数第二的位置 var l: number = left, r: number = right - 1; if(l === r) return; // 如果 l 与 r 相等了，就不要再走下面的程序了，说明经过分割后的数组长度只有 2，getMedia 已经排好序了 while(true){ // 先加加是因为左右指针指向的第一项都不用再比了，左边第一项必定小于主元，而右边指针指向的是主元 // l 变量是用来找到左侧大于主元的索引 while(array[++ l] < provit){}; // r 变量是用来找到右侧小于主元的索引 while(array[-- r] > provit){}; if(l < r){ // 当 l 小于 r 时才做交换 swap(array, l, r); }else{ // 当 l 大于等于 r，说明 break; } } // 把主元放到正确的位置，right - 1 是主元的索引 // 之所以 l 索引的元素与主元交换 // 是因为 l 指向左侧第一个大于主元的元素 // 交换后主元左侧的元素就都是小于等于主元的了 swap(array, l, right - 1); // 递归，主元把数组分割成了两部分，将这两部分进行排序（除了主元之外，现在的 l 就指向主元） quick(left, l - 1); quick(l + 1, right); } return array; }
说一下 quick 函数中，if(l === r) return; 的含义。考虑这么一个数组：[2, 4, 7, 5, 6, 1, 3]。通过上面的代码可以知道，经过 getMedain 函数交换后，变成了下面的顺序：
// 3 是主元 [2, 4, 7, 1, 6, 3, 5]
如果去掉 if(l === r) 的判断语句。第一轮排序的结果将是（3 被放入正确的位置）：
[2, 1, 7, 4, 6, 3, 5] // 3 与 7 交换 [2, 1, 3, 4, 6, 7, 5]
然后分割数组，3 左侧就被分成了 [2, 1] 两个元素的数组。然后对这个数组排序，经过 getMedain 函数排序后，这个数组将是已经排好的（在 getMedain 函数中，center 将等于 0，最后的 swap(array, center, right – 1); 其实就是自己交换自己），如果不加 if(l === r) 做判断，就会走下面的循环，然后就会把本来排好序的 [1, 2] 又交换成 [2, 1]。
上面的方法比较麻烦，也可以不做比较，直接将数组的最后一项作为主元：
function quickSort<T>(array: T[]): T[]{ sort(0, array.length - 1); function sort(left: number, right: number){ if(left >= right) return; var l = left, r = right, pivot = array[r]; //把所有比主元小的数放在左边大的数放在右边 while(l < r){ while(l < r && array[l] <= pivot) l ++; // 将较大的值放在右边，如果没有比主元大的数就是将自己赋值给自己（i 等于 j） array[r] = array[l]; while(r > l && array[r] >= pivot) r -- ; // 将较小的值放在左边，如果没有找到比主元小的数就是将自己赋值给自己（i 等于 j） array[l] = array[r]; } // 将主元放至中央位置完成一次循环（这时候 j 等于 i ） array[l] = pivot; sort(left, l - 1); sort(l + 1, right); } return array; }
4. 插入排序
插入排序的思路：假定数组的第一项已经排好，我们从第二项开始，如果第二项元素比第一项元素要小，两者交换；然后开始排列数组的第三项，第三项会与前两项作比较，它是应插入第二项之前呢，还是插入第一项之前呢，还是原地不动（说明它比前两项都大）？以此类推，第四项会与前面三项作比较。
实现代码：
function insertionSort<T>(array: T[]): T[]{ var len = array.length; var temp: T; // 临时保存数组中的元素 for(let i = 1;i < len;i ++){ let j = i; // j 是为下面的 while 循环服务的 temp = array[i]; // 先保存当前的元素 // j > 0，不然 j - 1 没有意义 while(j > 0 && array[j - 1] > temp){ // 如果当前的元素（temp）比它之前的元素（j - 1）要小 // 就把前面的元素赋给当前元素，相当于把前面的元素后移 array[j] = array[j - 1]; j -= 1; // 别忘了 j --，继续与 temp 作比较 } // 比较完后，把临时保存的元素插入 array[j] = temp; } return array; }
在插入排序算法中，每一趟排序左侧都会“冒”出比较小的元素，但不一定是最小的。以数组 [3, 5, 1, 4, 2] 为例：
initail: [3, 5, 1, 4, 2]; // start: [3, 5, 1, 4, 2]; // 第一趟，元素 5 比前面的任何元素都要大； [1, 3, 5, 4, 2]; // 第二趟，元素 1 比前面的任何元素都小（插入到最左侧）； [1, 3, 4, 5, 2]; // 第三趟，元素 4 要比前面的 5 小，插入到 5 之前； [1, 2, 3, 4, 5]; // 第四趟：元素 2 与前面元素比较，它被插入到元素 1 之后。
5. 希尔排序
希尔排序是插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。在上面的插入排序中，有不好的一点，假如最小的元素却在数组的最右端，那么它就要把前面的元素一个一个都移动，最终插入到最左侧，这显然是很耗时的，希尔排序就是为了优化这样的情况。
希尔排序的原理：首先确定一个增量，一般这个增量的初始值是数组长度的一半。增量表示原始数组要分成几份（5 份），每一份中相邻元素之间的索引相差 5。
shell-gap
被分成五份，分别是：(2,6,10) (7,3) (4,11) (1,9) (8,5)
如果分成三份，则是：
分三组
分别是：(2,1,3,5) (7,8,11,10) (4,6,9)
这样不太好看，可以看成类似向量的形式，两两一组：
(2,1) (7,8) (4,6) (1,3) (8,11) (6,9) (3,5) (11,10)
例如：
原数组：[2, 7, 4, 1, 8, 6, 3, 11, 9, 5, 10]; 增量：5 分组：(2,6) (7,3) (4,11) (1,9) (8,5) (6,10); 即：(2,6,10) (7,3) (4,11) (1,9) (8,5) // 5 组 // 排序： 第一对：2 和 6 不需要交换； 第二对：7 和 3 需要交换：[2, 3, 4, 1, 8, 6, 7, 11, 9, 5, 10]; 第三对：4 和 11 不需要交换； 第四对：1 和 9 不需要交换； 第五对：8 和 5 需要交换：[2, 3, 4, 1, 5, 6, 7, 11, 9, 8, 10]; 第六对：6 和 10 不需要交换； --------------------------------------------------------- 增量变成 5 / 2 == 2 分组：(2,4) (3,1) (4,5) (1,6) (5,7) (6,11) (7,9) (11,8) (9,10) 即：(2,4,5,7,9,10) (3,1,6,11,8) // 两组 // 排序（只说一下需要交换的组）： 第二对：3 和 1 交换：[2, 1, 4, 3, 5, 6, 7, 11, 9, 8, 10]; 第八对：11 和 8 交换：[2, 1, 4, 3, 5, 6, 7, 8, 9, 11, 10]; 11 和 8 是属于第二组，对调完之后，还要判断 8 之前的元素有没有大于它的（3,1,6 都比它小，因此不需要交换） ---------------------------------------------------------- 增量：2 / 2 == 1 分组：(2,1) (1,4) (4,3) (3,5) (5,6) (6,7) (7,8) (8,9) (9,11) (11,10) 即：(2,1,4,3,5,6,7,8,9,11,10) // 一组 // 排序（只说一下需要交换的组）： 第三对：2 和 1 交换：[1, 2, 4, 3, 5, 6, 7, 8, 9, 11, 10]; 第三对：4 和 3 交换：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10]; // 交换完之后，继续判断 3 之前的元素有没有比它大的，显然没有 最后一对：11 和 10 交换：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]; // 交换完之后，继续判断 10 之前的元素有没有比它大的，显然没有 // 排好啦
代码实现：
function shellSort<T>(array: T[]): T[]{ let len = array.length; // 设定增量 var gap = Math.floor(len / 2); // 增量最小等于 1，也就是普通的插入排序的增量 while (gap > 0) { for (var i = gap; i < len; i++) { var j = i - gap; // j 最小等于 0 while (j >= 0 && array[j] > array[gap + j]) { swap(array, j, gap + j); j -= gap; } } gap = Math.floor(gap / 2); } return array; }
如果把 gap 替换成 1，不再有最外层循环，其实就是一个普通的插入排序（增量是 1）。设置增量可以减少交换次数，在希尔排序中，可以将两个距离很远的元素直接交换而不需要一个一个的移动，到最后 gap 变成 1 时，需要移动的元素就变得很少了。你可以试验一下，在最内层循环中都打印一下数组，会发现希尔排序要比插入排序的交换次数少。
对比
左边是插入排序，右边是希尔排序。
