于禤的博客

学习+记录

0%

快速排序

发表于 更新于 分类于

快速排序的过程：

  1. 在数据中选择一个元素作为基准（ 一般选择中间的数字或者最左边的数字 ），所有小于基准的元素都移到左边的子集中，所有大于基准的元素都移到右边的子集中
  2. 对基准左右两边的两个子集不断重复第一步，直到所有子集只剩下一个元素为止。

例子：现有数组arr:[14,3,13,33,61,20,11]

  1. 第一次分类选择中间元素的位置Math.floor(arr.length/2) = 3，则中间元素是13，小于13的放左边， 大于13的放右边

    3,11//左边 **13 ** 14,33,61,20//右边

  2. 第二次则分别对左右两边的子集重复第一次排序。

    3 11 13 14 ,20 33 61

  3. 第四次

    3,11,13 ,14,20,33,61

使用JavaScript实现快排算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const quickSort = arr => {
  if (arr.length <= 1) {
    return arr;
  }

  const pivotIndex = Math.floor(arr.length / 2) - 1;
  const pivot = arr.splice(pivotIndex, 1)[0];
  const leftArr = [];
  const rightArr = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      leftArr.push(arr[i]);
    } else {
      rightArr.push(arr[i]);
    }
  }
  
  return quickSort(leftArr).concat([pivot], quickSort(rightArr));
};

时间复杂度： 平均时间复杂度O(nlogn) 、最好情况O(n)、最差情况O(n*n)
空间复杂度： O(logn)
稳定性： 不稳定

这里如果是二分查找，则logn的底数是2

对数函数和指数函数复习：

如果a(a大于0，且a不等于1)的b的次幂等于N，那么数b叫做以a为底N的对数，记作 logaN = b,读作以a为底N的对数，a叫做对数的底数，N叫做真数。

一般函数 y = log(a)X (其中a 是常数，a大于0且不等于1)叫做对数函数，

对数函数是指数函数的反函数，则指数函数为 x = a^y

时间复杂度指的是一个算法执行所耗费的时间
空间复杂度指运行完一个程序所需内存的大小
稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面
不稳定指，如果a=b，a在b的前面，排序后可能会交换位置