第五话 排序算法

排序算法（Sort Algorithm），排序是将一组数据，依指定的顺序进行排序的过程

排序的分类：

1. 内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。
2. 外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

常见的排序算法分类

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-thpn5xWQ-1618541456962)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325084358307.png)]

度量一个程序（算法）执行时间的两种方法

1. 事后统计方法

这种方法可行，但是有两个问题：一是要想对设计的算法的运行能力进行评价，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件，软件等环境因素，这种方式，要在同一台计算机的相同状态下运行，才能比较哪个算法速度更快

2. 事前估计的方法

通过分析某个算法的时间复杂度来判断哪个算法更优。

5.1.1 算法的时间复杂度

时间频度

时间频度：一个算法花费的时间与算法中语句的执行次数成正比，哪个算法在语句执行的次数多，它花费的时间就多，**一个算法中的语句执行次数称为语句频度或时间频度。**计为T(n)。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Mhgat7rL-1618541456966)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325084440288.png)]

结论

1. 2n+20和2n随着n变大，执行曲线无限接近，20可以忽略
2. 3n+10和3n随着n变大，执行曲线无限接近，10可以忽略

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hANpvmK2-1618541456970)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325084551920.png)]

结论

1. 2n^2+3n+10和2n2随着n的增大，执行曲线无限接近，可以忽略3n+10
2. n^2+5n+20和n2随着n的增大，执行曲线无限接近，可以忽略5n+20

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O5RUvlvy-1618541456974)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325084622475.png)]

结论

• 随着 n 值变大， 5n^2+7n 和 3n^2 + 2n ， 执行曲线重合, 说明 这种情况下, 5 和 3 可以忽略。
• 而 n^3+5n 和 6n^3+4n ， 执行曲线分离， 说明多少次方式关键

5.1.2 时间复杂度概念

1. 一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
2. T(n)不同，但时间复杂度可能相同。如：T(n)=n^{2+7n+6与T(n)+3n}2+2n+2，它们的T(n)不同，但时间复杂度相同都是O(n^2)。
3. 计算时间复杂度的方法
   1. 用常数1代替运行时间中的所有加法常数
   2. 修改后的运行次数函数中，只保留最高阶项
   3. 去除最高阶项的系数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YrfMhmPq-1618541456976)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325090021138.png)]

常数阶O(1)

无论代码执行了多少行，只要没有循环体等复杂结构，那么这个代码的时间复杂度就是O(1)，上述代码在执行的时候，它消耗的时间不随着某个变量的增长而增长，那么无论这类代码有多长。即使几十万都可以用O(1)来表示它的时间复杂度。

对数阶

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SFmTLaMG-1618541456978)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325090949315.png)]

线性阶O(n)

这段代码，for循环里面的代码块会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

线性对数阶

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EK3D4zKJ-1618541456980)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325092301879.png)]

平方阶O(n^2)

平方阶O(n^{2)就更容易理解了，如果把O(n)的代码再嵌套循环一遍，它的时间复杂度就是O(n}2)，这段代码其实就是嵌套了2层n循环，如果将其中的一层循环由n改为m，那么它的时间复杂度就变成了O(m*n)。

5.1.3 平均时间复杂度和最坏时间复杂度

1. 平均时间复杂度是指所有可能的输入实例以等概率出现的情况下，该算法的运行时间
2. 最坏情况下的时间复杂度称最坏时间复杂度，一般讨论的时间复杂度均是最坏情况下的时间复杂度，这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长了。
3. 平均时间复杂度和最坏时间复杂度是否一致，和算法有关如图所示；

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CsqynZtf-1618541456982)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325093406839.png)]

5.1.4 算法空间复杂度

1. 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所消耗的存储空间，也是问题规模n的函数。
2. 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n比较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。
3. 在做算法分析的时候，主要讨论的是时间复杂度。从用户使用体验上来看，更看重的程序执行的速度，一些缓存产品（redis,memcache）和算法（基数排序）的本质就是用空间换时间。

5.2.1 基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从小标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前向移向后部，就象水底下的气泡一样逐渐向上冒。

