排序（数据结构）
排序：
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
常见排序法
. 常见排序算法的实现
插入排序
1.直接插入排序
2.希尔排序( 缩小增量排序）
希尔排序的特性总结：
1.
希尔排序是对直接插入排序的优化。
2.
当
gap > 1
时都是预排序，目的是让数组更接近于有序。当
gap == 1
时，数组已经接近有序的了，这样就会很 快。这样整体而言，可以达到优化的效果。
3.
希尔排序的时间复杂度不好计算，因为
gap
的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排 序的时间复杂度都不固定
选择排序
直接选择排序:
在元素集合
array[i]--array[n-1]
中选择关键码最大
(
小
)
的数据元素
若它不是这组元素中的最后一个
(
第一个
)
元素，则将它与这组元素中的最后一个（第一个）元素交换 在剩余的array[i]--array[n-2]
（
array[i+1]--array[n-1]
）集合中，重复上述步骤，直到集合剩余
1
个元素
【
直接选择排序的特性总结
】
1.
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2.
时间复杂度：
O(N^2)
3.
空间复杂度：
O(1)
4.
稳定性：不稳定
堆排序
堆排序
(Heapsort)
是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆 来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
【
直接选择排序的特性总结
】
1.
堆排序使用堆来选数，效率就高了很多。
2.
时间复杂度：
O(N*logN)
3.
空间复杂度：
O(1)
4.
稳定性：不稳定
交换排序
1冒泡排序
【冒泡排序的特性总结】
1.
冒泡排序是一种非常容易理解的排序
2.
时间复杂度：
O(N^2)
3.
空间复杂度：
O(1)
4.
稳定性：稳定
2.快速排序
. Hoare版
挖坑法（优先考虑）
前后指针
快速排序优化
快速排序递归
快速排序非递归
2.3.4
快速排序总结
1.
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫
快速
排序
2.
时间复杂度：
O(N*logN)
3.
空间复杂度：
O(logN)
4.
稳定性：不稳定
归并排序
归并排序总结
1.
归并的缺点在于需要
O(N)
的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2.
时间复杂度：
O(N*logN)
3.
空间复杂度：
O(N)
4. 稳定性：稳定
记数排序
【计数排序的特性总结】
1.
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2.
时间复杂度：
O(MAX(N,
范围
))
3.
空间复杂度：
O(
范围
)
4.
稳定性：稳定
排序算法复杂度及稳定性分析总结
原文地址：https://blog.csdn.net/2301_80363309/article/details/144030703
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！