阅读 384

快速、归并、堆排、冒泡、选择、插入详解

快速排序

分区(partition)

给一个数组arr和一个num,要求大于num的在左边,小于num的在右边,要求时间复杂度是O(N),空间复杂度是O(1)。

伪代码:

1、给一个指针i,初始位置是0,表示当前指向的位置
2、进行分区操作,初始化 <= 区的位置在 -1
3、当前数 <= num 时,把当前数和 <= 区的下一个数交换,<= 往前走一个位置,当前数往前跳一个。
4、当前数 > num 时,直接往前跳一个。
5、重复3、4步骤,直到整个数组遍历完成。
复制代码

code

荷兰国旗问题

现有红白蓝三个不同颜色的小球,乱序排列在一起,请重新排列这些小球,使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗问题,是因为我们可以将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗。

<==>其实这个问题等价于

给你一个数组 arr和一个num。要求大于 num 在左边,等于 num 在中间,小于 num 的在右边。要求时间复杂度是 O(N)。空间复杂度是 O(1)

伪代码:

1、分区为 <区、>区
2、用指针 i 表示当前值,指针 less 表示 < 区的值(初始是 -1),指针 more 表示 > 区的值(初始是arr.length)
3、当前值 < num。把 i和 < 区的后一个数交换,i往前走,<区往前走
4、当前值 > num。把 i和 > 区的前一个树交换,< 区往前走,i 不动
5、当前值 = num。i++
6、重复3、4、5直到遍历完成
复制代码

code

leetcode题目地址

经典快排

主要应用了partiton的思想。

经典快排代码 改进后的快排

时间复杂度

O(N^2)
因为会出现最坏情况。比如 1,2,3,4,5,6,7,8,9
第一次parition。  1,2,3,4,5,6,7,8,9              其中partition中循环是9次
第二次parition 8作为哨兵 1,2,3,4,5,6,7,8,9          8

这是个等差数列 N + N-1 + .... + 1
(N+1)*N/2 ~ O(N^2)
所以时间复杂度是 O(N^2)

最好的时候是通过partition分区的值是数值的中位数
这样通过master公式得出时间复杂度是 O(NlogN)
T(N) = 2T(N/2) + O(N) ~ O(N)

改进方式:
在通过随机性最后让数组中别的值取代,这样时间复杂度是 O(NlogN)

综上:
经典快排的时间复杂度是 **O(N^2)**
改进的快排时间复杂度是 **O(NlogN)**

复制代码

空间复杂度

O(logN)
因为在操作中要把左右位置记住,下次partition时才能从相应的位置开始,
而这些位置是的数量就是一个树的高度,所以时间复杂度是 O(logN)。
复制代码

稳定性

[ 2,4,2,1]  由算法思想得知,在排序过程中两个2是会互换位置的,这个算法是不稳定的。
复制代码

优化

1、在哨兵处增加随机性,可以使得快排的时间复杂度降到O(NlogN)
2、partition 时使用荷兰国旗方式分成三段分区
3、快排数量较少时,使用其他普通的排序方式(在快排的过程是使用其他排序方式)。
复制代码

改进后的快排

归并排序

merge

给两个数组各自都是有序的,如何使得全部有序?

伪代码:

[2,3,6,7]   [5,7,9,10]

1、准备两个指针i、j,分别指向两个数组的头部。再准备一个辅助数组help,临时存储排好序的部分数组。指针 n 指向辅助数组0位置。
2、把 i 指针指向的值和 j 指针指向的值进行比较,谁小复制谁到辅助数组help。同时 n 和 更小的指针往前走一步。直到指针i或者指针j到数组的末尾
3、指针i 或者 指针 j 退出循环。把还没跑到指针尾部的数据复制到 help 数组中。
4、返回 help
复制代码

merge

归并排序逻辑

思想:

归并排序是借助上面 merge 的思想: 先把数组分成左右两部分,先让左边有序,
再让右边有序,最后整体有序。在 merge 中依次比较左右两部分的值,
谁小 copy 谁到 help 数组。然后在把 help 数组复制到原数组相应的位置。

复制代码

mergeSort

时间复杂度是 O(NlogN),因为这个排序可以表示成 T(N) = T(N/2) + O(N)。

根据 master 公式这个时间复杂度是 O(NlogN)

空间复杂度是 O(N)。因为在 merge 中有个 help 数组申请。

下面问题是归并排序思想的应用。

小和问题

在一个数组中, 每一个数左边比当前数小的数累加起来, 叫做这个数组的小和。 求一个数组的小和。

例子:

对于[1,3,4,2,5]
1左边比1小的数, 没有;
3左边比3小的数, 1;
4左边比4小的数, 1、 3;
2左边比2小的数, 1;
5左边比5小的数, 1、 3、 4、 2
所以小和为1+1+3+1+1+3+4+2=16
复制代码

xiaohe

逆序对问题

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对,输入一个数组,求出这个数组中的逆序对的总数P。

比如在数组 [1,3,4,2,5] 中总共有这两个逆序对[3,2]、[4、2] 
复制代码

code

逆序对问题2

与上题一样,也是在 merge 中过程中操作

reverse-pairs

code

堆排序

堆排序

冒泡排序

冒泡排序思想代码

比较前一个位置的数如果比后一个大,就交换,否则不交换。
复制代码

code

冒泡排序复杂度分析

  1. 算法时间是时间复杂度为O(n²)
  2. 空间复杂度为O(1)
  3. 选择排序是稳定的(如果有相等元素,不交换,就可以做到稳定)

选择排序

选择排序思想代码

1、从待排序序列中,找到关键字最小的元素;起始假定第一个元素为最小
2、如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换
3、从余下的 N - 1 个元素中,找出关键字最小的元素,重复1,2步,直到排序结束。
复制代码

code

选择排序复杂度分析

  1. 算法时间是时间复杂度为O(n²)
  2. 空间复杂度为O(1)
  3. 选择排序是不稳定的( 不稳定算法,比如数组 [5,5,1],依次排序过后,1,5交换位置。两个5的相对次序发生了变化,因此是不稳定性的)

插入排序

插入排序思想代码

1、从第一个元素开始,该元素可以认为已经被排序
2、取出下一个元素,在已经排序的元素序列中从后向前扫描
3、如果下一个元素比扫描的元素小,交换。否则,跳出循环,继续下次循环的排序
复制代码

code

插入排序复杂度分析

  1. 时间是时间复杂度为O(n²)。
  2. 空间复杂度为O(1)
  3. 插入排序是稳定的(对于数组[2,4,6,4],当4插入有序数组2,4,6时,当相等时,就停止,不做处理,可以做到稳定性)

总结

排序方法 时间复杂度 空间复杂度 稳定性
快排 O(NlogN) O(logN) 不稳定
归并 O(NlogN) O(N) 稳定
堆排 O(NlogN) O(1) 不稳定
冒泡 O(N^2) O(1) 稳定
选择 O(N^2) O(1) 不稳定
插入 O(N^2) O(1) 稳定

备注:快排、归并、堆排虽然时间复杂度都是O(logN),但是常数项极低,因此工程上有的相对比较多。

原文地址,欢迎 star。

关注下面的标签,发现更多相似文章
评论