开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 排序（十多种排序） -> 正文阅读

[数据结构与算法]排序（十多种排序）

8.1 排序的基本概念

排序定义

在这里插入图片描述

排序算法的评价指标

在这里插入图片描述

排序算法的分类

在这里插入图片描述

总结

在这里插入图片描述
https:/www.cs.usfca.edu/~galles/visualization/Algorithms.html

8.2-1 插入排序

插入排序举例

在这里插入图片描述

插入排序算法实现

插入排序一般实现

在这里插入图片描述

插入排序带哨兵实现

在这里插入图片描述

算法效率分析

空间复杂度
在这里插入图片描述
时间复杂度

下图：比如第一趟：查找70，对照着对待，A[2]=70<A[1]=80,对比关键字一次，A[0]=A[i]=70,移动元素一次，for循环，A[0]=70<A[1]=80,又对比关键字一次，A[2]=A[1]=80,又移动元素一次，最A[1]=A[0]=70,又移动元素一次。共对比关键字2次，移动元素3次
在这里插入图片描述
平均时间复杂度O（n2）

优化—折半插入排序

在这里插入图片描述

8.2-2 希尔排序

希尔排序示例

第一趟：
在这里插入图片描述

第二趟：

第三趟：

希尔建议设置每次将来增量缩小一半

在这里插入图片描述

算法实现

下图只是实现希尔排序的一种方法，但是这种方法并不是按照上面的思路：先分成多个子表，每个子表排完序再放回数组，更换d的大小，继续这样的操作。但下图的方法仍然能实现希尔排序。由于时间原因暂时没能实现上述思路的希尔排序的代码。
下图方法的思路是：逐步的遍历每个子表，在逐步遍历过程中使得每个子表都更有序一点，循环往复。
在这里插入图片描述

第一趟分别比较76和49，13和39，27和65，49和97.
第一趟结束时，第二趟开始时如下：

第二趟:d=4/2=2，从27开始比较，++i，顺次比较49和之前的13，比较76跟之前的27，38和之前的49，65和之前的76，97和之前38。
在这里插入图片描述
第二趟结束时，第三趟开始时如下：

第三趟结束时如下

算法性能分析

在这里插入图片描述

因为需要用增量d来快速的找到与之相邻的从属于同一个子表的元素，所以只有具有随机访问的特性才能完成这个事情。所以必须用顺序表。

8.3-1冒泡排序

在这里插入图片描述

算法实现

升序排列，从后往前冒泡，将小的值冒泡到前面。
当然也可以从前往后冒泡。
在这里插入图片描述

算法性能分析

在这里插入图片描述

冒泡排序适用于链表

在这里插入图片描述

8.3-2 快速排序

快速排序算法思想

在这里插入图片描述

快速排序代码

在这里插入图片描述

算法效率分析

时间复杂度

在这里插入图片描述
下面的分析是不严谨的，因为比较一次元素可能带来元素的移动，也可能不带来元素的移动，这里我们按照比较一次元素就按O(1)计算。那么比如下图这个初始序列，要比较每一个元素，所有我按O（n）处理。
在这里插入图片描述

空间复杂度

QuickSort（）函数在执行时，不断地递归会占用多层递归工作栈，所以这里空间复杂度和递归层数有关。空间复杂度=O(递归层数)

在这里插入图片描述

把快速排序过程梳理成二叉树

在这里插入图片描述

最坏的情况

若给的序列是有序的，那么每次划分都很不均匀
在这里插入图片描述

比较好的情况

优化思路②随机选一个元素作为枢轴元素：因为是随机的，所以不太可能每次都选到最大的或者最小的，所以划分比较均匀。
在这里插入图片描述

实际应用中

在实际应用当中，快速排序算法的平均时间复杂度其实要接近于最好的时间复杂度，而不是接近最坏，所以在实际应用当中，快排这个算法是所有内部排序算法当中平均性能最优的排序算法。
在这里插入图片描述

稳定性

在这里插入图片描述

1比2小，转移到数组编号0的位置。

总结

在这里插入图片描述

8.4-1简单选择排序

在这里插入图片描述
下图有两个49，当49是最小的时，我们优先将最前面的49移动到头部的位置使之有序。

算法性能分析

n个元素的简单选择排序需要n-1趟处理。
在这里插入图片描述

稳定性分析

在这里插入图片描述

8.4-2 堆排序

什么是堆？

在这里插入图片描述
回忆二叉树的顺序存储
大根堆

小根堆

如何基于堆进行排序

在这里插入图片描述
建立大根堆

从n/2 的位置 8/2即4的位置开始逐个往前检查。
9不大于他的左孩子32，互换位置。

互换后符合大根堆

检查78，78小于右孩子87，互换位置。

交换位置后符合大根堆

检查17，17小于右孩子45，互换位置
在这里插入图片描述
交换位置后符合大根堆

检查53，53小于其右孩子87

交换位置后，53引起了其下层子树不符合大根堆要求，

采取同样的方式检查53，53小于其右孩子78，交换位置。

调整完成

建立大根堆的代码

在这里插入图片描述
这里我们直接快进到代码执行到53这个元素。

