数据结构与算法——排序算法

���录

文章目录

前言

一.排序的基本概念

1.什么是就地排序

2.什么是内部排序和外部排序

3.什么是稳定排序

4.判定一个排序算法的是稳定的

二.插入排序算法

1.直接插入排序

1.1基本思想

1.2复杂度

1.3稳定性

1.4代码演示

2.折半插入排序

2.1基本思想

2.2性能

3.2-路插入排序算法

4.希尔排序

4.1基本思想

4.2 性能

4.3Hibbard增量序列

4.4更多的增量序列

4.5代码演示

三.交换排序

1.冒泡排序

1.1算法思想

1.2关于冒泡的优化

1.3复杂度分析

1.4如何用两个栈实现冒泡

1.5详细解析

1.6代码演示

2.快速排序

2.1算法思想

2.2复杂度分析

2.3快速排序的稳定性从哪里来

2.4代码演示

四.归并和计数排序

1.归并排序

1.1算法思想

1.2复杂度分析

1.3代码演示

2.计数排序

2.1算法思想

2.2稳定性

2.3复杂度分析

3.桶排序

3.1桶排序的思想

3.2关于桶排序的算法分析

3.3桶排序适用情况

4.基数排序

4.1算法思想

4.2复杂度分析

五.选择排序（二叉堆）

1.堆

2.二叉堆

3. 二叉堆的存储结构

4. 小顶二叉堆常见的操作

5.简单的选择排序与堆排序代码演示

---

文章目录

