Skip to main content

快速排序/Quick Sort ✓

快速排序​

快速排序（Quick Sort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤​

  1. 从数列中挑出一个元素，称为“基准”（pivot），

  2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

  3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

  4. 递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

/**
* 快速排序
* 取第一个值，作为中间值，与余下的一次比较
* 比中间值小的，放左边数组
* 比中间值大的，放右边数组
* 递归调用，直到每个数组只剩一个元素，返回该数组
*/
export  const quickSort = (arr) => {
    if(arr.length <=1){
        return arr
    }
    let mid = arr[0];
    let left =[];
    let right =[];
    for (let i =1; i<arr.length; i++){
        if(arr[i]<mid){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([mid],quickSort(right));
}
Try in StackBlitz

空间复杂度​

O(logn)

时间复杂度​

O(nlogn)

是否是稳定排序​

否