排序篇(七大基于比较的排序算法)
目录
插入排序
直接插入排序
希尔排序(缩小增量排序)
选择排序
选择排序
堆排序
交换排序
冒泡排序
快速排序
1.挖坑法
2.Hoare版
3.前后指针
快速排序优化
三数取中法 选基准数
2.递归到小的子区间时 可以考虑使用插入排序
非递归快速排序
归并排序
归并排序----非递归
其他非基于比较的排序
计数排序
几种常见的排序算法：
1.插入排序：直接插入排序、希尔排序
2.选择排序：选择排序、堆排序
3.交换排序：冒泡排序、快速排序
4.归并排序：归并排序
接下来我们一一讲解
插入排序
直接插入排序
思想：
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
简单点说 就是在已排好序的区间中 找到当前元素(无序区间)的应插入位置
代码实例：
特性：
时间复杂度：O(N^2)
空间复杂度：O(1) 它是一种稳定的排序算法
这里我们对稳定做下解释 当一个数组中 当采用某一排序算法时 重复数据原先在前面的仍在前面 这便称之为稳定
关于时间复杂度的分析：
· 最好情况下 也就是有序的时候 我们不需要移动元素 每次只需要比较一次即可 那么最好情况时的时间复杂度为O(N)
· 最坏情况下 也就是待排序区间为逆序的情况
例如： 9 8 7 6 5 (需要排为升序)
此时需要比较 1+2+3+4=10次
如果有n个元素的话 则需要比较1+2+3+....+(n-1)=n*(n-1)/2
所以最坏时间复杂度为:O(N^2)
空间复杂度分析：
插入排序不需要额外的存储空间 所以其空间复杂度为O(1)
稳定性分析：
根据插入排序思想可知 我们只会移动比temp值大的元素 所以我们排序后可以保证相同元素的相对位置不变 所以直接插入排序是稳定的
希尔排序(缩小增量排序)
思想：先选定一个整数gap 把待排序文件中所有记录分成多个组 所有距离为该整数gap的记录分在同一组内 并对每一组内的记录进行排序 然后 重复上述分组和排序的工作
直到该整数=1时 所有记录最后再统一排好序
特性：
1.希尔排序是对直接插入排序的优化
2.当gap>1时 都是预排序 目的是 让数组更接近于有序 当gap==1时 数组已经接近有序 这样就会很快 这样整体而言 可以达到优化的效果
3.希尔排序的时间复杂度不好计算 因为gap的取值方法有很多 导致很难去计算 因此在好些书中给出的希尔排序的时间复杂度都不固定
4.当然 希尔排序是不稳定的
代码实例：
选择排序
选择排序
基本思想：每一次从待排序的数据元素中选出最小(或最大)的一个元素 存放在序列的起始位置 直到全部待排序的数据元素排完
例如升序：每一次从待排序的数据元素中 找到最小的那个元素 存放在序列的起始位置
代码1：
关于选择排序 我们还有另一种方法：同时找到最大和最小的元素 的下标 每次排好两个元素
代码实例：
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
堆排序
堆排序(HeapSort)是指利用堆积树(堆：完全二叉树)这种数据结构所设计的一种排序算法 它也是选择排序的一种 它是通过堆来进行选择数据
需要注意的是：排升序要建大堆 排降序要建小堆
现在我们来理解一下 什么是大/小堆
大堆：每个结点的值都不大于其父节点的值(也就是 结点的值较大)
小堆：每个结点的值都不小于其父节点的值(也就是 结点的值较小)
大堆(结点的值较大)：
数组{6,7,9,4,5,1,3}建好大堆如下图：
小堆(结点的值较小)：
看了这两张图后 我们发现 即使建好大堆/小堆后 仍然需要排序
大概流程：建大堆(升序)---->然后需要将根节点和从最后一个元素进行交换(根节点的值是最大的) 然后再重新建大堆 直到每个元素都与根节点交换过
现在呢 我们先进行建大堆：
首先呢 先创建parent child两个变量
parent指向最后一棵树的根 child指向最后一棵树的子树 然后依次将每棵树置成大堆
即：让child指向子树元素较大的 若child指向位置的元素大于parent处的元素 则交换
然后令parent-- 直到parent走到0下标处
接下来我们给出上述图片转化为大堆的过程图
当child指向超过下标最大值时 siftDown结束
展示代码：
在创建好大堆以后 我们就需要将根节点的数 与end指向的元素 进行交换
然后再重排大堆 让end--
整体代码：
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
交换排序
冒泡排序
这里我们就不对冒泡排序进行讲解了 在之前有讲过
如果大家有些遗忘 可以通过下列链接进行复习
https://blog.csdn.net/L2770789195/article/details/137197253
快速排序
基本思想：任取待排序元素序列中的某元素作为基准值 按照该基准值 将待排序集合分割成两个子序列 左子序列中所有元素均小于基准值 右子序列中所有元素均大于基准值 然后重复该过程 直到所有元素都排列在相应位置上为止
1.挖坑法
我们先给个排序过程图：
代码实现
2.Hoare版
这个跟挖坑法也很相似 只是没有坑 当选择L处的元素作为基准值时 先让R移动 找到小于基准值的数 让L移动 找到大于基准值的数 然后让L、R两处的元素进行交换 当L、R相遇时 让相遇处的元素与基准数进行交换 然后在L、R相遇处的左右两侧接着重复上述步骤
3.前后指针
初始时 prev指针指向序列开头 cur指针指向prev指针的后一个位置
cur指针向后移动 寻找比基准值小的元素
当找到比基准值小的元素时 如果 ++prev和cur不相等 则交换prev和cur位置处的元素
这样做的原因是：cur和prev本身相差一个距离 当cur碰到几个大于基准值的元素时 prev就会与cur的距离增加几个距离 prev会停留在大于基准值处 当cur再次找到比基准值小的元素时 则可以把小于基准值的元素与大于基准值的元素进行交换 直到cur走到数组之外
代码实例：
总结:在这三种方法中 我们使用挖坑法最多 其次是Hoare法 至于前后指针已经使用的很少了
对于快速排序的过程 其实可以形象地用递归树来表示
具体来说 快速排序的递归树中的每个结点代表一次递归调用 左子树代表 对小于基准值的子数组进行排序的递归调用 右子树代表对大于基准值的子数组进行排序的递归调用
快速排序优化
-
三数取中法 选基准数
我们前面的基准数 选择的都是Left处的元素(也就是每个数组的最左侧元素)
但基准数当选择的过大或者过小时 会让数组排序的次数增加
如下图：
我们可以看到当选择的基准数过大时 会导致每次只排好一个元素或者很少的元素
而如果当选择的基准数为中间的数时 每次会排好一半的元素 大大减少了时间
所以我们三数取中法是 在最左侧、最右侧和中间的数中 选择某一位于两者区间的数
代码实例：
2.递归到小的子区间时 可以考虑使用插入排序
我们知道快速排序 每次会数组分成两个部分 类似于二叉树
这里 我们借用下之前的图：
在这里我们更加明显的看到了二叉树的样子
我们把每个圈当成一个数组 每次排序就会分成两个数组
当某一数组被分成另外几个数组时 也就是某一次递归 递归到剩余的几次 我们就可以采取直接插入排序
我们在前面都是用递归实现快速排序的
现在我们来学习一下非递归的快速排序
非递归快速排序
我们知道在使用递归的快速排序中 递归起到了将数组一分为二的作用
所以我们的非递归排序的核心就是 如何将数组一分为二
这里我们需要一个栈来配合
先利用自已写过的代码(partition)找到基准数要替换到的位置--pivot
注意：partition在找到基准值要替换的位置的同时 也进行着将小于基准数的划分到左边 将大于基准数的划分到其右边
让基准数左右两侧数组的起始和结尾的下标入栈
注意：当基准数某一侧只剩下一个元素时 代表着已经有序 不需要再进行排序
当pivot满足pivot>left+1或pivot<right-1 代表着至少有两个元素---》即需要入栈 排序
代码如下：
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定
归并排序
基本思想：
归并排序（Merge Sort）是一种分而治之的排序算法。它将一个大的列表分成两个小列表，分别进行排序，然后将排序好的小列表合并成一个最终的排序列表。这个过程递归地进行，直到子列表的大小为1（因为只有一个元素的列表自然是排序好的）
归并排序算法主要包含两个主要步骤：
分解：将数组分解成两个较小的子数组，直到子数组的大小为1。
合并：将已排序的子数组合并成一个大的有序数组，直到合并为1个完整的数组
过程实例：
代码实现：
归并排序----非递归
在递归的归并排序中 递归的作用在于将数组进行分解
所以我们在 非递归中主要是将数组进行分解
我们利用gap当作每个子数组的大小
利用left mid right来指示要合并的区间
代码实现：
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
其他非基于比较的排序
计数排序
思想：计数排序又称为鸽巢原理 是对哈希直接定址法的变形应用
操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
例如：
但也有一个问题 假如数组arr存放的是 {90,95,91,92,90,92} tmp数组难道还要申请100个空间吗？
其实不然 我们仍然只需要申请max-min+1个空间 即：6个空间(下标：0~5)
只需要在放入tmp数组时 让 下标=元素-min
在tmp数组中 取出元素放入arr的时候 让元素=下标+min 即可
代码实现：
计数排序总结：
- 计数排序在数据范围集中时 效率很高 但是适用范围及场景有限
- 时间复杂度：O(N+(arr的长度))
- 空间复杂度：O(arr的长度)
- 稳定性：稳定
排序算法总结：
