JavaScript实现快速排序(Quicksort)

2018-07-11 03:57:03来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主 东尼·霍尔(C. A. R. Hoare)于1960时提出来的。
 
 
快速排序"的思想很简单,整个排序过程只需要三步:
  (1)在数据集之中,选择一个元素作为"基准"(pivot)。
  (2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。
  (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
 
举例来说,现在有一个数据集{85, 24, 63, 45, 17, 31, 96, 50},怎么对其排序呢?
  第一步,选择中间的元素45作为"基准"。(基准值可以任意选择,但是选择中间的值比较容易理解。)
  第二步,按照顺序,将每个元素与"基准"进行比较,形成两个子集,一个"小于45",另一个"大于等于45"。
  第三步,对两个子集不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
 
按照之前的步骤,定义一个quickSort函数:
var quickSort = function(arr) { //参数是一个数组
  if (arr.length <= 1) { return arr; } //检查数组的元素个数,如果小于等于1,就返回。
  var pivotIndex = Math.floor(arr.length / 2); //选择"基准"(pivot),并将其与原数组分离,再定义两个空数组,用来存放一左一右的两个子集。
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var 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));
};
 
 
 
实现上面动画:
 
算法思路:
  1. 从数列中挑出一个元素,称为 “基准”(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出 之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;
 
实现代码:
 
function quickSort(arr, left, right) { 
  var len = arr.length,
  partitionIndex,
  left = typeof left != 'number' ? 0 : left,
  right = typeof right != 'number' ? len - 1 : right;
 
 
  if (left < right) {
  partitionIndex = partition(arr, left, right);
  quickSort(arr, left, partitionIndex-1);
  quickSort(arr, partitionIndex+1, right);
  }
  return arr;
}
function partition(arr, left ,right) { // 分区操作
  var pivot = left,                // 设定基准值(pivot)
    index = pivot + 1;
  for (var i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index++;
    }
  }
  swap(arr, pivot, index - 1);
   return index-1;
}
 
function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
    --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
    ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}
 
function quickSort2(arr, low, high) {
  if (low < high) {
  let pivot = partition2(arr, low, high);
  quickSort2(arr, low, pivot - 1);
  quickSort2(arr, pivot + 1, high);
  }
  return arr;
}
 
参考来源:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md
http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:JavaScript正则表达式练习

下一篇:使用闭包的方式实现一个累加函数 addNum