每一个从事计算机相关方向工作的同学一定听说过快速排序算法，在面试的准备过程中，快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。
快速排序算法又称划分交换排序，简称快排，是一种排序算法。在平均状态下排序n个项目需要O(nlogn)次比较，在最坏的情况下则需要O(n^2)次比较，不过这种情况并不常见。事实上呢，快速排序通常要比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。
快速排序的动画演示：
快排动画
快速排序算法采用的是分治法的思想，将一个完整的待排序的序列一分为二，分而治之，并递归的对子序列继续排序。
可以这么简单的描述快速排序的步骤：
1、从数组中随机的选择一个元素，称之为“基准” （pivot）。
2、从数组中按顺序取出元素与基准比较，如果取出的元素比基准小，则放置入基准之前的数组，而如果取出的元素比基准大，则放入基准之后的数组，如果取出的元素与基准相等，则与基准放置于同一数组中。该操作可以称之为分区（partition）操作。
3、在第一遍排序完之后，再递归的对基准之前的数组与基准之后的两个数组进行排序，直至拆分至最小的数组大小，则可视为排序完成，按照调用栈返回结果。则排序完成。
介绍完步骤之后，来看看用javaScript如何来实现快速排序：
/**
* 快速排序算法
* 最优时间复杂度 O(nlogn)
* 平均时间复杂度 O(nlogn)
* 最坏时间复杂度 O(n^2)
* 是否稳定 否
*/
class QuickSort {
sort(originalArray) {
const array = [...originalArray];
// 如果数组小于等于一个元素的时候就返回，可以理解为已经排好序
if (array.length <= 1) {
return array;
}
// 定义左右两个数组
const leftArray = [];
const rightArray = [];
// 取出第一个元素作为比较对象
const pivotElement = array.shift();
const centerArray = [pivotElement];
// 把数组切分为左中右三部分
while (array.length) {
const currentElement = array.shift();
if (currentElement === pivotElement) {
centerArray.push(currentElement);
} else if (currentElement < pivotElement) {
leftArray.push(currentElement);
} else {
rightArray.push(currentElement);
}
}
// 对左右两个数组递归排序
const leftSortedArray = this.sort(leftArray);
const rightSortedArray = this.sort(rightArray);
// 将返回的已经排好序的左中右三个数组合并 完成排序
return leftSortedArray.concat(centerArray, rightSortedArray);
}
}
// 排序测试
const array = [6, 10, 1, 9, 4, 8, 2, 7, 3, 5];
const quick = new QuickSort();
const res = quick.sort(array);
console.log(res);
最后温馨的提醒各位同学，一定要牢牢的掌握快速排序算法，直到能随意白板手写快排为止。
网友评论