TS数据结构与算法之快速排序

固定算法，固定思路

• 找到中间位置 midValue
• 遍历数组，小与 midValue 放在 left，否则放在 right
• 继续递归。最后 concat 拼接，返回

细节

• 获取 midValue 的两种方式
• 使用 splice，会修改原数组
• 使用 slice，不会修改原数组 - 更加推荐

代码实现

方案1 splice

/**
 * 快速排序 - splice
 */
export const quickSort1 = (
  arr: number[]
): number[] => {
  if (!arr.length) return arr;

  const left: number[] = [];
  const right: number[] = [];
  const midIndex = Math.floor(arr.length / 2);
  const midValue = arr.splice(midIndex, 1)[0];

  // splice会修改数组，需要实时获取数组的大小
  for (let i = 0; i < arr.length; i ++) {
    const n = arr[i];

    if (n < midValue) {
      // 小于 midValue 放在 left
      left.push(n);
    } else {
      // 大于 midValue 放在 right
      right.push(n);
    }
  }

  return quickSort1(left).concat(
    [midValue],
    quickSort1(right)
  );
}

方案2 slice

/**
 * 快速排序 - slice
 */
 export const quickSort2 = (
  arr: number[]
): number[] => {
  const len = arr.length;
  if (!len) return arr;

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

  for (let i = 0; i < len; i ++) {
    if (i !== midIndex) {
      const n = arr[i];
  
      if (n < midValue) {
        // 小于 midValue 放在 left
        left.push(n);
      } else {
        // 大于 midValue 放在 right
        right.push(n);
      }
    }
  }

  return quickSort2(left).concat(
    [midValue],
    quickSort2(right)
  );
}

功能测试

export const quickSortFunctionalTest = () => {
  const arr = [3, 2, 1, 4, 5, 7, 8];
  const res = quickSort2(arr);
  console.info(res); // [1, 2, 3, 4, 5, 7, 8]
}

单元测试

/**
 * 快速排序单元测试
 */
import { quickSort2 } from '../src/utils/quick-sort';

describe('快速排序', () => {
  test('正常情况', () => {
    const arr = [3, 2, 1, 4, 5, 7, 8];
    const res = quickSort2(arr);
    expect(res).toEqual([1, 2, 3, 4, 5, 7, 8]);
  });

  test('有负数', () => {
    const arr = [3, 2, 1, 4, -10, 5, 7, 8];
    const res = quickSort2(arr);
    expect(res).toEqual([-10, 1, 2, 3, 4, 5, 7, 8]);
  });

  test('数组元素都一样', () => {
    const arr = [1, 1, 1, 1];
    const res = quickSort2(arr);
    expect(res).toEqual([1, 1, 1, 1]);
  });

  test('空数组', () => {
    const arr: number[] = [];
    const res = quickSort2(arr);
    expect(res).toEqual([]);
  });
});

执行 yarn jest:

PASS  tests/quick-sort.test.ts
  快速排序
    ✓ 正常情况 (2 ms)
    ✓ 有负数 (1 ms)
    ✓ 数组元素都一样
    ✓ 空数组

性能分析

时间复杂度

for 循环一次遍历时间复杂度 O(n)，二分 O(logn)，嵌套后复杂度就是 O(nlogn)。常规排序，嵌套循环，复杂度是 O(n^2)

性能测试

使用两种算法分别对10W条数据的数组排序

export const quickSortPerformanceTest = () => {
  const arr1 = [];
  for (let i = 0; i < 10 * 10000; i++) {
    arr1.push(Math.floor(Math.random() * 1000));
  }
  console.time('quickSort1');
  quickSort1(arr1);
  console.timeEnd('quickSort1');

  const arr2 = [];
  for (let i = 0; i < 10 * 10000; i++) {
    arr2.push(Math.floor(Math.random() * 1000));
  }
  console.time('quickSort2');
  quickSort2(arr1);
  console.timeEnd('quickSort2');
}

执行结果：

• quickSort1: 75.958984375 ms
• quickSort2: 76.9580078125 ms

两个算法时间几乎相同，splice 和 slice 并没有区分出来

• 排序算法本身的时间复杂度已经够高 O(n*logn)
• 外加，splice 是逐步二分之后执行的，二分会快速削减数量级
• 如果只是单独比较 splice 和 slice, 效果会非常明显