js的算法-交换排序（快速排序）

快速排序

基本思想

快速排序的基本思想是基于分治法的：在待排序表L【1...n】中任意取一个元素p 作为枢轴（或基准，通常取首元素）。通过一趟排序将待排序表划分为独立的两部分L【1...k-1】和L【k+1...n】;这样的话，L【1...k-1】中所有的元素小于p,L【k+1...n】中所有的元素大于等于p,p 放在了整个待排序表排好序的最终位置上。也就是p 的顺序已经排好。左边全是比p 小的，右面全是比p 大的。这个过程称为一趟快速排序（或一次划分）。然后分别递归对两个子表，重复上述过程。直至每部分内只有一个元素或空为止。此时，所有的元素都放在了其最终的位置上。

一趟快速排序的过程是一个交替搜索和交换的过程。

演示

第一趟

js 代码

let ary = [3, 8, 1, 9, 4, 5, 6, 2, 7];
let len = ary.length;
let p = ary[len - 1];
console.log("p", p);

const left = [];
const right = [];

for (let i = 0; i < len - 1; i++) {
  if (ary[i] < p) {
    left.push(ary[i]);
  } else {
    right.push(ary[i]);
  }
}
let result = left.concat(p, right);
console.log(JSON.stringify(result));

运行结果：

p 7
[3,1,4,5,6,2,7,8,9]

代码展示

console.log("******递归实现快速排序******");
let ary = [3, 8, 1, 9, 4, 5, 6, 2, 7];
function quickSort(ary) {
  // 如果数组长度小于等于1，直接返回
  if (ary.length <= 1) {
    return ary;
  }
  // 如果数组长度大于1，则取最后一个元素为基准值
  let p = ary[ary.length - 1];
  const left = [];
  const right = [];
  // 遍历给左右分区
  for (let i = 0; i < ary.length - 1; i++) {
    if (ary[i] < p) {
      // 小于的放在左边
      left.push(ary[i]);
    } else {
      // 大于的放在右边
      right.push(ary[i]);
    }
  }

  // 注意递归
  return quickSort(left).concat(p, quickSort(right));
}
const result1 = quickSort(ary);
console.log(JSON.stringify(result1));

结果：

******递归实现快速排序******
[1,2,3,4,5,6,7,8,9]

性能分析

性能分析
时间复杂度	空间复杂度
最好情况：O(nlogn),）每次取到的元素都刚好平分平分整个数组	最好情况：O（logn）每次取到的元素都刚好平分平分整个数组
最坏情况O（n^2）每次取到的元素就是数组中最小/最大的，同冒泡排序	最坏情况：O（n）每次取到的元素就是数组中最小/最大的，同冒泡排序
平均情况：O（nlogn）	平均情况：O（logn）;因为用到了递归，每次递归都必须使用栈