再写一次快排

快速排序基于分治法的思想,每次划分后让枢轴左边的全部小于等于它,右边的大于等于它

function devide(a, l, r)
{
    if(l == r) return a[l];
    let pivot = a[l];
    let i = l;
    let j = r;

    while(i < j){
        while(i < j && a[j] >= pivot) j--;
        if(i < j){
            a[i] = a[j];
            i++;
        }

        while(i < j && a[i] <= pivot) i++;
        if(i < j){
            a[j] = a[i];
            j--;
        }
    }

    a[i] = pivot;

    if(i > l) devide(a, l, i-1);
    if(i < r) devide(a, i+1, r);
    return a;
}

function qsort(a)
{
    return devide(a, 0, a.length-1);
}

console.log(qsort([1, -1, 3, 7, 0, 10]));
console.log(qsort([1, -1, 3, 7, 1, 10]));

思考:
快速排序之所以是不稳定的排序,就在于交换的过程中相等元素后面可能被换到前面去

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!