• 前言
• 一.排序的基本概念
• 二.插入排序算法
• 三.交换排序
• 四.归并排序和计数排序
• 五.选择排序（二叉堆）
• 总结

  ---

  前言

  排序算法的重要性不言而喻在算法竞赛中经常考到因此我们要好好学习！

  ---

  一.排序的基本概念

  1.什么是就地排序

  使用恒定的额外空间，只需要使用他给你的数据

  一个就地排序算法使用恒定的的额外空间来产生输出（仅修改给定的数组）。它仅通过修改线性表中元素的顺序来对线性表进行排序。

  例如，插入排序和选择排序是就地排序算法，因为它们不使用任何额外的空间来对线性表进行排序。而归并排序和计数排序的经典实现就不是就地排序算法

  2.什么是内部排序和外部排序

  待排序数据，是否可以一次性的载入到内存中

  当所有待排序记录不能被一次载入内存进行处理时，这样的排序就被称为外部排序。

  外部排序通常应用在待排序记录的数量非常大的时候。归并排序以及它的变体都是典型的外部排序算法。外部排序通常与硬盘、CD等外部存储器（辅存）关联在一起。当所有待排序记录可以一次载入内存时，则称为内部排序。

  3.什么是稳定排序

  判断相同的关键字，排序以后，相对位置的变化，处理键值对的时候

  当我们对可能存在重复键的键值对（例如，人名作为键，其详细信息作为值）按照键对这些对象 进行排序时，稳定性就显得至关重要

  4.判定一个排序算法的是稳定的

  如果两个具有相等关键字的对象在排序前后的相对位置没有发生变化，则认为排序算法是稳定的。可以形式化地描述为：

  设A表示一个待排序的数组， 9，顺序没有问题。不动。

  第二次插入：将13与20比较，139，那么此时

  将13插入到9后面

  第三次插入，将10和20比较，10 2，交换 5 和 2 的位置：

   第四步：比较 5 和 8 ，5

   第五步：比较 8 和 4 ， 8 > 4，交换 8 和 4 ：

  此刻我们获得数组当中最大的元素 8 ，使用橘黄色进行标记：

  第一轮冒泡结束，最大的元素8到了最后，然后对于前面5个元素，进行第二轮冒泡最终结果：

  事实上第二阶段结束，整个数组已经有序了，但是对于冒泡排序而言并不知道，她还需要通过第三阶段的比较操作进行判断。

  对于冒泡排序算法而言，她是通过判断整个第三阶段的比较过程中是否发生了交换来确定数组是否有序的，显然上面的过程中没有交换操作，冒泡排序也就知道了数组有序，整个算法执行结束

  1.2关于冒泡的优化

  基本的冒泡排序的实现方式，就是两个for循环，持续比较和交换。这种实现方式有一个明显的弊端，就是不论数组是否有序，两层 for 循环都要执行一遍，而我们是希望数组有序的时候，仅进行一轮判断，或者一轮都不进行（当然不判断，排序算法是不能知道数组是否有序的）

  一次优化

  这里我们增加了一个标识数组是否有序 ，当冒泡排序过程中没有交换操作时， swapped =false ，也意味着数组有序；否则数组无序继续进行冒泡排序。不要小看这个变量，因为这个变量，当数组有序的时候，冒泡排序的时间复杂度将降至 (因为其只需要执行一遍内层的 for 循环就可以结束冒

  泡排序)，没有这个变量，数组有序也需要的时间复杂度

  二次优化

  一次优化是为了避免数组有序的情况下，继续进行判断操作的。那么二次优化又为了什么呢？

  我们看下面的例子

  经过一次冒泡后，我们会注意到一个问题，但是我们注意到，数组数组中的 [5,6,8] 本身已经有序，而对于有序的部分进行比较是没有意义的，相当于在白白浪费资源，有没有什么办法减少这样的比较次数呢？换句话说，是否能够确定出已经有序部分和无序部分的边界呢？

  答案当然是肯定的，这个边界就是第一趟冒泡排序的过程中最后一次发生交换的位置 j ：也就是1 和 4 发生交换之后，4 和 5 没有发生交换，此时 1 之后的元素为有序。

  第一步：4 和 2比较，4 > 2 ，交换 4 和 2 ，将 LastSwappedIndex = 0 ；

  第二步：4 和 1 比较，4 > 1，交换 4 和 1， LastSwappedIndex = 1 ；

  第三步：比较 4 和 5 ， 4

  第四步：比较 5 和 6 ，不交换， lastSwappedIndex 也不更新;

  第五步：比较 6 和 8 ，不交换， lastSwappedIndex 也不更新;

  第一趟冒泡排序结束了，这里似乎看不出和之前有什么区别，但是来看第二趟冒泡排序就不一样了，此时 j 的 取值将从 j = 0 到 j = lastSwappedIndex ，第一步：比较 2 和 1 ，2 > 1，交换， lastSwappedIndex = 0 ，并且第二趟冒泡也就结束了，也就说我们节省了 从 2 到 6的比较操作；

  最后再来一趟冒泡排序，发现没有任何交换，所以冒泡排序结束。

  相比于一次优化的实现方式，二次优化的实现方式进一步减少了不必要的执行次数，两种优化后的实现方式需要冒泡排序的趟数是一样的，本质上没有什么区别。所以即使对于一个有序的数组，两种方式的时间复杂度都是O（n）

  1.3复杂度分析

  时间复杂度：

  最坏情况下（数组逆序）：

  当 i == 0 的时候，j 的取值范围是从 0 到 n -1，内循环的执行判断和交换操作 n - 1 次；当 i == 1的时候，j 的取值范围是从 0 到 n -2，内循环的执行判断和交换操作 n - 2 次；以此类推......当 i 取最大值n - 2 时，j 的取值为 1，内循环的执行判断操作 1 次；所以，整体内循环的判断语句执行次数就是：1 +2 + 3 + ... + (n - 2) + (n - 1) 。则最坏情况下的时间复杂度为O（n^2）量级。

  最好情况下（数组有序）：

  当 i == 0 的时候， swapped = false ，j 的取值范围是从 0 到 n -1，内循环的执行判断操作 n -1次，但是没有发生交换操作，冒泡排序算法直到数组已经有序，所以执行结束。则最好情况下的时间复杂度为O（n）。

  空间复杂度：

  冒泡排序没有使用任何额外的空间，空间复杂度为 O（1），是典型的原地排序算法

  稳定性分析：

  我们可以发现，两个 4 的相对位置没有发生变化，也就是说冒泡排序是稳定的。但这仅相当于实验验证，而在理论上冒泡排序为什么是稳定的呢？

  本质原因在于冒泡排序比较和交换的是两个相邻元素，对于键值相同的关键字是不交换位置的，所以排序前后键值相同的关键字的相对位置才保持不变的

  1.4如何用两个栈实现冒泡

  对于这个问题本身，你可能会觉得没有任何意义，但是当你去努力实现的时候，就会发现，你对于栈和冒泡排序的理解有了新的见解。

  问题本身不难理解，就是利用两个栈，然后每一次选择出数组中最大的元素，并存入数组对应的位置。但是当你自己去实现时，还是会发现好多问题，比如如何互换着使用两个栈？如何对栈中相邻的两个元素比较大小，并交换位置？

  下面是参考的思路：

  给定两个栈 s1 和 s2 ，以及一个长度为 n 的数组 arr :

  1、将数组 arr 中的所有元素压入栈 s1 当中；

  2、执行 for 循环 n 次（每一次选择出一个最大的元素）：

  1. 情况一： s1 不为空， s2 为空，则尝试将栈 s1 当中的所有元素压入栈 s2 ，并保证 s2的栈顶元素为最大值；当 s1 为空时， s2 中的栈顶元素即为栈中元素的最大值，插入数组相应位置。

  2. 情况二： s2 不为空， s1 为空，则尝试将栈 s2 当中的所有元素压入栈 s1 ，并保证 s1的栈顶元素为最大值；当 s2 为空时， s1 中的栈顶元素即为栈中元素的最大值，插入数组相应位置。

  1.5详细解析

  初始时两个栈 s1 和 s2 都为空栈，数组 arr[] = [5,1,4,2,8] 。

  第一步：将数组 arr 中的所有元素都压入栈 s1 当中：

  第二步：栈 s2 为空，直接将 s1 的栈顶元素 8 压入栈 s2 

  第三步：栈 s1 不为空，尝试将 s1 的栈顶元素 2 压入栈 s2 ，但是此时 s2 的栈顶元素 8 >2，所以利用一个临时变量 tmp 交换两个元素在栈中的位置，先将 s2 的栈顶 8 保存到 tmp 并弹出，然后压入元素 2 ，最后再将8重新入栈。(其实就是交换操作)

   第四步：栈 s1 不为空，同第三步一样将 s1 的栈顶元素压入栈 s2 当中：

  第五步：栈 s1 不为空，同上将 s1 的栈顶元素 1 压入栈 s2 当中： 

  第六步：栈 s1 不为空，同上将 s1 的栈顶元素 5 压入栈 s2 当中： 

  之后的过程和前面讲的类似，将栈 s2 中的元素压入栈 s1 当中，并找到次大元素 5 ，以此类推，实现对数组的冒泡排序

  1.6代码演示

  #include#include#define maxx 100/*所谓交换,是指根据序列中两个关键字比较的结果来对换这两个关键字在序列中的位置。*/int a[maxx],n,t;int v;//标记 int main(){scanf("%d",&n);for(int i=1;i