快速排序?

快速排序（Quicksort）是一种高效的排序算法，它的平均时间复杂度为 O(n log n)，是目前最快的通用排序算法之一。

快速排序的基本步骤是：

1. 选择一个元素作为枢轴（pivot）。
2. 将所有小于枢轴的元素放在枢轴的左边，所有大于枢轴的元素放在枢轴的右边。
3. 对枢轴左边和右边的子序列递归应用快速排序算法。

快速排序的关键在于选择合适的枢轴。不同的枢轴选择方法会影响快速排序的性能。常见的枢轴选择方法包括：

• 随机选择：随机选择一个元素作为枢轴。
• 中位数选择：选择中位数作为枢轴。
• 最小值选择：选择最小值作为枢轴。

demo

代码

function quickSort(arr) {
	if (arr.length <= 1) {
		return arr;
	}
	const pivot = arr[0];
	const left = [];
	const 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).concat(pivot, quickSort(right));
}

console.log(quickSort([5, 2, 8, 3, 1, 6, 4]));

这个函数接受一个数组 arr 作为输入，返回一个排序后的数组。它的工作原理是：

1. 如果数组长度小于或等于 1，则返回原数组（因为已经排序）。
2. 选择第一个元素作为枢轴 (pivot）。
3. 创建两个空数组 left 和 right。
4. 遍历数组（从第二个元素开始），如果当前元素小于或等于枢轴，则将其添加到 left 数组，否则添加到 right 数组。
5. 递归调用 quickSort 函数对 left 和 right 数组进行排序。
6. 将排序后的 left 数组、枢轴和排序后的 right 数组拼接起来，返回结果。

可视化

优缺点

快速排序的特点是：

• 高效：快速排序的平均时间复杂度为 O(n log n)，是目前最快的通用排序算法之一。
• 稳定：快速排序是稳定排序算法，不会改变相同元素的相对顺序。
• 适合大数据集：快速排序适合大数据集的排序。

快速排序的缺点是：

• 不稳定：快速排序在最坏情况下可能会出现不稳定的现象。
• 需要额外空间：快速排序需要额外的空间来存储递归函数的调用栈。

快速排序可以用于以下场景：

• 大数据集排序：快速排序适合大数据集的排序。
• 需要高效率的场景：快速排序适合需要高效率的场景。
• 需要稳定排序的场景：快速排序适合需要稳定排序的场景。

参考

• github
• 在线排序