快速排序（Quick Sort常考）

认识

快速排序（Quick Sort）是一种经典的排序算法，广泛应用于实际工程中。主要特点是利用分治法来排序，能够在大多数情况下实现 <font style="color:rgb(36, 41, 47);">O(n log n) 的时间复杂度。

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

/**
 * @description 快速排序
 * @author hovinghuang
 */

/**
 * 快速排序 (splice)
 * @param arr 
 * @returns 
 */
function quickSort1(arr: number[]): number[] {
    const len = arr.length
    if (len === 0) return arr

    const midIndex = Math.floor(len / 2)
    const midValue = arr.splice(midIndex, 1)[0]

    const left: number[] = []
    const right: number[] = []

    // 注意： splice 会修改原数组，所以用 arr.length
    for (let i = 0; i < arr.length; i++) {
        const n = arr[i]
        if (n < midValue) {
            left.push(n)
        } else {
            right.push(n)
        }
    }
    return quickSort1(left).concat([midValue], quickSort1(right))
}

/**
 * 快速排序 (slice)
 * @param arr 
 * @returns 
 */
 function quickSort2(arr: number[]): number[] {
    const len = arr.length
    if (len === 0) return arr

    const midIndex = Math.floor(len / 2)
    const midValue = arr.slice(midIndex, midIndex + 1)[0]

    const left: number[] = []
    const right: number[] = []

    for (let i = 0; i < len; i++) {
        if (i === midIndex) continue
        const n = arr[i]
        if (n < midValue) {
            left.push(n)
        } else {
            right.push(n)
        }
    }
    
    return quickSort2(left).concat([midValue], quickSort2(right))
}

// 功能测试
const testArr3 = [3, 2, 5, 1, 8, 7]
console.info('quickSort2:', quickSort2(testArr3))

基本概念

快速排序的核心思想是通过“分治法”将问题拆解为更小的子问题来递归解决。

1. 分治法：快速排序每次通过选择一个元素作为基准（pivot），将数组分为两部分。左边部分的元素比基准小，右边部分的元素比基准大。然后，分别对左右两部分递归地进行排序。
2. 选择基准元素：可以选择第一个元素、最后一个元素或中间元素作为基准，或者通过随机选择基准来避免最坏情况。

工作过程

1. 选择基准元素（Pivot）：从待排序的数组中选择一个元素作为基准（可以是第一个元素、最后一个元素，或通过其他方法选择）。
2. 划分操作：将数组分为两部分。左边部分的元素都小于等于基准元素，右边部分的元素都大于基准元素。基准元素在划分过程中会被放到正确的位置。
3. 递归排序：对基准元素左边和右边的子数组继续进行快速排序。

例子

假设我们要对以下数组进行排序：

[6, 3, 8, 2, 7, 5, 1, 4]

1. 选择基准元素：假设选择第一个元素 6 作为基准。
2. 划分操作：将数组划分为左边部分（小于等于6）和右边部分（大于6）。

左边：[3, 2, 5, 1, 4]
基准：[6]
右边：[8, 7]

1. 对左右子数组递归进行快速排序：
   • 左边 [3, 2, 5, 1, 4] 选择 3 为基准，再进行划分。
   • 右边 [8, 7] 选择 8 为基准，再进行划分。

最终，经过递归排序后，得到排序后的数组：

[1, 2, 3, 4, 5, 6, 7, 8]

时间复杂度

• 最优情况：当每次基准元素将数组均匀分割时，时间复杂度为 O(n log n)，其中 n 是数组的长度。
• 平均情况：在大多数实际情况下，快速排序的平均时间复杂度也是 O(n log n)。
• 最坏情况：当选择的基准总是数组中的最大或最小元素（例如，数组已经排好序或完全逆序），导致每次分割只有一个元素时，时间复杂度退化为 O(n^2)。

快速排序的空间复杂度

快速排序的空间复杂度是 O(log n)，这主要是由递归调用栈所占用的空间决定的。每次划分时，递归深度最多为 log n。

如果使用原地排序（即直接在原数组上修改，而不使用额外数组），空间复杂度可以降到 O(log n)。但如果每次划分时创建新的数组，空间复杂度则是 O(n)。

优缺点

优点：

