快速排序,😄
发布于 1 年前 作者 weivea 1130 次浏览 来自 分享
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


回到顶部