快排

/**

• 快速排序是一种交换排序的方式
• 不稳定
• 时间复杂度 最好nlogn 最差n平方
• 找一个基准数字，每一轮排序之后找到一个中间位置指针，这个位置之前的数都比基准数字小，之后的数都比基准数字大，找到这个位置后，把这个位置的数字和基准数字交换
• 为什么是用right指针的位置作为中间位置？
• 一定要让right指针先走吗？https://blog.csdn.net/u013447565/article/details/82079959
• 记得参数中有left right这样才能递归
• 基准数字可以是随机的
• @param arr
• @param left
• @param right
• @returns {*}
  */

function sort(arr, left, right){
    const basePos = left;
    const base = arr[left];

    while (left<right){
        while (arr[left]<=base && left<right){
            left++;
        }

        while (arr[right]>base && left<right){
            right--;
        }

        swap(arr, left, right)
        console.log('round:', arr, left, right)
    }

    swap(arr, basePos, right);
    return right;
}

function quicksort(arr = [], left, right){
  if(left >= right) return arr;

  const middle = sort(arr, left, right);

  quicksort(arr, left, middle-1);
  quicksort(arr, middle+1, right);
}

function swap(arr, i, j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function main(){
    console.time();
    let arr = [6,1,2,7,3,9,8,4,5,10,2,1];

    quicksort(arr, 0, arr.length-1)
    console.log(arr);
    console.timeEnd();
}

main()