复习一下几种排序算法。
我本想只写归并和快排，学习下分治思想，又觉得文章太突兀，所以就又挖了一下基本排序的细节写在下边与你分享;
如果您正在准备面试，并对排序算法不了解，那下边的文章可以当作八股文来背诵下，在面试官面前引导节奏侃侃而谈;
如果您已经对这些排序算法烂熟于心，那您也可以带着批判的眼光看一下，也来写一篇“wz版本的快速排序是错的”。

基本排序

  • 冒泡
  • 选择
  • 插入

分治

  • 快排
  • 归并

一、测试数据

  1. const array = [...new Array(100).keys()].reverse();
  2. console.log('array: ', array); // print 100,99,98,...,0

把这个逆序的100个元素的数组转为正序的

二、冒泡

const array = [...new Array(100).keys()].reverse();
console.log('array: ', array);

let count1 = 1
function sort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        //两两比较，如果前一个比后一个大，则交换位置。
        for (let j = 0; j < arr.length - 1 - i; j++) {
            count1++
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
}
let arr1 = [...array]
sort(arr1);
console.log(arr1, `共执行: ${count1} 次`);// 共执行4950次

基本介绍
  • 两层循环；
  • 两两比较，如果前一个比后一个大，则交换位置；

  • 从后向前排序，后边的先排好，第一遍冒泡，最大的会到最后边去。

    时间复杂度

  • 冒泡排序的时间复杂度是；

  • 外层循环用来做标识，走到第i步标志着最后的i个已经排好了；
  • 内层循环每次从0开始走，走到数组长度 - 外层循环下标位置，随着外层下标的增加而一步步减少，实际上内层循环每次走的次数是99，98 ，97，…，1；
  • 实际准确的复杂时间是关于排序 - 图1，约去常数算
  • 不受数组的元素值得影响，人人有份，非常固定，就是关于排序 - 图2

    三、选择排序

    ```javascript const array = […new Array(100).keys()].reverse(); console.log(‘array: ‘, array);

let count2 = 1 function selectSort(arr) { for (let i = 0; i < arr.length; i++) { //设置当前范围最小值和索引 let min = arr[i]; let minIndex = i; //在该范围选出最小值 for (let j = i + 1; j < arr.length; j++) { count2++ if (min > arr[j]) { min = arr[j]; minIndex = j; } } //将最小值插入,并将原来位置的最小值删除 arr.splice(i, 0, min); arr.splice(minIndex + 1, 1); } } let arr2 = […array] selectSort(arr2); console.log(arr2, 共执行: ${count2} 次);// 共执行4950次

非常符合人类直觉的一种排序方法<br />你要排序一堆高度不同的书本，把他们都扔到地上，每次捡起来里边最小的那本放到书架上，直到所有书都被放大到书架上，这就是选择排序。

- 从前向后，前边的是先排好序的
<a name="QoUe5"></a>
##### 时间复杂度
几乎和冒泡一模一样，处理外层i标识的是前边i个已经排好了外

- ；
- 外层循环用来做标识，走到第i步标志着前边的i个已经排好了；
- 内层循环每次从0开始走，走到数组长度 - 外层循环下标位置，随着外层下标的增加而一步步减少，实际上内层循环每次走的次数是99，98 ，97，...，1；
- 实际准确的复杂时间是![](https://cdn.nlark.com/yuque/__latex/1803fa399b0273049cd7036720bbc9ca.svg#card=math&code=%5Cfrac%7B%28n%5E2%2Bn%29%7D%7B2%7D&id=fvW8b)，约去常数算；
- 不受数组的元素值得影响，人人有份，非常固定，就是![](https://cdn.nlark.com/yuque/__latex/1803fa399b0273049cd7036720bbc9ca.svg#card=math&code=%5Cfrac%7B%28n%5E2%2Bn%29%7D%7B2%7D&id=ZMkk6)；

<a name="MkFqg"></a>
#### 四、插入排序
```javascript
// const array = [...new Array(100).keys()].reverse();
const array = [...new Array(100).keys()];
console.log('array: ', array);

let count3 = 1
function insertSort(arr) {
    //假设第0元素是有序序列，第1元素之后是无序的序列。从第1元素开始依次将无序序列的元素插入到有序序列中
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) {
            //取出无序序列中需要插入的第i个元素
            let temp = arr[i];
            //定义有序中的最后一个位置
            let j = i - 1;
            arr[i] = arr[j];
            //比较大小，找到插入的位置
            while (j >= 0 && temp < arr[j]) {
                count3++
                arr[j + 1] = arr[j];
                j--;
            };
            //插入
            arr[j + 1] = temp;
        }
    }
}
let arr3 = [...array]
insertSort(arr3)
console.log(arr3, `共执行: ${count3} 次`); // print 100, 4950

冒泡排序和选择排序基本就是人类正常直觉的实现，在工程中说实话没啥用；
但同样归属于基本排序的插入排序以及插入排序的思想可以解决很多的问题；
通过上边代码可以看出

  • 插入排序受数组内元素值得影响，数组内值越有序越快
  • 如果已经是有序的那只有外层走一遍就好了，内部while永远不成立，当前值一直比下一个值小

时间复杂度
  • 最差是和冒泡、选择一样，数组内的元素是一个逆序的要转为正序的，内部while走的次数是随着外部forloop下标移动增加 1，2，3，…99，因为下一个元素总是比前边所有元素都小，所以要一直对比走到第一个的位置；
  • 最好的情况就是元素已经是排序好的了，那只有外层走一遍就好了，内部while一次也不走，因为下一个已经比当前最头上这个最大的还要大了；
  • 所以时间复杂度在关于排序 - 图3到关于排序 - 图4之间，很恐怖啦已经，最慢的形态与冒泡和选择一样效率，最快只需要关于排序 - 图5。

