/**
- 快速排序是一种交换排序的方式
- 不稳定
- 时间复杂度 最好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()
