- function quicksort(arr){
- function q(start,end){
- if(start>=end){return;}
- var pivot = start,
- temp = arr[pivot],
- i = start+1;
- for(;i<=end;i++){
- if(arr[i]<temp){
- var s = arr.splice(i,1)[0];
- arr.splice(start,0,s);
- pivot++;
- }
- }
- q(start,pivot-1);
- q(pivot+1,end);
- }
- q(0,arr.length);
- return arr;
- }
- var arrs = [9,45,45,90,3,77,4,90];
- var c = quicksort(arrs);
- 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;也退出递归