传统原地快排,js实现

quickSort.js

var arr = [];
for(let i = 0; i < 100; i++){
  arr[i] = Math.round(Math.random()*99);
}


//上面是生成随机数组

function quickSort(arr){
  function swap(arr, i, j){
    var tmp;
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  
  //选取更优的pivot
  function middleOfthree(arr, left, right){
    var center = Math.floor((left + right) / 2);
    //交换后最大的是中间或右边
    if(arr[left] > arr[right]){
      swap(arr, left, right);
    }
    //再交换后右边是最大的，最小的是左边或中间
    if(arr[center] > arr[right]){
      swap(arr, center, right);
    }
    //交换后arr[left]是三者的中位数
    if(arr[left] < arr[center]){
      swap(arr, left, center);
    }
    return arr[left];
    //因为partition要求pivot在left，所以这里要把中值放到left上。
  }
  
  function partition(arr, left, right){
    //注意此处pivot必须放在left（可以试一下取其它位置的值时的后果）
    //这样保证每次swap都有pivot在参与
    //也就是保证每次swap能做到把小的放左边大的放右边
    var pivot = middleOfthree(arr, left, right);
    while(left < right){
      while(left < right && arr[right] >= pivot){
        right--;
      }
      //遇到比pivot小的数交换位置到left
      //left实质上是按顺序数的未满足小于pivot条件的位置
      swap(arr, left, right);
      while(left < right && arr[left] <= pivot){
        left++;
      }
      //遇到比pivot大的数交换位置到right
      //left实质上是按顺序数的未满足小于pivot条件的位置
      swap(arr, left, right);
    }
    //弹出时left === right === pivot所在的索引
    return left;
  }
  
  function sort(arr, left, right){
    var pivot;
    if(right > left){
      pivot = partition(arr, left, right);
      sort(arr, left, pivot - 1);
      sort(arr, pivot + 1, right);
    }
  }
  
  return sort(arr, 0, arr.length - 1);
  
}
quickSort(arr)
console.log(arr);