基于大根堆进行排序

将87与待排序序列的最后一个元素9交换
在这里插入图片描述
87和09交换完成，87不需要再移动

将待排序元素序列再次调整为大根堆

小元素09下坠第一次

小元素09下坠第二次

经过调整后待排序元素序列再次构成一个“大根堆”

将78跟待排序序列的最后一个元素交换。
在这里插入图片描述
53被交换到第一个元素的位置

53下坠一次，由于78已经被排好序了，不在待排序序列中了，所以不用在比较53和78了，下图虚线的就不用再比较了。

经过调整后待排序元素序列再次构成一个“大根堆"

将65和待排序序列中的最后一个元素交换。
在这里插入图片描述
9被换到第一个位置，继续小元素下坠

将53与待排序序列中的最后一个元素交换，

将17进行下坠

17下坠一次，还没形成大根堆

17下坠第二次，形成大根堆

将45和17进行交换，

17下坠一次，形成大根堆
在这里插入图片描述
将来32和9交换，

9下坠一次形成大根堆

将17和待排序元素序列中的元素9交换，只剩下一个元素9，不用再调整。

基于大根堆进行排序（代码）

在这里插入图片描述

算法效率分析

在这里插入图片描述
下方有两个孩子，则“下坠”一层，需对比左右孩子各1次

下方只有1个孩子，则“下坠”一层，需对比左孩子1次。i<len说明没有右孩子。

时间复杂度1：建堆的过程（每个关键字都可能下坠）

第1层有1个结点，最多下坠（h-1）层，每个结点最多对比关键字不超过2（h-1）
第2层有2个结点，最多下坠（h-2）层，每个结点最多对比关键字不超过2（h-2），第二层最多对比关键字不超过22（h-2），
第h层不下坠，
第h-1层有2的h-2次方个结点，最多下坠1层，每个结点最多对比关键字不超过2，第二层最多对比关键字不超过22的h-2次方，
在这里插入图片描述

时间复杂度2：每一趟调整的过程（由于已经建完堆了，双亲结点大于孩子结点，所以将一个元素下坠，无需担心被调整上去的元素造成大根堆的破坏，只需要考虑下坠元素即可，而下坠元素最多下坠次数不会超过树的高度h）

在这里插入图片描述

空间复杂度：只用到了几个 i 这样的变量，所以是常数级O(1)

在这里插入图片描述

稳定性分析

在这里插入图片描述

2杠和最后一个2交换，

未破坏大根堆，将第一个2和1交换，

还剩一个元素1，算法结束。结果显示是不稳定的。

8.4-3 堆的插入删除

插入

插入13

在这里插入图片描述
13和32比较一次，上升一层，

13和17比较一次，上升一层，17和9比较一次，17>9,无法上升，程序停止。共比较了3次关键字。

插入46

在这里插入图片描述

删除

在这里插入图片描述
删除13，

用堆底元素46替代被删除元素的位置。

46下坠第一次，比较左右孩子各一次

46下坠第二次，比较左右孩子各一次。以上共对比关键字次数4次

关键字对比次数

在这里插入图片描述

8.5-1 归并排序

什么是归并？

在这里插入图片描述

2路归并和4路归并

在这里插入图片描述

代码实现Merge函数

在这里插入图片描述
归并排序有稳定性

代码递归实现MergeSort

在这里插入图片描述

算法效率分析

第一次归并对比关键字次数3次，相当于n/2,是O(n)数量级。
第三次归并：每对比关键字一次，就能挑出一个当前还剩余的更小的元素。最多进行n-1次关键字的对比，就能完成一趟归并。
所以不管是那一次的归并，都是O（n）的数量级的时间。
在这里插入图片描述

8.5-2 基数排序

基数排序示例

第一趟

在这里插入图片描述

靠近队头的连在前面，靠近队尾的连在后面。

第二趟

在这里插入图片描述

第三趟

在这里插入图片描述

基数排序总体顺序

在这里插入图片描述

基数排序得到递减序列的过程

在这里插入图片描述

基数排序得到递增序列的过程

在这里插入图片描述

算法效率分析

每新增一个队列就是新增两个指针域的空间。
下图r就是10，代表0-9 10个辅助队列，
d就是关键字能被拆成几个部分。
每次分配其实就是从头到尾把链表元素扫一遍，有n个元素，扫一遍需要有O（n）的时间。
一次收集就是逐个的扫描这些队列，把这些队列上的元素都给拆下来，合成一条新链表。
在这里插入图片描述
收集一个队列只需O（1）的时间，如下图，后，这一队列的全部元素就串到下面的链表中了，只需要O（1）的时间。

稳定性分析

在这里插入图片描述

8.7-1 外部排序

外部排序使用的是归并排序

磁盘的读/写以“块"为单位数据读入内存后才能被修改修改完了还要写回磁盘。
“归并排序”要求各个子序列有序，每次读入两个块的内容,进行内部排序后写回磁盘。所以先进行一次内部排序将各个初始归并块有序，后面才能进行归并排序。
若要进行k路归并排序，则需要在内存中分配k个输入缓冲区和1个输出缓冲区。
在这里插入图片描述