当前位置:Gxlcms > JavaScript > JavaScript实现快速排序的算法思想

JavaScript实现快速排序的算法思想

时间:2021-07-01 10:21:17 帮助过:62人阅读

这篇文章主要介绍了关于JavaScript实现快速排序的算法思想,有着一定的参考价值,现在分享给大家,有需要的朋友可以参考一下

目前,最常见的排序算法大概有七八种,其中"快速排序"(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;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,更多相关内容请关注PHP中文网!

相关推荐:

js数组随机排序的方法

js将任意元素移动到指定位置

以上就是JavaScript实现快速排序的算法思想的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行