快速排序

基本思想

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

一趟快速排序的算法：

1.设置两个变量i，j,排序开始的时候：i=0,j=arr.length-1
2.以数组第一个元素作为base数据，赋值给temp,即temp = arr[i]
3.从j开始向前搜索，即由从数组后面向前搜索（j--），找到一个小于temp的值arr[j],将arr[j]赋值给arr[i],arr[i]=arr[j]
4.从i开始向后搜索，即由前到后搜索（i++），找到第一个大于temp的arr[i],j将arr[i]赋值给arr[j],arr[j] =arr[i]
5.重复第3、4步，直到i=j

代码示例(javascript)：

var quickSort = (arr,left,right) =>{
    var temp = arr[left];
    var i = left, j=right;
    //如果i>j不符合快速排序逻辑，直接返回
    if (i > j) return;
    //一次快速排序逻辑，找出符合条件的i和j
    while (i != j) {
        //注意查找顺序，想从数组后面向前查找
        while (arr[j] >= temp && i<j) {
            j--
        }
        while (arr[i] <= temp && i<j) {
            i++
        }
        //找到符合条件的i和j,调换位置
        if ( i<j ) {
            var t=arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[left] = arr[i];
    arr[i] = temp;
    //一次排序结束
    递归继续排序
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
}
// test
var arr = [5, 4, 6, 2, 88, 23, 79];
console.log(arr.toString());
var arrTemp = quickSort(arr, 0, arr.length - 1);
console.log(arrTemp.toString());