左神排序算法文字总结

文章目录
  1. 1. 前言
  2. 2. 排序算法
  3. 3. 笨蛋算法
    1. 3.1. 冒泡排序
    2. 3.2. 选择排序
    3. 3.3. 插入排序
  4. 4. 聪明算法
    1. 4.1. 归并排序
    2. 4.2. 快速排序
    3. 4.3. 堆排序
    4. 4.4. 希尔排序
  5. 5. 变态算法
    1. 5.1. 计数排序
    2. 5.2. 基数排序
  6. 6. 后记
  7. 7. 书签

前言

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

《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 — 求职算法精品课