五、用插排思想解决问题

LC第一题：两数之和
https://leetcode-cn.com/problems/two-sum/

  1. 先排个正序
  2. while判断nums[i] < target && nums[i] + nums[i] > target
  3. 向前找

比不上哈希表解法，但也比暴力两层要好吧

LC春季赛第一题
https://leetcode-cn.com/problems/4xy4Wx/
数据集大，暴力超时

  1. 先排个正序
  2. 如果当前元素和第一个最小的元素加起来比target小，while向前滑，一直找当前元素与当前滑到的元素加起来比target小的位置，把前边的全加进去，包括自己。 ```javascript var purchasePlans = function (nums, target) { const mod = 1000000007 let res = 0 nums = nums.sort((a, b) => a - b) for (let i = 1; i < nums.length; i++) {
     if (nums[i] + nums[0] > target) break
 let left = i - 1
 while (left > -1) {
     if (nums[left] + nums[i] <= target) {
         res += (left + 1 || 1)
         break
     }
     left--
 }
    } return res % mod

};



<a name="eAzH1"></a>
#### 六、分治(divide and conquer)

- 排序100个元素用朴素方法需要扫4950
- 排序两个元素，最多只需要两次操作，扫一下两个元素，如果大则交换，小则不动；排序五十个组两个元素，只需要50 * 2次扫描

就像排序一样，现实中的很多问题并不是随着数量的增加复杂度线性增长的<br />2，4，6，8，10，12，14，16，18，20，22，24，26，28，30……<br />而是像排序一样是指数式增长的<br />2，4，8，16，32，64，128，256，512，1024，2048，4096，8196，16384，32468……
<a name="mkZcP"></a>
##### 分治思想
我们把一个大问题拆成一堆小问题，逐一解决再拼回去，这就是分治思想；<br />分治思想可以解决很多问题包括斐波那契数列等的经典问题；<br />而就像排序这样的复杂性指数式增长的问题，用分治算法还能高效的降低复杂度。
<a name="xcqvh"></a>
##### let’s get it
让我们去窥看一下排序的分治思想的经典算法吧——快排和归并

<a name="RQdpT"></a>
#### 七、快速排序
快速排序的基本思想就是上边所说

- 指数增长问题，用分治降低复杂度
<a name="MC1uG"></a>
##### 快排基本实现步骤

1. 分割（partition）：把这个大数组分割为两个小数组，左边的元素都小于枢轴（pivot），右边的都大于或等于枢轴。
1. 合并
```javascript
const array = [...new Array(100).keys()].reverse();
console.log('array: ', array);

let count4 = 1
function quickSort(arr) {
    //如果数组长度小于等于1，则返回数组本身
    if (arr.length <= 2) {
        if (arr.length <= 1) return arr
        if (arr[0] > arr[1]) [arr[0], arr[1]] = [arr[1], arr[0]]
        return arr
    };
    //定义中间值的索引
    const mid = Math.floor(arr.length / 2);
    //取到中间值，并且从原数组值扣去这个中间值，避免对左小右大拆分的影响
    const temp = arr.splice(mid, 1)[0];
    //定义左右部分数组
    const left = [];
    const right = [];
    for (let i = 0; i < arr.length; i++) {
        count4++
        //如果元素比中间值小，那么放在左边，否则放右边
        if (arr[i] < temp) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([temp], quickSort(right));
}

const res = quickSort(array)
console.log(res, `共执行: ${count4} 次`) //print 共执行： 454 次

这是一个基本的快排实现
基本就是：在数组里面挑一个 pivot 出来，然后把数组里面比 pivot 小的数放一堆，比 pivot 大的放另一堆，各自排序后再合并结果。
现实使用的快排在此基础上做了众多的优化，但加上优化之后的算法是很难向新手解释清楚的。
我所知道的优化有

  • 三值中值取枢轴，不过让我再在上边代码上加上这一层，已经到我现在思维的极限了；
  • 。。。没了，我就只知道这个

快排的逼太容易撕了，就这样吧
如何看待文章《面试官：阮一峰版的快速排序完全是错的》？
https://www.zhihu.com/question/276746146

时间复杂度
  • 关于排序 - 图6，背下好了。

八、用快排思想解决问题

k大自己看吧
https://leetcode-cn.com/problems/smallest-k-lcci/solution/zui-xiao-kge-shu-by-leetcode-solution-o5eg/

九、归并排序

我已经很累了，不想再写了，但归并排序还有一个有意思的小问题，合并两个有序数组。
归并和快排思想差不多，也是分治
不过归并不找枢轴分大小，而是把一个大数组拆成一堆小数组然后小数组排序后再用合并两个有序数组的方法合并成原来的大数组。

基本步骤
  1. 递归/迭代拆成小数组
  2. 小数组排序
  3. 合并有序数组（LC：第88题 https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/）

归并排序更直观的符合分治思想
网上复制一个归并算法

作者：developer1024
链接：https://zhuanlan.zhihu.com/p/124356219
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// 归并排序（Java-递归版）
static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, result, start1, end1);
    merge_sort_recursive(arr, result, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        result[k++] = arr[start1++];
    while (start2 <= end2)
        result[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = result[k];
}

public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    merge_sort_recursive(arr, result, 0, len - 1);
}

归并与快排区别
  • 快排只能递归，数据大就爆栈，所以使用也比较受限，现实中内置在编程语言中的排序算法是timSort，一种改进了归并和插排的算法。以后写。
  • 归并有个大常数，所以综合比快排慢些。

https://www.zhihu.com/question/292486713

  • 归并不是原地算法，比较占内存

[

](https://www.zhihu.com/search?type=content&q=%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F)

—- END —-

2021年5月15日
in njlib