function QuickSort(a, from, to) { // Insertion sort is faster for short arrays. if (to - from <= 22) { InsertionSort(a, from, to); return; } var pivot_index = $floor($random() * (to - from)) + from; var pivot = a[pivot_index]; // Pre-convert the element to a string for comparison if we know // it will happen on each compare anyway. var pivot_key = (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot); // Issue 95: Keep the pivot element out of the comparisons to avoid // infinite recursion if comparefn(pivot, pivot) != 0. a[pivot_index] = a[from]; a[from] = pivot; var low_end = from; // Upper bound of the elements lower than pivot. var high_start = to; // Lower bound of the elements greater than pivot. // From low_end to i are elements equal to pivot. // From i to high_start are elements that haven‘t been compared yet. for (var i = from + 1; i < high_start; ) { var element = a[i]; var order = Compare(element, pivot_key); if (order < 0) { a[i] = a[low_end]; a[low_end] = element; i++; low_end++; } else if (order > 0) { high_start--; a[i] = a[high_start]; a[high_start] = element; } else { // order == 0 i++; } } QuickSort(a, from, low_end); QuickSort(a, high_start, to); }
基本思想：
通过一趟循环将要排序的数据分割成独立的两部分。
其中一部分的所有数据都比另外一部分的所有数据都要小。
然后再按此方法对这两部分数据分别进行快速排序。
整个排序过程可以递归进行，以此达到整个数据变成有序序列。
操作流程：
接着是取分界值，在传入的起始索引和截至索引的差值中任取一个索引，该索引对应的值即为分界值，保存副本
需要注意的是，key不应该在循环时被循环出来和自身比较
创建两个变量记录已交换位置的索引。
一个初值等于截至索引，每交换一个值到右边，则该变量减-1。最后该变量和截至索引即为递归函数的from和to。
另一个初值等于开始索引，每交换一个值到左边，则该变量加1。最后开始索引和该变量即为递归函数的from和to。
然后从起始索引加+1开始循环
根据比较结果的不同，分别对大于0，小于0的数组值进行分边。
比较结果小于0，放右边。右边的逻辑：（升降序是通过比较函数来控制）
比较结果大于0，放左边。左边的逻辑：
值相同时，令i++。
循环结束后，数组已被边界值分成了两部分，每部分的起始、截至索引都以记录。
接着把这两部分按照上述逻辑进行操作。循环往复。
以上都是在原数组中操作，并未引入新数组。
源码在对未传入比较函数的情况下，对key 进行了toString处理，保证行为的一致性。
源码对比较函数进行了封装。在未传入比较函数时，对两个参数进行了toString处理。
代码：
function quickSort(a, from, to) { // 递归退出条件，当传入的起始索引和截至索引差值小于2时，此时对应的数据只有一个。已经无需比较 if (to - from < 2) return; const key_index = Math.floor(Math.random() * (to - from)) + from; // key的索引，值的范围在起始索引和截至索引中任取 const key = a[key_index]; // key 用于比较 // 需要注意的是，key不应该在循环时被循环出来和自身比较 // 这里交换数组起始位置值和key值。然后循环从起始位置+1开始 a[key_index] = a[from]; a[from] = key; let high_start = to; // 数组分边后其中一边的开始索引 let low_end = from; // 数组分边后另一边的截至索引 // 循环从起始位置+1开始，判断条件中high_start，每交换一个值到右边，该值就减1 for (let i = from + 1; i < high_start;) { let el = a[i]; // 当前值副本 let result = a[i] - key; // 比较。可封装成比较函数，实现升降序 if (result < 0) { /** * 右边。把high_start对应的值赋给a[i]。 * 此时a[i]已经变了，需要重新比较。故不能i++。把当前副本el赋给a[high_start]。 * a[high_start]已经是比较过的值。踢出循环 */ high_start--; a[i] = a[high_start]; a[high_start] = el; } else if (result > 0) { /** * 左边。 * from是数组起始索引，如果循环从from开始。 * 则每次需要把值放左边时，会出现i = low_end的情况，导致交换失败。 * 故循环从from + 1开始。 * 当循环至边界索引key_index时，该索引对应的是数组起始值。 * 由此数组每个值都与key进行了比较，然后被分边。 */ a[i] = a[low_end]; a[low_end] = el; low_end++; i++; } else { i++; } } // 此时递归，传入起始索引和截至索引，对两部分数据的进行上述操作 quickSort(a, from, low_end) // 左边组数据 quickSort(a, high_start, to) // 右边组数据 }
原文：https://www.cnblogs.com/caimuguodexiaohongmao/p/11867659.html