快速排序

2018-11-27  本文已影响0人  Jason_Shu
  1. 原理
    (1)从一个数列中选出一个「基准」
    (2)然后遍历所有元素,把所有比这个「基准」小的元素放在「基准」的左边,所有比「基准」大的元素放在「基准」的右边,如果与「基准」相等,随意放哪边。一轮分区下来,这样会是该「基础」处于整个数列的中间位置。
    (3)递归地,把小于基准值元素的子数列和大于基准值元素的子数列排序。
    (4)递归到最底部时,数列的长度只有0或者1,即本身就是排好序的。这个算法一定会结束,因为在每次的迭代中,它至少会把一个元素摆到它最后的位置去。

  2. 代码

function quickSort(arr) {
    function __quickSort__(arr, start, end) {
        if(start >= end) return;
        let key = arr[end];
        let left = start;
        let right = end - 1;
        while(left < right){
            while( arr[left] < key && left < right) left++;
            while( arr[right] > key && left < right) right--;
            [arr[left], arr[right]] = [arr[right], arr[left]];
        }
        if(arr[left] >= key) {
            [arr[left], arr[end]] = [arr[end], arr[left]];
        } else {
            left++;
        }
        __quickSort__(arr, start, left - 1);
        __quickSort__(arr, left + 1, end);
    }
    __quickSort__(arr, 0, arr.length - 1 );
    return arr;
}

参考:https://zhuanlan.zhihu.com/p/46189099

上一篇下一篇

猜你喜欢

热点阅读