Loveyless的学习笔记

Appearance

Return to top
On this page

快速排序(Quick Sort)

阮一峰 快速排序

快排的优化 快速排序(Quick Sort)算法又称为划分交换排序(Partition-Exchange Sort)算法，是实用性很高的排序算法，它可以在 O(nlogn)的时间复杂度完成排序，虽然是不稳定排序，但它的速度完全可以弥补这个缺点。

思路

  1. 在数据集之中，选择一个元素作为"基准"（pivot）。

  2. 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。

  3. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

实现

1. 首先，定义一个 quickSort 函数，它的参数是一个数组。

js
let quickSort = (arr) => {};

2. 然后，检查数组的元素个数，如果小于等于 1，就返回。

js
let quickSort = (arr) => {
  //如果传进来的数小于1就返回
  if (arr.length <= 1) {
    return arr;
  }
};

3. 接着，选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。

js
let quickSort = (arr) => {
  //如果传进来的数小于1就返回
  if (arr.length <= 1) {
    return arr;
  }

  //找到数组item中间的下标
  let pivotIndex = Math.floor(arr.length / 2); //Math.floor 向下取整

  //把中间下标的值截取出来 arr.splice为变异数组 会修改原数组 取出来之前concat()浅拷贝一下
  let pivot = arr.concat().splice(pivotIndex, 1)[0];

  let left = [];

  let right = [];
};

4. 接着，选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。

js
let quickSort = (arr) => {
  //如果传进来的数小于1就返回
  if (arr.length <= 1) {
    return arr;
  }

  //找到数组item中间的下标
  let pivotIndex = Math.floor(arr.length / 2); //Math.floor 取近似值

  //把中间下标的值截取出来作为'基准' arr.splice为变异数组 会修改原数组 取出来之前concat()浅拷贝一下
  let pivot = arr.concat().splice(pivotIndex, 1)[0];

  let left = [];

  let right = [];

  //开始遍历数组，小于"基准"的元素放入左边的子集，大于基准的元素放入右边的子集。
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      //每一项小于基准就取left
      left.push(arr[i]);
    } else {
      //每一项大于基准就取right
      right.push(arr[i]);
    }
  }

  //或者

  arr.forEach((item) => {
    //每一项小于基准就取left
    item < pivot && left.push(item);

    //每一项大于基准就取right
    item > pivot && right.push(item);
  });
};

5. 最后，使用递归不断重复这个过程，就可以得到排序后的数组。

js
let quickSort = (arr) => {
  //如果传进来的数小于1就返回
  if (arr.length <= 1) {
    return arr;
  }

  //找到数组item中间的下标
  let pivotIndex = Math.floor(arr.length / 2); //Math.floor 取近似值

  //把中间下标的值截取出来作为'基准' arr.splice为变异数组 会修改原数组 取出来之前concat()浅拷贝一下
  let pivot = arr.concat().splice(pivotIndex, 1)[0];

  let left = [];

  let right = [];

  //然后，开始遍历数组，小于"基准"的元素放入左边的子集，大于基准的元素放入右边的子集。
  arr.forEach((item) => {
    //每一项小于基准就取left
    item < pivot && left.push(item);

    //每一项大于基准就取right
    item > pivot && right.push(item);
  });

  return [...quickSort(left), pivot, ...quickSort(right)];
  //或者 Array.concat() 合并两个或多个 不传则浅拷贝
  return quickSort(left).concat([pivot], quickSort(right));
};

简化写法|去重&不去重

js
//100w个100以内长度数组716ms
function quickSort(arr) {
  //数组长度为1就不用比了 或者小于1就是空数组 都直接返回
  return arr.length <= 1 ? arr : [...quickSort(arr.filter((x) => x < arr[0])), ...arr.filter((x) => x == arr[0]), ...quickSort(arr.filter((x) => x > arr[0]))];

  //解析上面的一串代码
  // quickSort(arr.filter(x => x < arr[0])) //小于基准

  // .concat(arr.filter(x => x == arr[0])) //等于基准的

  // .concat(quickSort(arr.filter(x => x > arr[0]))) //大于基准的
}

//得到一个1000-0之间的随机整数数组
let a = Array(1000000)
  .fill(1)
  .map(() => {
    return Math.floor(Math.random() * (Math.floor(1000) - Math.ceil(0)) + Math.ceil(0));
  });

