左神排序算法文字总结

前言

相见恨晚!看了左神的算法视频,才知道自己到底浪费了多少时间。算法,居然能讲的这么有意思,居然能讲的这么通俗易懂!左神,不愧是左“神”!

《leetcode刷题记录-排序算法总结》一文中,也总结过排序算法,但是和左神的讲解一比,简直就是渣渣。所以,本文按照左神的讲解,再次总结一下排序算法。

排序算法

常见的排序算法有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位置的元素。

笨蛋算法

冒泡排序

1、依次比较,a[i] < a[i+1] 则交换元素,结果最大元素位于N-1位置
2、范围缩小1

选择排序

1、0到N-1选出最小元素放在0位置(交换元素即可)
2、1到N-1选出最小元素放在1位置

插入排序

1、1位置和0位置元素比较,小则交换
2、2位置和1位置元素比较,小则交换;1位置和0位置元素比较,小则交换

聪明算法

归并排序

1、数组分割成长度为1的有序区间
2、有序区间两两合并,得到长度为2的有序区间

快速排序

1、数组中随机选择一个数,小于等于这个数的元素放左,大于这个数的元素放右
2、左右两边递归

快速划分过程:
(1)左区间初始值为0,划分值放在N-1位置
(2)遍历数组,元素大于划分值则跳过,小于等于划分值则交换该元素与左区间加一的元素,到N-1位置则交换划分值与左区间加一的元素。

堆排序

1、已有大根堆(数组表示),把堆顶元素与最后一个元素交换,交换后最后一个元素有序
2、调整后,把堆顶元素与倒第二个元素交换,交换后最后两个元素有序

希尔排序

1、设定初始步长,按照步长比较元素大小并交换
2、步长减一,比较元素大小并交换

注:希尔排序是改良版的插入排序

变态算法

计数排序

1、建立0-M号桶
2、把元素按大小放入对应桶
3、依次把0-M号桶中的元素倒出

基数排序

1、准备0-9号桶
2、元素按个位数放入对应桶
3、依次把0-9号桶中的元素倒出(先进先出),成为序列
4、按序列把元素按十位数放入对应桶

注:计数排序和基数排序都属于桶排序的实现,桶排序是一种排序思想。

后记

好记性不如烂笔头,后续计划对其他算法也进行总结。

书签

牛客算法基础班

牛客算法进阶班

直通BAT — 求职算法精品课

0%