算法=>快速排序的尾递归推导

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。百度百科

将大的问题分解为小的问题，小问题处理的逻辑和大的问题一样，首先想到的是递归。

我们先来看看阮一峰前辈的实现，比较容易理解原理

 var quickSort = function(arr) {
         //终止递归的条件
    　　if (arr.length <= 1) { return arr; }
        //取得参照数
    　　var pivotIndex = Math.floor(arr.length / 2);
    　　var pivot = arr.splice(pivotIndex, 1)[0];
    　　var left = [];
    　　var right = [];
    　　for (var i = 0; i < arr.length; i++){
        //比参照数小的放在left数组
    　　　　if (arr[i] < pivot) {
    　　　　　　left.push(arr[i]);
    　　　　} else {
        //大于等于参照数的放在right数组
    　　　　　　right.push(arr[i]);
    　　　　}
    　　}
      /*
          递归处理
          处理左边的数组left   参照数   处理右边的数组right  =>生成一个新数组
           
      */
    　　return quickSort(left).concat([pivot], quickSort(right));
    };

上述实现避开了快排的一个难点=>确认子数组的起始、结束位置。

让我们在原数组上进行排序，而不产生新的数组。

function quicksort(arr,start,end){


start = start == undefined ? 0 : start;
end = end == undefined ? arr.length - 1 : end;
//通常验证传参end = end ||  arr.length - 1；这里这样写是因为end等于0时，也会去取arr.length - 1

if(start >= end){
    //终止条件
    return;
}

let index = arr[start];

let i = start , j = end;

while(i < j){
    //找出右边第一个小于参照数的下标并记录
    while(i < j && arr[j] >= index){
        j--;
    }
    if(i < j){
        arr[i++] = arr[j];
    }
      //找出左边第一个大于参照数的下标，并记录
    while (i<j && arr[i] < index) {
        i++;
    }

    if(i<j){
    
        arr[j--] = arr[i];
    }

}
//此时i的位置就是参照数在原数组中的新位置。
arr[i] = index;

quicksort(arr,start,i-1);
quicksort(arr,i+1,end);
}

上述实现是不能用数组中间位置的成员作参照数

起始位置作为临时变量，右边发现一个小于参照数的就赋值给起始位置，这时右边也有一个空闲的位置，当左边发现比参照数大的时，在赋值给右边的空闲位置，这时左边又有一个可覆盖的位置，如此周而复返，直到i不再小于j

arr[i] = index;很重要，当循环结束，如果不执行，arr[i]的值可能不是index。

如果已中间索引上的成员作为参照数，而第一个覆盖的是起始位置上的成员，导致起始位置上的值没有被记录，显然是不对的。

注意，这里的实现应为使得a[i]左边的数小于等于参照数，a[i]右边的数大于参照数！

看看下面实现与上述的去别

function quicksort(arr,start,end){


start = start == undefined ? 0 : start;
end = end == undefined ? arr.length - 1 : end;

if(start >= end){
    return;
}


let index = arr[(start+end)/2 | 0];


let i = start , j = end;

while(i <= j){

    while (arr[i] < index) {
        i++;
    }
    while(arr[j] > index){
        j--;
    }

    if(i<=j){

        [arr[i],arr[j]] = [arr[j],arr[i]];
        i++;
        j--;
    }

}

quicksort(arr,start,i-1);
quicksort(arr,i,end);
}

这时let index = arr[start];也是没有关系的，注意这句话quicksort(arr,i,end);如果换成quicksort(arr,i+1,end);就会发生问题

我们看下面例子

数组 起始位置 结束位置 参照数 i的值
[22, 930, 1848, 66, 520, 1775, 1362, 854, 591, 1227]
注意这里 3的位置是1848 而1848下一个是930，但是3-9的位置都是大于520的，右边都是小于等于520的
[22, 520, 66, 1848, 930, 1775, 1362, 854, 591, 1227] 0 9 520 3

1848不参与下一次的排序就有问题了

不管数组内容如何，只要长度一致，执行的次数就是可以预见的，因此，减少执行的次数便是优化方案了，在这一点上，第二种方式是好于第三种的。

因为第二种每次排序后都会有一个数不用参与下一次的排序。这不仅减少数组内部交换的次数，同样也减少了函数调用的次数

在发生下一次函数调用前就判断也能减少调用次数，并将参数的判断移到最外面。这些我们在尾递归中做到。

当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归

return quick(arr);//是
return type == undefined ? a : quick(a);//是
return quick(arr)+1;//不是

把函数一下次运行的全部信息都通过参数传递，那么就无需保留上一次运行的栈了。

尾递归实现了，循环的方案也就出来了。

quicksort(a,[0,a.length-1]);
   function quicksort(arr,stack){



let start = stack[0],
    end = stack[1];

let index = arr[start];

let i = start , j = end;

while(i < j){

    while(i < j && arr[j] >= index){
        j--;
    }
    if(i < j){
        arr[i++] = arr[j];
    }

    while (i<j && arr[i] < index) {
        i++;
    }

    if(i<j){
        arr[j--] = arr[i];
    }

}

arr[i] = index;
//移除已经使用完的下标
stack.shift();
stack.shift();
 //注意要先放入右边数组的下标
if(i+1<end){

    stack.unshift(i+1,end);
}
if(start < i-1){

    stack.unshift(start,i-1);
}

if(stack.length == 0){
    //排序完成
    return;
}

return quicksort(arr,stack);


}

}

快速排序相当于一个深度优先遍历，我们利用一维数组来记录位置信息。

下面是验证排序正确性的测试函数，还应该做值对应的检测，防止发生值覆盖。

for(let count =0;count<100;count++){

var arr = [];
for(let i=0;i<10;i++){
    arr[i] = Math.random() * 2000 | 0;
}

var temp = arr.slice();
quicksort(temp,[0,arr.length-1]);
for(let j=0;j<temp.length-1;j++){
    if(temp[j+1] < temp[j]){
        console.log("错误:\n"+temp)
        console.log("源:\n"+arr);
        break;
    }
}
}

console.log("end")

没想到花了我三个晚上！
纸上得来终觉浅，绝知此事要躬行。
上一次研究快排还是用java，人生啊，那时我还在读大学。