排序 - 《数据结构和算法》

基础排序算法
进阶排序算法
- 归并排序
- 快排
  - 思路分析
  - 编码实现

基础排序算法

冒泡

插入排序

选择排序

进阶排序算法

归并排序

时间复杂度就是 O(nlog(n))

思路分析

归并排序是对分治思想的典型应用，它按照如下的思路对分治思想“三步走”的框架进行了填充：

分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。
合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组
真实排序过程演示
下面我们基于归并排序的思路，尝试对以下数组进行排序：

首先重复地分割数组，整个分割过程如下：
首次分割，将数组整个对半分：

二次分割，将分割出的左右两个子数组各自对半分：

三次分割，四个子数组各自对半分后，每个子数组内都只有一个元素了：

接下来开始尝试解决每个子问题。将规模为1的子数组两两合并为规模为2的子数组，合并时确保有序，我们会得到这样的结果：

继续将规模为2的按照有序原则合并为规模为4的子数组：

最后将规模为4的子数组合并为规模为8的数组：

整个数组就完全有序了。

编码实现

通过上面的讲解，我们可以总结出归并排序中的两个主要动作：

分割
合并

这两个动作是紧密关联的，分割是将大数组反复分解为一个一个的原子项，合并是将原子项反复地组装回原有的大数组。整个过程符合两个特征：

重复（令人想到递归或迭代）
有去有回（令人想到回溯，进而明确递归这条路）

因此，归并排序在实现上依托的就是递归思想。

function mergeSort(arr) {
    const len = arr.length
    // 处理边界情况
    if(len <= 1) {
        return arr
    }   
    // 计算分割点
    const mid = Math.floor(len / 2)    
    // 递归分割左子数组，然后合并为有序数组
    const leftArr = mergeSort(arr.slice(0, mid)) 
    // 递归分割右子数组，然后合并为有序数组
    const rightArr = mergeSort(arr.slice(mid,len))  
    // 合并左右两个有序数组
    arr = mergeArr(leftArr, rightArr)  
    // 返回合并后的结果
    return arr
}
function mergeArr(arr1, arr2) {  
    // 初始化两个指针，分别指向 arr1 和 arr2
    let i = 0, j = 0   
    // 初始化结果数组
    const res = []    
    // 缓存arr1的长度
    const len1 = arr1.length  
    // 缓存arr2的长度
    const len2 = arr2.length  
    // 合并两个子数组
    while(i < len1 && j < len2) {
        if(arr1[i] < arr2[j]) {
            res.push(arr1[i])
            i++
        } else {
            res.push(arr2[j])
            j++
        }
    }
    // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
    if(i<len1) {
        return res.concat(arr1.slice(i))
    } else {
        return res.concat(arr2.slice(j))
    }
}

快排

快速排序在基本思想上和归并排序是一致的，仍然坚持“分而治之”的原则不动摇。区别在于，快速排序并不会把真的数组分割开来再合并到一个新数组中去，而是直接在原有的数组内部进行排序。

思路分析

快速排序会将原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
这个描述对初学者来说可能会比较抽象，我们直接通过真实排序的过程来理解它：

时间复杂度

最好时间复杂度 O(nlog(n))
最坏时间复杂度O(n^2)
平均时间复杂度：O(nlog(n))
编码实现
```javascript const quickSort = (arr, left = 0, right = arr.length - 1) => { if (arr.length > 1) { const lineIndex = partition(arr, left, right); if (left < lineIndex - 1) {
```
quickSort(arr, left, lineIndex - 1);
```
} if (right > lineIndex) {
```
quickSort(arr, lineIndex, right);
```
} } return arr; };

排序

基础排序算法

冒泡

插入排序

选择排序

进阶排序算法

归并排序

思路分析

真实排序过程演示

编码实现

快排

思路分析

编码实现