快速排序是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法。
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序基于冒泡、递归分治。他在大数据情况下是最快的排序算法之一，平均事件复杂度很低而且前面的系数很小，在大量随机输入的情况下最坏情况出现的概率是极小的。
最坏时间复杂度：O($n^2$) 当选择的基准值为最大值或最小值时 稳定性：不稳定 平均时间复杂度：O(n*$log_2$n)
阮一峰版 内存占用较多
function quickSort(arr) { if(arr.length <= 1) { return arr; } let pivotIndex = Math.floor(arr.length / 2); let pivot = arr.splice(pivotIndex, 1)[0];// let pivot = arr.splice(pivotIndex, 1); 3 < [9] //true let left = []; let right = []; for(let i = 0; i < arr.length; i++) { if(arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat(pivot, quickSort(right));} 上面简单版本的缺点是，它需要Ω(n)的额外存储空间，也就跟归并排序一样不好。额外需要的存储器空间配置，在实际上的实现，也会极度影响速度和高速缓存的性能。
真正的快排
按照中的原地(in-place)分区版本，实现快速排序方法如下：
function quickSort(arr) { function swap(arr, i, k) { let temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } // 数组分区，左小右大 function partition(arr, left, right) { let storeIndex = left; let pivot = arr[right]; // 直接选最右边的元素为基准元素 for(let i = left; i < right; i++) { if(arr[i] < pivot) { swap(arr, storeIndex, i); storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置 } } swap(arr, storeIndex, right); // 将基准元素放置到最后的正确位置上 return storeIndex; } function sort(arr, left, right) { if(left > right) { return; } let storeIndex = partition(arr, left, right); sort(arr, left, storeIndex - 1); sort(arr, storeIndex + 1, right); } sort(arr, 0, arr.length - 1); return arr;} 利用分治法来处理快排，主要的思想是：
- 在数据集之中，选择一个元素作为”基准”（pivot）。
- 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是数组最终排序后它的位置。
- 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
步骤：
首先，把基准元素移到結尾（如果直接选择最后一个元素为基准元素，那就不用移动）；
然后从左到右（除了最后的基准元素），循环移动小于等于基准元素的元素到数组的开头，每次移动 storeIndex 自增 1，表示下一个小于基准元素将要移动到的位置；循环结束后 storeIndex 所代表的的位置就是基准元素的所有摆放的位置；所以最后将基准元素所在位置（这里是 right）与 storeIndex 所代表的的位置的元素交换位置。完成一次分区；tips：这里为什么要把基准元素放到数组的最后一个元素的位置上，是为了方便对数组中除了基准元素以外的所有元素进行遍历，并方便在找到基准元素的排序位置 storeIndex 后进行两两交换。倘若不如此，需要将该基准元素从原数组中取出来（类似阮一峰版做法arr.splice(pivotIndex, 1)）,循环遍历完所有除基准元素外的元素后，找到基准元素的最后排序位置 storeIndex后，需要将基准元素插入进来（用到插入排序的思想），显然这种方式较为复杂。
所以一般选取了除数组最后一个元素为基准元素后，会将该基准元素换到最后一个元素上；这里便直接选取数组中最后一个元素为基准元素，对整个数组进行分区操作[0~arr.length-1].当然也可以只对数组中某一连续数组元素进行分区，即只对数组中这一小部分元素进行排序sort(arr, start, end);。
function quickSort(arr, start, end) { function swap(arr, i, k) { let temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } // 数组分区，左小右大 function partition(arr, left, right) { let storeIndex = left; let pivot = arr[right]; // 直接选最右边的元素为基准元素 for(let i = left; i < right; i++) { if(arr[i] < pivot) { swap(arr, storeIndex, i); storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置 } } swap(arr, storeIndex, right); // 将基准元素放置到最后的正确位置上 return storeIndex; } function sort(arr, left, right) { if(left > right) { return; } let storeIndex = partition(arr, left, right); sort(arr, left, storeIndex - 1); sort(arr, storeIndex + 1, right); } sort(arr, start, end); return arr;}quickSort([3,7,8,5,2,1,9,5,4], 3, 7) // 只对部分元素排序