快速排序详解

快速排序使用的分治策略进行排序。快速排序像是冒泡排序上添加了递归分治。

1.算法步骤

• 从数列中挑出一个元素，称为“基准（pivot）”
• 重新排序数组，所有元素笔基准小的放在基准前面，所有元素笔基准值大的放在基准后面。（相同的值可以放任意一遍）
• 递归把小于基准和大于基准的子数组排序。

2.算法演示流程

        (对应方式1)

        （对应方式2）

3.算法代码

// -------------------------------方式1---------------------------------

    function fastSort(arr, left, right){

        var len = arr.length;
        var partitionIndex;   // 分割的位置

        var left = typeof left != "number" ? 0 : left;
        var right = typeof right != "number" ? len - 1 : right;
        if (left < right) {
            partitionIndex = partArrAction(arr, left, right);
            fastSort(arr, left, partitionIndex - 1);
            fastSort(arr, partitionIndex + 1, right);
        }

    }
//
    function partArrAction(arr, left, right){
        var povit = left;
        var index = povit + 1;

        for(var i = index; i < right; i++){
            if (arr[i] < arr[povit]) {
                swap(arr, i, index);
                index++;
            }
        }

        swap(arr, index - 1, povit);

        return index - 1;

    }

// 交换
    function swap(arr, i, j){
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // -----------------------------------方式2--------------------------------
    function quickSort(arr, low, hight){
        var povitIndex;   // 分割的位置

        if (low < hight) {
            povitIndex = partitionAction(arr, low, hight);
            quickSort(arr, low, povitIndex - 1);
            quickSort(arr, povitIndex + 1, hight);
        }
        return arr;
    }

    function partitionAction(arr, low, hight){
        var povit = arr[low];
        while(low < hight){
            while(low < hight && arr[hight] > povit){
                --hight;
            }

            arr[low] = arr[hight];
            while(low < hight && arr[low] <= povit){
                ++low;
            }
            arr[hight] = arr[low];
        }
        arr[low] = povit;
        return low;
    }