十大排序算法-分治思想-归并排序&&快速排序(js实现)

秒速五厘米 2022-11-18 13:57 103阅读 0赞

### 文章目录 ###

*  一、分治思想
 *  二、归并排序
 *   *  1.思路分析
     *  2.排序过程演示
     *  3.代码实现
     *  4.复杂度分析
 *  三、快速排序
 *   *  1.思路分析
     *  2.排序过程演示
     *  3.编码实现
     *  4.复杂度分析

# 一、分治思想 #

利用分治思想解决问题，我们一般分三步走：

*  分解子问题
 *  求解每个子问题
 *  合并子问题的解，得出大问题的解

归并排序和快速排序就是用了这种思想。

# 二、归并排序 #

## 1.思路分析 ##

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

## 2.排序过程演示 ##

例：`[8, 7, 6, 5, 4, 3, 2, 1]`

1.  首先重复地分割数组，整个分割过程如下：
    
        [8, 7, 6, 5,| 4, 3, 2, 1]
        [8, 7,| 6, 5,| 4, 3,| 2, 1]
        [8,| 7,| 6,| 5,| 4,| 3,| 2,| 1]
2.  接下来开始尝试解决每个子问题。将规模为1的子数组两两合并为规模为2的子数组，合并时确保有序
    
        [7, 8,| 5, 6,| 3, 4,| 1, 2]
3.  继续将规模为2的按照有序原则合并为规模为4的子数组：
    
        [5, 6, 7, 8,| 1, 2, 3, 4]
4.  最后将规模为4的子数组合并为规模为8的数组：
    
        [1, 2, 3, 4, 5, 6, 7, 8]

## 3.代码实现 ##

一直重复一个过程 **分割、合并**，涉及重复的可以采用递归。

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

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))
        }
    }

## 4.复杂度分析 ##

*  我们把每一次切分+归并看做是一轮。对于规模为 n 的数组来说，需要切分 log(n) 次，因此就有 log(n) 轮。
 *  每一轮中，切分动作都是小事情，只需要固定的几步,因此单次切分对应的是常数级别的时间复杂度 O(1)。
    
        // 计算分割点
        const mid = Math.floor(len / 2)    
        // 递归分割左子数组，然后合并为有序数组
        const leftArr = mergeSort(arr.slice(0, mid)) 
        // 递归分割右子数组，然后合并为有序数组
        const rightArr = mergeSort(arr.slice(mid,len))
 *  再看合并，单次合并的时间复杂度为 O(n)。

所以，时间复杂度就是 **O(nlog(n))**。

# 三、快速排序 #

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

## 1.思路分析 ##

快速排序会将原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。

## 2.排序过程演示 ##

例子：`[5, 1, 3, 6, 2, 0, 7]`

1.  首先要做的事情就选取一个基准值。基准值的选择有很多方式，这里我们选取数组中间的值,左右指针分别指向数组的两端。
    
        [5, 1, 3, 6, 2, 0, 7]
         ↑       基准      ↑
2.  接下来我们要做的，就是先移动左指针，直到找到一个不小于基准值的值为止；然后再移动右指针，直到找到一个不大于基准值的值为止。
    
        [5, 1, 3, 6, 2, 0, 7]
                 基准   ↑
                  ↑
3.  交换 6 和 0，同时两个指针共同向中间走一步：
    
        [5, 1, 3, 0, 2, 6, 7]
                     ↑ 基准
                     ↑
4.  此时 2 比 6 小，故右指针不动，左指针继续前进：
    
        [5, 1, 3, 0, 2, 6, 7]
                     ↑ 基准
                   right↑
                       left
5.  此时右指针所指的值不大于 6，左指针所指的值不小于 6，故两个指针都不再移动。此时我们会发现，对于左指针所指的数字来说，**它左边的所有数字都比它小，右边的所有数字都比它大**（这里注意也可能存在相等的情况）。由此我们就能够以左指针为轴心，划分出一左一右、一小一大两个子数组：
    
        [5, 1, 3, 0, 2]   
        [6, 7]
6.  针对两个子数组，重复执行以上操作，直到数组完全排序为止。这就是快速排序的整个过程。

## 3.编码实现 ##

// 快速排序入口
    function quickSort(arr, left = 0, right = arr.length - 1) {
      // 定义递归边界，若数组只有一个元素，则没有排序必要
      if(arr.length > 1) {
          // lineIndex表示下一次划分左右子数组的索引位
          const lineIndex = partition(arr, left, right)
          // 如果左边子数组的长度不小于1，则递归快排这个子数组
          if(left < lineIndex-1) {
            // 左子数组以 lineIndex-1 为右边界
            quickSort(arr, left, lineIndex-1)
          }
          // 如果右边子数组的长度不小于1，则递归快排这个子数组
          if(lineIndex<right) {
            // 右子数组以 lineIndex 为左边界
            quickSort(arr, lineIndex, right)
          }
      }
      return arr
    }
    // 以基准值为轴心，划分左右子数组的过程
    function partition(arr, left, right) {
      // 基准值默认取中间位置的元素
      let pivotValue = arr[Math.floor(left + (right-left)/2)]
      // 初始化左右指针
      let i = left
      let j = right
      // 当左右指针不越界时，循环执行以下逻辑
      while(i<=j) {
          // 左指针所指元素若小于基准值，则右移左指针
          while(arr[i] < pivotValue) {
              i++
          }
          // 右指针所指元素大于基准值，则左移右指针
          while(arr[j] > pivotValue) {
              j--
          }
    
          // 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序
          if(i<=j) {
              swap(arr, i, j)
              i++
              j--
          }
    
      }
      // 返回左指针索引作为下一次划分左右子数组的依据
      return i
    }
    
    // 快速排序中使用 swap 的地方比较多，我们提取成一个独立的函数
    function swap(arr, i, j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
    }

更好理解的写法：

## 4.复杂度分析 ##

快速排序的时间复杂度的好坏，是由基准值来决定的。

*  **最好**时间复杂度：它对应的是这种情况——我们每次选择**基准值**，都刚好是当前子数组的**中间数**。这时，可以确保每一次分割都能将数组分为两半，进而只需要递归 log(n) 次。这时，快速排序的时间复杂度分析思路和归并排序相似，最后结果也是 **O(nlog(n))。**
 *  **最坏**时间复杂度：每次划分取到的都是当前数组中的**最大值/最小值**。大家可以尝试把这种情况代入快排的思路中，你会发现此时快排已经退化为了冒泡排序，对应的时间复杂度是 **O(n^2)。**
 *  **平均**时间复杂度： **O(nlog(n))**

[本文链接https://blog.csdn.net/qq\_39903567/article/details/115673107][https_blog.csdn.net_qq_39903567_article_details_115673107]

[https_blog.csdn.net_qq_39903567_article_details_115673107]: https://blog.csdn.net/qq_39903567/article/details/115673107