快速排序算法javascript实现

时间:2021-12-30 07:29:21
  1. function quicksort(arr){
  2.   function q(start,end){
  3.     if(start>=end){return;}
  4.     var pivot = start,
  5.     temp = arr[pivot],
  6.     i = start+1;
  7.     for(;i<=end;i++){
  8.       if(arr[i]<temp){
  9.         var s = arr.splice(i,1)[0];
  10.         arr.splice(start,0,s);
  11.         pivot++;
  12.       }
  13.     }
  14.     q(start,pivot-1);
  15.     q(pivot+1,end);
  16.   }
  17.   q(0,arr.length);
  18.   return arr;
  19. }
  20. var arrs = [9,45,45,90,3,77,4,90];
  21. var c = quicksort(arrs);
  22. console.log(c);

第3行的if(start>=end){return;},以这样的方式退出递归,我是这么考虑的。

当子数组中剩两项时,分两种情况分析:

(1)当子数组第一项(传递给参数start)比第二项(传递给参数end)小

  在函数q中先做了一遍调整,最后变量start指向第一项,变量pivot指向第一项,然后是:

  q(start,pivot-1);//此时start==pivot,故start>pivot-1,通过if(start>=end){return;}退出递归

  q(pivot+1,end);//此时pivot+1==end,同理退出递归

(2)当第一项比第二项大

  在函数q中做一遍调整,最后变量start指向第一项,变量pivot指向第二项,然后:

  q(start,pivot-1);//此时start==pivot-1,退出递归

  q(pivot+1,end);//此时pivot+1>end;也退出递归