1. 高效性：在大多数情况下，快速排序的性能非常优越，时间复杂度为 O(n log n)，适用于大规模数据排序。
2. 原地排序：快速排序是一种原地排序算法，不需要额外的存储空间（除了递归栈）。
3. 分治法：通过递归和分治法来处理复杂问题，适用于大规模数据集。

缺点：

1. 最坏情况性能差：当数据已经接近有序或是逆序时，快速排序的性能会退化为 O(n^2)。这个问题可以通过随机选择基准元素或使用三数取中的方法来减少。
2. 不稳定排序：与冒泡排序、插入排序等稳定排序算法不同，快速排序会改变相等元素的顺序。

优化策略

1. 基准选择优化：
   • 随机选择基准：通过随机选择基准元素，可以避免在已经排序或逆序的数组上出现最坏情况。
   • 三数取中法：选择数组首、尾和中间三个元素的中位数作为基准，可以减少最坏情况的概率。
2. 递归深度限制：
   • 当子数组的长度较小时（如小于10），可以切换为其他排序算法，如插入排序，因为插入排序对小规模数据的排序更高效。
3. 尾递归优化：
   • 在递归过程中，可以选择递归较小的子数组，然后迭代处理较大的子数组，减少递归的深度。

快速排序核心

1. 理解分治法：核心是分治法的思想。通过选择基准将问题划分成两个子问题，并通过递归解决它们。
2. 实现多种方式：尝试实现快速排序的不同版本，例如使用递归实现、使用随机基准、三数取中法等。
3. 分析时间复杂度：理解快速排序的时间复杂度分析，尤其是最坏情况和平均情况的区别，以及如何优化。
4. 与其他排序算法比较：将快速排序与其他排序算法（如冒泡排序、选择排序、归并排序等）比较其优缺点和场景。

写法

基础写法

// 解法1 快速排序
    function quickSort(arr) {
        if (arr.length <= 1) {
            return arr
        }
        // 选择基准元素，这里我们选择第一个元素作为基准
        let pivot = arr[0];
        let left = [];
        let right = [];
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] <= pivot) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return [...quickSort(left), pivot,...quickSort(right)]
    }
    // 测试数据
    let arr = [6, 3, 8, 2, 7, 5, 1, 4];
    console.log("排序前：", arr);
    let sortedArr = quickSort(arr);
    console.log("排序后：", sortedArr);

整个过程

选择一个基准元素（pivot），这里选择数组的第一个元素
将小于等于基准元素的元素放到左数组
将大于基准元素的元素放到右数组
递归地对左数组和右数组进行同样的排序
最后将排序后的左数组、基准元素和排序后的右数组合并

执行过程：
对于数组 [6, 3, 8, 2, 7, 5, 1, 4]
第一次选择6为基准，分成 [3, 2, 5, 1, 4] 和 [8, 7]
然后对 [3, 2, 5, 1, 4] 选择3为基准，分成 [2, 1] 和 [5, 4]
对 [2, 1] 选择2为基准，分成 [1] 和 []
对 [5, 4] 选择5为基准，分成 [4] 和 []
对 [8, 7] 选择8为基准，分成 [7] 和 []
然后按照相同的方式递归处理其他子数组


输出：
排序前：[6, 3, 8, 2, 7, 5, 1, 4]
排序后：[1, 2, 3, 4, 5, 6, 7, 8]

优化-使用随机基准选择

添加注释以后我们更加容易看出添加基准以后，进行的步数大概平均下来在25步左右

// 写法优化1-使用随机基准选择
   let stepCount = 0; // 全局步数计数器
   console.log(`步骤 ${stepCount}: 进入`);
   function quickSort(arr) {
      if (arr.length <= 1) {
          return arr
      }
      stepCount++; // 基准选择计数
      // 选择基准元素，这里我们选择第一个元素作为基准
      const randomIndex = Math.floor(Math.random() * arr.length);
      [arr[0], arr[randomIndex]] = [arr[randomIndex], arr[0]]; // 交换到第一个位置
      let pivot = arr[0];
      let left = [];
      let right = [];
      for (let i = 1; i < arr.length; i++) {
          stepCount++; // 循环迭代计数
          console.log(`步骤 ${stepCount}: 检查元素 ${arr[i]}, 当前基准: ${pivot}`);
          if (arr[i] <= pivot) {
              left.push(arr[i]);
          } else {
              right.push(arr[i]);
          }
      }
      stepCount++; // 递归调用计数

      return [...quickSort(left), pivot,...quickSort(right)]
  }

