1.概念
快速排序
快速排序，听这个名字就能想到它排序速度比较快方法，是一种分治思想，现在各种语言中自带的排序库很多使用的都是快速排序。快速排序是一种原地排序，只需要一个很小的栈作为辅助空间，空间复杂度为O(log2n)，适合在数据集比较大的时候使用。时间复杂度比较复杂，最好的情况是O(n)，最差的情况是O(n2)，所以平时说的O(nlogn)，为其平均时间复杂度。
2.基本思想
随机找出一个数，可以随机取，也可以取固定位置，一般是取第一个或最后一个称为基准，然后就是比基准小的在左边，比基准大的放到右边，如何放做，就是和基准进行交换，这样交换完左边都是比基准小的，右边都是比较基准大的，这样就将一个数组分成了两个子数组，然后再按照同样的方法把子数组再分成更小的子数组，直到不能分解为止。
3.举例说明
假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。
1.分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字8。
2.首先哨兵j开始出动，哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。
3.现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下。6 1 2 5 9 3 4 7 10 8。
4. 第一次交换结束。接下来开始哨兵j继续向左挪动。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下。6 1 2 5 4 3 9 7 10 8 。
5. 第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。3 1 2 5 4 6 9 7 10 8 。
6. 到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。
第一轮结束后，对原基准点左右，递归排序
4、代码示例
function quickSort(arr, begin, end) { //递归出口 if(begin >= end) return; var l = begin; // 左指针 var r = end; //右指针 var temp = arr[begin]; //基准数，这里取数组第一个数 //左右指针相遇的时候退出扫描循环 while(l < r) { //右指针从右向左扫描，碰到第一个小于基准数的时候停住 while(l < r && arr[r] >= temp) r --; //左指针从左向右扫描，碰到第一个大于基准数的时候停住 while(l < r && arr[l] <= temp) l ++; //交换左右指针所停位置的数 [arr[l], arr[r]] = [arr[r], arr[l]]; } //最后交换基准数与指针相遇位置的数 [arr[begin], arr[l]] = [arr[l], arr[begin]]; //递归处理左右数组 quickSort(arr, begin, l - 1); quickSort(arr, l + 1, end); } var arr = [2,3,4,1,5,6] quickSort(arr, 0, 5); console.log(arr)
5、时间复杂度
最好 n
最坏 n^2
平均 nlogn
属于不稳定性算法