vlambda博客
学习文章列表

function quickSort(arr) { _sort(arr, 0, arr.length - 1);}
function _sort(arr, l, r) { if (l >= r) return;
 var p = _random(l, r); _swap(arr, l, p);
 var lt = l, // 小于p部分的最后1个元素的索引 gt = r + 1, // 大于p部分的第1个元素的索引 i = l + 1; // 遍历所用索引
 // 当 i 与 gt 的位置未重叠时 while (i < gt) { // 如果当前元素小于p，则交换arr[i]与当前lt + 1处元素的位置 if (arr[i] < arr[l]) { lt++; _swap(arr, i, lt); i++; }     // 如果当前元素大于p，则交换arr[i]与当前gt - 1处元素的位置 else if (arr[i] > arr[l]) { gt--; _swap(arr, i, gt); }    // 如果当前元素等于p，i++（即等于p部分中的元素+1） else { i++; } }
  // 完成本次排序前，交换p与小于p部分的最后1个元素 _swap(arr, l, lt);
 _sort(arr, l, lt - 1); _sort(arr, gt, r);}
function _swap(arr, i, j) { var t = arr[i]; arr[i] = arr[j]; arr[j] = t;}
function _random(from, to) { return Math.floor(Math.random() * (to - from + 1) + from);}