1. 前言
相见恨晚!看了左神的算法视频,才知道自己到底浪费了多少时间。算法,居然能讲的这么有意思,居然能讲的这么通俗易懂!左神,不愧是左“神”!
《leetcode刷题记录-排序算法总结》一文中,也总结过排序算法,但是和左神的讲解一比,就是渣渣。所以,本文按照左神的讲解,再次总结一下排序算法。
2. 排序算法
常见的排序算法有9个,分别是冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、希尔排序、计数排序和基数排序。它们的时间空间复杂度如下:
算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|
冒泡排序 | $O(N^2)$ | $O(1)$ | 稳定 |
选择排序 | $O(N^2)$ | $O(1)$ | 不稳定 |
插入排序 | $O(N^2)$ | $O(1)$ | 稳定 |
归并排序 | $O(N*logN)$ | $O(N)$ | 稳定 |
快速排序 | $O(N*logN)$ | $O(logN)到O(N)$ | 不稳定 |
堆排序 | $O(N*logN)$ | $O(1)$ | 不稳定 |
希尔排序 | $O(N*logN)$ | $O(1)$ | 不稳定 |
计数排序 | $O(N)$ | $O(M)$ | 稳定 |
基数排序 | $O(N)$ | $O(M)$ | 稳定 |
注:M代表桶数量。
如上图,按照时间复杂度的不同,分为三大类。
以下算法描述,实现的都是升序排序,N代表元素个数,a[i]代表i位置的元素。
3. 笨蛋算法
3.1. 冒泡排序
1、依次比较,a[i] > a[i+1]
则交换元素,结果最大元素位于N-1位置
2、范围缩小1
3.2. 选择排序
1、0到N-1选出最小元素放在0位置(交换元素即可)
2、1到N-1选出最小元素放在1位置
3.3. 插入排序
1、1位置和0位置元素比较,小则交换
2、2位置和1位置元素比较,小则交换;1位置和0位置元素比较,小则交换
4. 聪明算法
4.1. 归并排序
1、数组分割成长度为1的有序区间
2、有序区间两两合并,得到长度为2的有序区间
4.2. 快速排序
1、数组中随机选择一个数,小于等于这个数的元素放左,大于这个数的元素放右
2、左右两边递归
快速划分过程:
(1)左区间初始值为0,划分值放在N-1位置
(2)遍历数组,元素大于划分值则跳过,小于等于划分值则交换该元素与左区间加一的元素,到N-1位置则交换划分值与左区间加一的元素。
4.3. 堆排序
1、建立大根堆(数组表示),把堆顶元素与最后一个元素交换,交换后最后一个元素有序
2、调整后,把堆顶元素与倒第二个元素交换,交换后最后两个元素有序
完全二叉树当前节点索引为i,那么父节点为(i-1)/2,子节点为2i+1和2i+2
调整大根堆:调整当前节点大于左右子节点,若发生调整则递归
建立大根堆:从下往上,从第一个父节点开始
视频讲解:堆排序
4.4. 希尔排序
1、设定初始步长,按照步长比较元素大小并交换
2、步长减一,比较元素大小并交换
注:希尔排序是改良版的插入排序
5. 变态算法
5.1. 计数排序
1、建立0-M号桶
2、把元素按大小放入对应桶
3、依次把0-M号桶中的元素倒出
5.2. 基数排序
1、准备0-9号桶
2、元素按个位数放入对应桶
3、依次把0-9号桶中的元素倒出(先进先出),成为序列
4、按序列把元素按十位数放入对应桶
注:计数排序和基数排序都属于桶排序的实现,桶排序是一种排序思想。
6. 后记
代码实现:排序算法
好记性不如烂笔头,记下来,多看几遍,多想几遍,多写几遍,熟能生巧。