固定算法，固定思路
- 找到中间位置 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, 效果会非常明显