console.time();
let b = quickSort(a); //100w个100以内长度数组716ms
console.timeEnd();

console.log(b === a); //false
console.log(b); //结果不会去重

如果结果想去重呢？

js
function quickSort(arr) {
  return arr.length <= 1
    ? arr //直接放入基准arr[0]
    : [...quickSort(arr.filter((x) => x < arr[0])), arr[0], ...quickSort(arr.filter((x) => x > arr[0]))];

  //解析
  // quickSort(arr.filter(x => x < arr[0])) //小于基准

  // .concat(arr[0]) //基准 直接放入基准返回 不去比较等于基准的

  // .concat(quickSort(arr.filter(x => x > arr[0]))) //大于基准的
}

学到了什么

  1. Math.floor() 为向下取整 如果想实现四舍五入
js
// 任何数 + 0.5
Math.floor(any + 0.5);

或者 Math.round() 函数返回一个数字四舍五入后最接近的整数。

  1. Array.concat() 合并两个或多个 不传则浅拷贝
js
// 以后数组浅拷贝就这样写
arr.concat();
  1. 得到一个 1000-0 之间的随机整数数组长度为 100w
js
let a = Array(1000000)
  .fill(1)
  .map(() => {
    return Math.floor(Math.random() * (Math.floor(1000) - Math.ceil(0)) + Math.ceil(0));
  });

more

  1. 非简化版本测试发现不光排序还去重了 为什么呢?
js
arr.forEach((item) => {
  //每一项小于基准就取left
  item < pivot && left.push(item);

  //每一项大于基准就取right
  item > pivot && right.push(item);
});

这里对比 item 与基准值的时候并没有对item 等于基准时的操作 所以当数组里两个值相同 比对基准 会无任何操作 只是返回的时候带上 pivot 基准 return [...quickSort(left),pivot,...quickSort(right)]

  1. splice 会改变传进来的参数数组 所以 splice 时要浅拷贝 因为函数中会先生命形参 在拿实参赋值给形参 对象数据是拿栈地址赋值 所以会一起变化

js
let fun = (arr) => {
  let d = arr.splice(0, 1)[0]; //这里改变了arr的值 也就改了a的值为[2,3]
  d = arr.push(2); //这里也改变了值 a为[2,3,2]
  return d;
};

let a = [1, 2, 3];
let b = fun(a); //这里传入了a

console.log(a); //所以a被改为[2,3,2]了
console.log(b);

我去，我好像发现了一个颠覆认知的事，以后类似操作还是浅/深拷贝一下吧

未解

  1. 相比于Array.prototype.stor()快排没有原地算法
js
    let quickSort = (arr) => {...};
    let a = [12, 3, 3124, 14];
    let b, c;

    b = quickSort(a);
    c = a.sort((a, b) => { return a - b });

    console.log(a); //(4) [3, 12, 14, 3124]
    console.log(b); //(4) [3, 12, 14, 3124]
    console.log(c); //(4) [3, 12, 14, 3124]
    console.log(b === a); //false
    console.log(c === a); //true

Array.prototype.stor()使用了原地算法所以还是 c 和 a 相等

go

go
//快排
//Go语言并没有对删除切片元素提供专用的语法或者接口，需要使用切片本身的特性来删除元素。
//根据要删除元素的位置有三种情况，分别是从开头位置删除、从中间位置删除和从尾部删除，其中删除切片尾部的元素速度最快。
func Quick(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	var (
		left  []int
		right []int
		mid   int
	)

	mid = arr[len(arr)-1]
	arr = arr[:len(arr)-1] //删除尾部item

	for _, v := range arr {
		if v < mid {
			left = append(left, v)
		} else {
			right = append(right, v)
		}
	}

	return append(append(Quick(left), mid), Quick(right)...)

}

复习回头写

ts
let arr = [53, 2, 2, 6, 63, 312, 23, 6, 74, 6, 2, 8, 856, 85, 75, 4, 7, 8, 9, 9];

function qSort(arr: Array<number>): Array<number> {
  if (arr.length <= 1) return arr;
  let num = arr[0];
  let left = [];
  let mid = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < num) left.push(arr[i]);
    if (arr[i] === num) mid.push(arr[i]);
    if (arr[i] > num) right.push(arr[i]);
  }

  return [...qSort(left), ...mid, ...qSort(right)];
}
console.log(qSort(arr));