2022-09-20算法00
请注意,本文编写于 614 天前,最后修改于 614 天前,其中某些信息可能已经过时。

快速排序

快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

代码实现:

function quickSort(array, start, end) {

  let length = array.length;

  // 如果不是数组或者数组长度小于等于1,直接返回,不需要排序 
  if (!Array.isArray(array) || length <= 1 || start >= end) return;

  let index = partition(array, start, end); // 将数组划分为两部分,并返回右部分的第一个元素的索引值

  quickSort(array, start, index - 1); // 递归排序左半部分
  quickSort(array, index + 1, end); // 递归排序右半部分
}


function partition(array, start, end) {

  let pivot = array[start]; // 取第一个值为枢纽值,获取枢纽值的大小


  // 当 start 等于 end 指针时结束循环
  while (start < end) {

    // 当 end 指针指向的值大等于枢纽值时,end 指针向前移动
    while (array[end] >= pivot && start < end) {
      end--;
    }

    // 将比枢纽值小的值交换到 start 位置
    array[start] = array[end];

    // 移动 start 值,当 start 指针指向的值小于枢纽值时,start 指针向后移动
    while (array[start] < pivot && start < end) {
      start++;
    }

    // 将比枢纽值大的值交换到 end 位置,进入下一次循环
    array[end] = array[start];
  }

  // 将枢纽值交换到中间点
  array[start] = pivot;

  // 返回中间索引值
  return start;
}

这一种方法是填空法,首先将第一个位置的数作为枢纽值,然后 end 指针向前移动,当遇到比枢纽值小的值或者 end 值等于 start 值的时候停止,然后将这个值填入 start 的位置,然后 start 指针向后移动,当遇到比枢纽值大的值或者 start 值等于 end 值的时候停止,然后将这个值填入 end 的位置。反复循环这个过程,直到 start 的值等于 end 的值为止。将一开始保留的枢纽值填入这个位置,此时枢纽值左边的值都比枢纽值小,枢纽值右边的值都比枢纽值大。然后在递归左右两边的的序列。

当每次换分的结果为含 ⌊n/2⌋⌈n/2⌉−1 个元素时,最好情况发生,此时递归的次数为 logn,然后每次划分的时间复杂度为 O(n),所以最优的时间复杂度为 O(nlogn)。一般来说只要每次换分都是常比例的划分,时间复杂度都为 O(nlogn)

当每次换分的结果为 n-10 个元素时,最坏情况发生。划分操作的时间复杂度为 O(n),递归的次数为 n-1,所以最坏的时间复杂度为 O(n²)。所以当排序序列有序的时候,快速排序有可能被转换为冒泡排序。

快速排序的空间复杂度取决于递归的深度,所以最好的时候为 O(logn),最坏的时候为 O(n)

快速排序的平均时间复杂度为 O(nlogn) ,最坏时间复杂度为 O(n²) ,空间复杂度为 O(logn) ,不是稳定排序。

详细资料可以参考: 《图解排序算法(五)之快速排序——三数取中法》 《关于快速排序的四种写法》 《快速排序的时间和空间复杂度》 《快速排序最好,最坏,平均复杂度分析》 《快速排序算法的递归深度》

本文作者:前端小毛

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!