数据结构与算法之排序: 快速排序 (Javascript版)

排序

• 排序：把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例)

快速排序

• 该排序属于 分治 策略
• 将一个问题分解为两个问题来计算，计算完成之后，就会得到子任务的解，这些解不是最终问题的解，还需要merge起来

算法实现

1 ) 简单版本，消耗内存

function quickSort(arr: number[]) {
	// 1.核心函数
	const qsFn = (arr: number[]) => {
	   if (arr.length <= 1) return arr;
	   const pivotIndex: number = Math.floor(arr.length / 2);
	   const pivot: number = arr.splice(pivotIndex, 1)[0];
	   const left: number[] = [];
	   const right: number[] = [];
	   arr.forEach(item => {
	   	if (item < pivot) left.push(item);
	   	if (item > pivot) right.push(item);
	   });
	　　return qsFn(left).concat([pivot], qsFn(right));
	}
	// 2.执行核心函数
	const res: number[] = qsFn(arr); // res 用于返回最终结果
	arr.splice(0, arr.length, ...res); // 将最终排好序的结果赋值给原数组arr
	// 3. 可以有返回值
	return arr; // 可以用于返回值
};

const arr = [15, 4, 23, 52, 1];
quickSort(arr);
console.log(arr); //  [1, 4, 15, 23, 52]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 这里是 多开了一些存储空间，而且有递归, 一般生产环境不会使用这类内存占用较大的算法
• 思路
  • 分区：从数组中，任意选择一个基准，所有比基准小的元素放在基准前面，比基准大的元素放在基准后面
    • 此时，基准已经找到自己合适的位置了
  • 递归：递归地对基准前后的子数组进行分区
    • 在子数组中找到一个基准，并把它放到合适的位置
    • 一直递归下去，基准前后子数组最后的长度都是1，不用再递归了，此时子数组已经排序好了
    • 等所有子数组都排序好，我们整个快排结束
• 时间复杂度: O(nlogn)
  • 递归时间: logn, 每次劈成2半
  • 分区时间：n，for循环，找出比基准小和大的元素

2 ）基于指针版本, 优化内存

const quickSort = (array: number[], replace: boolean) => {
	// 1. 核心函数
	const qsFn = (arr: number[], left: number = 0, right: number = arr.length - 1) => {
		//如果左边的索引大于等于右边的索引说明整理完毕
		if (left >= right) return;
		let low: number = left; // 低指针
		let high: number = right; // 高指针
		const pivot: number = arr[high]; // 取无序数组最后一个数为基准值
		// 把所有比基准值小的数放在左边, 大的数放在右边
		while (low < high) {
		  // 找到一个比基准值大的数交换
		  while (low < high && arr[low] <= pivot) low ++;
		  arr[high] = arr[low]; // 将较大的值放在右边，如果没有比基准值大的数就是将自己赋值给自己
		  // 找到一个比基准值小的数交换
		  while (high > low && arr[high] >= pivot) high --;		  
		  arr[low] = arr[high]; // 将较小的值放在左边，如果没有找到比基准值小的数就是将自己赋值给自己
		}
		arr[high] = pivot; // 将基准值放至中央位置完成一次循环
		qsFn(arr, low, high - 1) // 将左边的无序数组重复上面的操作
		qsFn(arr, high + 1, right) // 将右边的无序数组重复上面的操作
	}
	// 2. 准备执行核心函数, 多加一项配置 (是否影响原数组)
	const result = replace ? array : array.concat(); // 基于配置，为了保证这个函数是纯函数拷贝一次数组, 这样不影响原array数组
	qsFn(result);
	return result; // 配置replace为true则可以不用返回值
}

const arr = [15,4,23,52,1];
quickSort(arr, true); // 不加第二个参数, 不会影响原 arr
console.log(arr); //  [1, 4, 15, 23, 52]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 这个优化比较好，可用于生产环境
• 思路
  • 基于高低指针，不断比较指针，满足条件进行交换
  • 也是基于递归实现，但不占用过多内存

总结

• 比冒泡，选择，插入性能都要好, 分而治之
• Chrome 曾经用快排作为sort排序的方法