优化-使用三数取中法选择基准

这个时候我们优化下来，在14步左右

// 优化2-使用三数取中法选择基准（带步数计算）
     let stepCount = 0; // 全局步数计数器
     function quickSort(arr) {
        if (arr.length <= 1) {
            return arr
        }
        stepCount++; // 基准选择计数
        // 选择基准元素，这里我们选择第一个元素作为基准
        const mid = Math.floor(arr.length / 2);

        // 比较三个数
        if (arr[0] > arr[mid]) {
            [arr[0], arr[mid]] = [arr[mid], arr[0]];
        }
        if (arr[0] > arr[arr.length - 1]) {
            [arr[0], arr[arr.length - 1]] = [arr[arr.length - 1], arr[0]];
        }
        if (arr[mid] > arr[arr.length - 1]) {
            [arr[mid], arr[arr.length - 1]] = [arr[arr.length - 1], arr[mid]];
        }
        let pivot = arr[mid];;
        let left = [];
        let right = [];
        for (let i = 1; i < arr.length; i++) {
            if (i === mid) continue; // 跳过基准元素
            stepCount++; // 循环迭代计数
            console.log(`步骤 ${stepCount}: 检查元素 ${arr[i]}, 当前基准: ${pivot}`);
            if (arr[i] <= pivot) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        stepCount++; // 递归调用计数
        return [...quickSort(left), pivot,...quickSort(right)]
}

优化3-使用原地分区

这里一定得去看看原理分区的概念才能理解这个原地分区，其实就是不借助于额外存储进行位置的不断交换

// 优化3-使用原地分区
    let stepCount = 0; // 全局步数计数器
    function quickSort(arr, left = 0, right = arr.length - 1) {
        if (left < right) {
            stepCount++; // 递归调用计数
            const mid = Math.floor((left + right) / 2);
            // 比较三个数
            if (arr[left] > arr[mid]) {
                [arr[left], arr[mid]] = [arr[mid], arr[left]];
            }
            if (arr[left] > arr[right]) {
                [arr[left], arr[right]] = [arr[right], arr[left]];
            }
            if (arr[mid] > arr[right]) {
                [arr[mid], arr[right]] = [arr[right], arr[mid]];
            }

            [arr[mid], arr[right]] = [arr[right], arr[mid]];
            const pivot = arr[right];
            let i = left - 1;
            for (let j = left; j < right; j++) {
                stepCount++; // 循环迭代计数
                if (arr[j] <= pivot) {
                    i++;
                    [arr[i], arr[j]] = [arr[j], arr[i]];
                }
            }
            [arr[mid], arr[right]] = [arr[right], arr[mid]];
            const partitionIndex = i + 1;
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    // 测试数据
    let arr = [6, 3, 8, 2, 7, 5, 1, 4];
    console.log("排序前：", arr);
    let sortedArr = quickSort(arr);
    console.log("排序后：", sortedArr);
    console.log("总步数：", stepCount);

优化4-添加小数组插入排序优化

这个时候我们又能感觉到步数明显确实加快了

// 优化4-添加小数组插入排序优化
     let stepCount = 0; // 全局步数计数器
     function quickSort(arr, left = 0, right = arr.length - 1) {

         // 对小数组使用插入排序
        if (right - left < 10) {
            insertionSort(arr, left, right);
            stepCount++;
            return arr;
        }

        if (left < right) {
            stepCount++; // 递归调用计数
            const mid = Math.floor((left + right) / 2);
            // 比较三个数
            if (arr[left] > arr[mid]) {
                [arr[left], arr[mid]] = [arr[mid], arr[left]];
            }
            if (arr[left] > arr[right]) {
                [arr[left], arr[right]] = [arr[right], arr[left]];
            }
            if (arr[mid] > arr[right]) {
                [arr[mid], arr[right]] = [arr[right], arr[mid]];
            }
            [arr[mid], arr[right]] = [arr[right], arr[mid]];
            const pivot = arr[right];
            let i = left - 1;
            for (let j = left; j < right; j++) {
                stepCount++; // 循环迭代计数
                if (arr[j] <= pivot) {
                    i++;
                    [arr[i], arr[j]] = [arr[j], arr[i]];
                }
            }
             [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
            const partitionIndex = i + 1;
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }


    // 辅助函数：插入排序（带步数计算）
    function insertionSort(arr, left, right) {
        for (let i = left + 1; i <= right; i++) {
            const key = arr[i];
            let j = i - 1;
            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
        return arr;
    }

优化5-尾递归优化的原理

优化前（普通递归）：

复制 插入 新文件

factorial(3)
→ 3 * factorial(2)
→ 3 * (2 * factorial(1))
→ 3 * (2 * 1)
→ 3 * 2
→ 6

优化后（尾递归）：

复制 插入 新文件

factorial(3, 1)
→ factorial(2, 3)
→ factorial(1, 6)
→ 6

这里我们进行一下尾递归优化的写法，核心就是下面的代码

优点：避免递归深度过大，从而引发栈溢出

传统的快速排序

quickSort(arr, left, partitionIndex - 1);  // 递归处理左子数组
quickSort(arr, partitionIndex + 1, right); // 递归处理右子数组

尾递归

 // 先处理较小的子数组，减少递归深度
  if (partitionIndex - left < right - partitionIndex) {
      quickSort(arr, left, partitionIndex - 1);
      left = partitionIndex + 1;
  } else {
      quickSort(arr, partitionIndex + 1, right);
      right = partitionIndex - 1;
  }

尾递归优化完整

 // 优化5 - 尾递归优化
    let stepCount = 0; // 全局步数计数器
    function quickSort(arr, left = 0, right = arr.length - 1) {

        // 对小数组使用插入排序
        if (right - left < 10) {
            insertionSort(arr, left, right);
            stepCount++;
            return arr;
        }

        while (left < right) {
            stepCount++; // 递归调用计数
            const mid = Math.floor((left + right) / 2);

            // 比较三个数
            if (arr[left] > arr[mid]) {
                [arr[left], arr[mid]] = [arr[mid], arr[left]];
            }
            if (arr[left] > arr[right]) {
                [arr[left], arr[right]] = [arr[right], arr[left]];
            }
            if (arr[mid] > arr[right]) {
                [arr[mid], arr[right]] = [arr[right], arr[mid]];
            }

            // 将基准放到right位置
            [arr[mid], arr[right]] = [arr[right], arr[mid]];
            const pivot = arr[right];


            let i = left - 1;
            for (let j = left; j < right; j++) {
                stepCount++; // 循环迭代计数
                if (arr[j] <= pivot) {
                    i++;
                    [arr[i], arr[j]] = [arr[j], arr[i]];
                }
            }
            [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];


            // 
            const partitionIndex = i + 1;


            // 先处理较小的子数组，减少递归深度
            if (partitionIndex - left < right - partitionIndex) {
                quickSort(arr, left, partitionIndex - 1);
                left = partitionIndex + 1;
            } else {
                quickSort(arr, partitionIndex + 1, right);
                right = partitionIndex - 1;
            }

        }
        return arr;
    }


    // 辅助函数：插入排序（带步数计算）
    function insertionSort(arr, left, right) {
        stepCount++;
        console.log(`步骤 ${stepCount}: 进入insertionSort, 范围: [${left}, ${right}]`);

        for (let i = left + 1; i <= right; i++) {
            stepCount++;
            console.log(`步骤 ${stepCount}: 处理元素arr[${i}](${arr[i]})`);
            const key = arr[i];
            let j = i - 1;

            stepCount++;
            while (j >= left && arr[j] > key) {
                stepCount++;
                console.log(`步骤 ${stepCount}: 移动arr[${j}]到arr[${j + 1}]`);
                arr[j + 1] = arr[j];
                j--;
            }

            stepCount++;
            arr[j + 1] = key;
            console.log(`步骤 ${stepCount}: 将${key}放到位置${j + 1}，数组变为:`, arr);
        }

        stepCount++;
        console.log(`步骤 ${stepCount}: 插入排序完成`);
        return arr;
    }