因为排序的过程中，各个元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此需要在排序的过程中设置一个标志flag判断元素是否进行过交换。

思路

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SpohdlX0-1618541456984)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325101055268.png)]

5.2.2 应用实例

我们举例一个具体的案例来说明冒泡法，将五个无序的数：3 9 -1 10 -2，使用冒泡排序法将其排成一个从小到大的有序数列

基础代码

结果

优化：如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序，这个就是优化。

结果

选择排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再次依规定交换位置后达到排序的目的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7tMutooi-1618541456986)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325130810350.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d8di3ZK1-1618541456988)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325131357981.png)]

代码实现

结果

运行时间代码测试

结果

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式寻求该元素的适当位置，以达到排序的目的。

插入排序（Inserting Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只含有一个元素，无需表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-B0TjIwjs-1618541456990)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210325151652653.png)]

代码实现

运行结果

5.5.1 希尔排序算法的介绍

针对插入排序中存在的问题有：

当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-90ONTyHD-1618541456993)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210329111648973.png)]

希尔排序算法的介绍

希尔排序是1959年提出的一种排序算法，希尔排序也是插入排序，它是简单的排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

希尔排序的基本思想：

希尔排序是把记录按小标的一定增量分组，对每组使用直接插入排序算法排序，随着增量的减少，每组包含的关键词越来越多，当增量减少至1时，整个文件被分成一组，算法终止。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3k0jJogO-1618541456996)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210329112211305.png)]

经过上面的宏观调控，整个数组的有序化程度成果惊人，此时仅仅需要对以上数列简单微调，无需大量移动就可以完成整个数组的排序。

5.5.2 算法的实现

交换法实现

运行的结果显示

效率的显示

移位式的算法实现

算法效率的计算

*这也太牛逼了吧~~~~~*~

5.6.1 快速排序算法的介绍

快速排序算法（Quicksort）是对冒泡排序的一种改进，基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序国恒可以递归，以此达到整个数据都变成有序序列。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0F2mm65h-1618541456998)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210329144131037.png)]

5.6.3 代码实现

代码的实现

上面是有两种实现代码

5.7.1 归并排序算法基本介绍

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（devide-and-conquer）策略（分治法将问题分(devide)成一些小的问题，然后再递归求解，而治(conquer)的阶段则将分的阶段得到各答案修补在一起，即分而治之。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DHo26srn-1618541457000)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210330090336661.png)]

**说明：**可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现，（也可以使用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SBe6fs6w-1618541457002)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210330091200075.png)]

5.7.2 代码的实现

运行的结果

合并的次数就是n-1

5.8.1 基数排序的基本知识

1. 基数排序（radix sort）属于分配式排序（distribution sort）又称桶子法或bin sort，顾名思义，它是通过键值的各个位的键，将要排序的元素分配至某些桶中，达到排序的作用。
2. 基数排序是属于稳定性的排序，基数排序法是效率高的稳定性排序法。
3. 基数排序是桶排序的扩展
4. 基数排序是1887年赫尔曼发明的，它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序的基本思想

1. 将所有待比较数值统一为同样数位长度，数位较短的数前面补0，然后从低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成了一个有序序列。
2. 看一个图文解释，理解基数排序的步骤。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kKvcVXON-1618541457004)(C:UsersdongweiAppDataRoamingTypora ypora-user-imagesimage-20210330110131298.png)]

第二轮之后是十位

第三轮是百位

轮数是按照最高位数来判断的

5.8.2 代码实现

结果

5.8.3 基数排序的注意事项

1. 基数排序是对传统桶排序的扩展，速度很快
2. 基数排序是经典的空间换时间的方式，占用的内存很大，当对海量数据排序的时候，容易造成 OutOfMemoryError
3. 基数排序是稳定的。【注：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]依旧在r[j]之前，则称这种排序算法是稳定的，否则是不稳定的。
4. 有负数的数组，我们不用基数排序来进行排序，如果想要支持负数，请查看：https://code.i-harness.com/zh-CN/q/e98fa9