一个计算机技术爱好者与学习者

0%

左神排序算法文字总结

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. 后记

代码实现:排序算法

好记性不如烂笔头,记下来,多看几遍,多想几遍,多写几遍,熟能生巧。

7. 书签

直通BAT — 求职算法精品课

牛客算法基础班

牛客算法进阶班

  • 本文作者: 好好学习的郝
  • 原文链接: https://www.voidking.com/dev-zuo-sort/
  • 版权声明: 本文采用 BY-NC-SA 许可协议,转载请注明出处!源站会即时更新知识点并修正错误,欢迎访问~
  • 微信公众号同步更新,欢迎关注~