【排序算法】排序算法总结

【排序算法】—— 排序算法总结

一、排序算法的分类

排序算法 就是通过算法将数据排成一定的次序

按照排序原理以将常见的排序算法分为5部分

排序的位置可以是内存，也可以是外部存储设备，内存内的排序叫做内排序，在内存外的排序叫做外排序

在进行外排序的时候需要进行大量的文件操作，而且外部存储设备的读写速度要远远慢于内存的读写速度，所以外排序并不常用，只有很大的文件，一次无法全部加载进内存时会使用外排序，外排序通常使用归并排序完成。

稳定性：排序算法的稳定性是指排序时，元素的位置相对于相同元素的位置不发生改变。对于单一的数据类型来说稳定性并没有什么影响，但是对于结构体类型来说，利用元素的一个成员变量排序，相同的该成员变量的元素相等时，其他成员变量的值可能并不相等。

排序方法	稳定性	备注
直接插入排序	稳定	从前往后依次插入，不改变相同元素次序
希尔排序	不稳定	预排序时，相同元素可能分到不同组
简单选择排序	不稳定	交换数据时可能将数据交换到相同元素的后面。如`8 9 8 9 5 5`
堆排序	不稳定	建堆过程向下调整时，相同元素的交换并不是按照元素原本的顺序
冒泡排序	稳定	相邻的数据，相同的数据不交换，非常稳定
快速排序	不稳定	与基准值`key`相同的可能在基准值的左边或右边
归并排序	稳定	两个有序数组排序合并的方式，遇到相同数据时以第一个数组优先
计数排序	稳定	只有整数类型的数据可以排序，稳定性没有意义

对于基数排序和桶排序的实用性不高，所以在此并没有实现。

点击以下表格对应的排序方式名称就可以跳转到对应的排序详解（C语言实现）

排序方式	时间复杂度	空间复杂度	稳定性	特点
冒泡排序	$O(n^2)$	$O (1)$	稳定	简单，好实现
直接插入排序	$O(n^2)$	$O (1)$	稳定	有序效率最高执行n次，逆序效率最低 $n^2$ 次
简单选择排序	$O(n^2)$	$O (1)$	不稳定	有序无序都是 $O(n^2)$ ，是效率最差的算法之一
希尔排序	$O (n l o g n)$	$O (1)$	不稳定	预排序和插入排序两步，最好情况效率是 $O(n^{1.3})$
堆排序	$O (n l o g n)$	$O (1)$	不稳定	建堆和选数两步，最实用的是解决Top k问题
快速排序	$O (n l o g n)$	$O (1)$	不稳定	有序效率最低 $O(n^2)$ ，但是可以解决，是效率最高的算法
归并排序	$O (n l o g n)$	$O (n)$	稳定	需要额外空间，对稳定性要求高的数据会使用
计数排序	$O (m a x (n, 范围))$	$O (范围)$	稳定	使用场景有限，在范围集中的数据下效率最高

相关阅读:
面向对象分析与设计的关系和区别，面向对象的设计概念，面向对象设计准则
【面试专题】设计模式篇①
优维低代码实践：片段
如何使用ps制作ico图标文件
redis副本
想法子记忆Vi/Vim常用操作及指令
2022-09-09 Unity InputSystem1——概述
排序算法（未完）
Jenkins离线插件配置（二）
Java —— 数组

原文地址：https://blog.csdn.net/weixin_52811588/article/details/126850166