div js 排序 分析 gpo 中位数 urn parse body function
终于到了传说中的快速排序算法了,快速排序的思想和归并排序一样,都是采用分治思想,不同之处在于归并每次将数组一分为二,最后将小的数组进行比较,合并为大数组.快排是每次找一个主元,也就是基准数,按照这个基准数,把小于基准数的数放左边,大于基准数的数放右边,通过基准数来分组实现排序.所以快排的很重要一步就是选择主元,主元选取的是否合适直接影响到算法的效率.我的方法是每次从子数组中三个数(首,尾,中),取他们的中位数作为主元,分析到此结束,直接上 code
function quickSort(arr,left,right){
if(right-left<=1){
return arr;
}
else{
var l=left,r=right,m=parseInt((r+l)/2);
var pivot,cup;
if(arr[l]>arr[m]){
cup = arr[m];
arr[m] = arr[l];
arr[l] = cup;
}
if(arr[m]>arr[r]){
cup = arr[m];
arr[m] = arr[r];
arr[r] = cup;
}
if(arr[l]>arr[m]){
cup = arr[m];
arr[m] = arr[l];
arr[l] = cup;
}
pivot = arr[m];
cup = arr[r-1];
arr[r-1] = arr[m];
arr[m] = cup;
var i=0,j=r-2;
while(i<j){
while(arr[i]<pivot){
i++;
}
while(arr[j]>pivot){
j--;
}
if(i<=j){
cup = arr[i];
arr[i] = arr[j];
arr[j] = cup;
i++;
j--;
}
}
cup = arr[i];
arr[i] = arr[r-1];
arr[r-1] = cup;
quickSort(arr,l,i-1);
quickSort(arr,i,r);
return arr;
}
}
哈哈,比较简单粗暴,其实可以把交换位置的部分封装成一个函数的,在此就不赘言了.快排属于非稳定算法,时间平均时间复杂度为 O(nlogn); 在处理大量随机数的排序时,表现很好的.
js 排序算法 05--快速排序
来源: http://www.bubuko.com/infodetail-2472694.html