快速排序,😄 - CNode技术社区

var list = [1,2,12,15,7,43,3,18,9,11,5,345,667,45,6,454,2,6,78,54,77,85,345,65,44,345,76,4,53,2,25,864,55,43,778,54,8,29,83];
var list2 = [1,2,12,15,7,43,3,18,9,11,5,345,667,45,6,454,2,6,78,54,77,85,345,65,44,345,76,4,53,2,25,864,55,43,778,54,8,29,83];
var counterA = 0,counterB = 0, counter2A = 0, counter2B = 0;
function quickSort(list,start,stop) {
 start = start||0;
 stop = stop||(list.length-1);
 var tmp = null, continueFlag = false;
 for(var indL = start,indR = stop-1; indL<indR;){
 counterA++;
 if(list[indL]<=list[stop]){
 indL++;
 continueFlag = true
 }
 if(list[indR]>=list[stop]){
 indR--;
 continueFlag = true
 }
 if(continueFlag){
 continueFlag = false;
 continue;
 }
 counterB++
 tmp = list[indL];
 list[indL] = list[indR];
 list[indR] = tmp;
 indL++;
 indR--;
 }
 if(list[indL]>list[stop]){
 counterB++
 tmp = list[indL];
 list[indL] = list[stop];
 list[stop] = tmp;
 }
 if(indL-start > 1){
 quickSort(list,start,indL);
 }
 if(stop-indL > 1){
 quickSort(list,indL,stop);
 }
}
function normalSort(list) {
 var tmp;
 for(var i = 0;i<list.length; i++){
 for(var j = i; j<list.length;j++){
 counter2A++
 if(list[i]>list[j]){
 counter2B++
 tmp = list[i];
 list[i]=list[j];
 list[j] = tmp;
 }
 }
 }
}
quickSort(list);
normalSort(list2);
console.log('quick:',"循环次数:"+counterA,"值交换次数:"+counterB)
console.log('normal:',"循环次数:"+counter2A,"值交换次数:"+counter2B)
//quick: 循环次数:182 值交换次数:40
//normal: 循环次数:780 值交换次数:243