JavaScript实现快速排序

<快速排序算法>

简单介绍:

给定一个无序数组，从中选出一个数作为哨兵位 (pivot)

Step1: 从最后一位 (high) 开始遍历数组，若小于pivot，则继续往前，发现大于哨兵位的数 (j) 则停止。

Step2: 从数组的最前 (low) 往后遍历，若小于pivot则继续，若大于哨兵位的数则停止 (i) , high、low、 i、j均为数组下标。

Step3: 交换i、j位置上的数，直到 low=high。

Step4: 递归。

※ 快速排序的核心思想是通过哨兵位，从而将数组一次一次分为两部分，即左边<哨兵位；右边>哨兵位，从而递归实现最终的排序结果

图片来源及详细说明https://www.cnblogs.com/redbear/p/8891730.html

function QuickSort(arr) {

    let low =0;

    let high = arr.length-1;

//设定枢轴 (pivot) , 即哨兵位 。这里使用第一个元素作为哨兵

let pivot = arr[0];

    if(arr.length<2){

return arr;

    }

while(low<high){

while (arr[high] >= pivot && high > low){

high--;

        }

while (arr[low] <= pivot && high > low){

low++;

        }

if(low==high){

let mid = arr[high];

            arr[high] = arr[0];

            arr[0] = mid;

            break;

        }else{

        let tem = arr[high];

        arr[high] = arr[low];

        arr[low] = tem;

        }

}

//Note: slice()函数的两个参数start和end，end数组下标-1!

    let res =QuickSort(arr.slice(0,low)).concat(arr[low]).concat(QuickSort(arr.slice(low+1)));

    return res;

}