快速排序详解

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

1.算法步骤

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

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;
                }