利用JavaScript实现快速排序算法及步骤详解

javascript实现快速排序算法:
快速排序基本思想:
使用分治法策略来把一个序列分为两个子序列

步骤为：
1.从数列中挑出一个元素,称为"基准"(pivot),一般选用最右边元素为基准元素.
2.重新排序数列,所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。
3.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
4.递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。

在平均状况下，排序n个项目要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较,但这种状况并不常见

    function quickSort(array) {

    // 交换元素位置
    function swap(array, i, k) {
        var temp = array[i];
        array[i] = array[k];
        array[k] = temp;
    }
    // 数组分区，左小右大
    function partition(array, left, right) {
        var storeIndex = left;        
        var pivot = array[right]; // 直接选最右边的元素为基准元素
        for (var i = left; i < right; i++) {
            if (array[i] < pivot) {
                swap(array, storeIndex, i);
                storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置
            }
        }
        swap(array, right, storeIndex); // 最后将基准元素放置正确位置上
        return storeIndex;
    }

    function sort(array, left, right) {
        console.log("原始left="+left+"---原始right="+right);
        if (left > right) {
            return;
        }
        var storeIndex = partition(array, left, right);
        
        //基准元素左边排序
        sort(array, left, storeIndex - 1);
        
        //基准元素右边排序
        sort(array, storeIndex + 1, right);
    }

    sort(array, 0, array.length - 1);

    return array;
}

var arr=[3,7,8,5,2,1,9,5,4];

console.log(quickSort(arr));

步骤详解:

原始顺序: 3 7 8 5 2 1 9 5 4

说明: 序列一与序列二独立运行

pivot=4(最右边的元素为基准元素)

storeIndex=1; i=4时
3 2 8 5 7 1 9 5 4

stroeIndex=2; i=5时
3 2 1 5 7 8 9 5 4

stroeIndex=3; i=8时循环结束

交换 array[8]与array[3]值
3 2 1 4 7 8 9 5 5
返回stroeIndex=3

序列一(基准元素左边):
sort(array, 0,2)
left=0; right=2;
partition(array,0,2); 此时 pivot=1

stroeIndex=0；i=2时跳出循环

交换 array[2]与array[0]值
1 2 3 4 7 8 9 5 5
返回stroeIndex=0
sort(array, 0,2)此函数结束

序列二(基准元素左边):
sort(array, 4,8)
partition(array,4,8); 此时 pivot=5

stroeIndex=4；i=8是循环结束

交换 array[8]与array[4]值
1 2 3 4 5 8 9 5 7
返回stroeIndex=4

sort(array,5,8)
partition(array,5,8); 此时 pivot=7

stroeIndex=5; i=7时
1 2 3 4 5 5 9 8 7

stroeIndex=6；i=8循环结束
交换 array[8]与array[6]值
1 2 3 4 5 5 7 8 9
返回stroeIndex=6

sort(array,7,8)
sort(array,8,8)
sort(array,9,8)此函数结束

返回最终结果: array
1 2 3 4 5 5 9 8 7