Skip to content

Latest commit

 

History

History
104 lines (77 loc) · 3.67 KB

快排.md

File metadata and controls

104 lines (77 loc) · 3.67 KB

快排

快排它采用了一种分治的策略，通常称其为分治法

算法思想

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步：

  • 在数据集之中，选择一个元素作为”基准”（pivot）。

  • 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。

  • 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

代码

function partition(arr, left, right) {
  let i = left,
    j = right,
    temp = arr[left];
  while (i < j) {
    while (i < j && arr[j] > temp) {
      j--;
    }
    if (i < j) {
      arr[i] = arr[j];
      i++;
    }
    while (i < j && arr[i] < temp) {
      i++;
    }
    if (i < j) {
      arr[j] = arr[i];
      j--;
    }
    console.log(i, ' ', j, ' ', temp, arr);
  }
  arr[i] = temp;
  return i;
}

function quickSort(arr, left, right) {
  if (left < right) {
    let index = partition(arr, left, right); // 分区，找到一个基点
    quickSort(arr, left, index - 1);
    quickSort(arr, index + 1, right);
  }
  return arr;
}

var arr = [20, 40, 30, 10, 60, 50];
console.log(quickSort(arr, 0, arr.length - 1)); // [10, 20, 30, 40, 50, 60]

阮一峰老师的错误快排，可以去知乎上去吃瓜，这边我还是照样贴出来阮老师的快排代码～

function quickSort(arr) {
  if (arr.length === 0) {
    return [];
  }
  let index = Math.floor(arr.length / 2);

  let midValue = arr.splice(index, 1);

  let leftArr = [],
    rightArr = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < midValue) {
      leftArr.push(arr[i]);
    } else {
      rightArr.push(arr[i]);
    }
  }
  return quickSort(leftArr).concat(midValue, quickSort(rightArr));
}

var arr = [20, 40, 30, 10, 60, 50];
console.log(quickSort(arr));

时间复杂度

最好的情况，时间复杂度为 O(nlog2n), 最差的情况，时间复杂度为 O(n²) ,平均复杂度为 O(nlog2n)

有没有其他方法？

快速排序也有不足之处，比如对于元素较少或接近有序的数组来说，快速排序平均性能比插入排序差。这是因为小数组信息熵相对来说比较小（特别是经过一系列的快速排序调用以后），而插入排序在数据接近有序的情况下时间复杂度接近 O(N)，再加上快速排序递归调用也会有一些性能损耗。

因此，针对于小数组的话，可以采用插入排序，如果大数组，就采用快速排序。

Java 标准库自带的排序 DualPivotQuicksort 就是这么干的，INSERTION_SORT_THRESHOLD = 47。

那有没有更好能够优化快速排序性能的方法？ 双枢轴，即将数组三切分(大于枢轴，等于枢轴，小于枢轴），为什么这样划分呢？因为对大规模数组进行排序时，数据重复的情况可能比较多，因此使用双枢轴可以有效避免相等元素之间的比较。

快排的改进主要有三种方法：小数组使用插入排序、双枢轴（快速三向切分）、划分策略优化（五取样划分）。经过优化后的快速排序算法时间复杂度可以介于 O(N) 到 O(NlogN) 之间，性能更优

推荐文章