再写一次快排
快速排序基于分治法的思想,每次划分后让枢轴左边的全部小于等于它,右边的大于等于它
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 协议》,转载必须注明作者和本文链接