数据结构学习笔记（六）——排序

七、排序

算法的稳定性: 若待排序表中有两个元素 $R_i$ 和 $R_j$ ，其对应的关键字 $key_i=key_j$ ，且在排序前 $R_i$ 在 $R_j$ 前面，若使用某一排序算法排序后， $R_i$ 仍然在 $R_j$ 的前面，则称这个排序算法是稳定的。否则称排序算法是不稳定的。

在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类：内部排序和外部排序。

内部排序，是指在排序期间元素全部存放在内存中的排序；
外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，知道全部记录插入完成。

直接插入排序算法中，不难看出每趟插入的过程中，都进行了两项工作：

注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。（折半查找需要能随机访问，因此排序表应该顺序存储）

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

选择排序的基本思想是：每一趟（如第 $i$ 趟）在后面 $n-i+1(i=1,2,\cdots, n-1)$ 个待排序元素中选取关键字最小的元素，作为有序子序列的第 $i$ 个元素，直到第 $n - 1$ 趟做完，待排序元素只剩下1个，就不用再选了。

中文名称	英文名称	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
选择排序	Selection	$n^2$	$n^2$	$n^2$	1	不稳
冒泡排序	Bubble	$n^2$	$n^2$	$n$	1	稳
插入排序	Insertion	$n^2$	$n^2$	$n$	1	稳
快速排序	Quick	$nlog_2n$	$n^2$	$nlog_2n$	$log_2n$	不稳
归并排序	Merge	$nlog_2n$	$nlog_2n$	$nlog_2n$	$n$	稳
堆排序	Heap	$nlog_2n$	$nlog_2n$	$nlog_2n$	1	不稳
希尔排序	Shell	$n^{1.3}$	$n^2$	$n$	1	不稳
桶排序	Bucket	$n + k$	$n^2$	$n$	$n + k$	稳
计数排序	Counting	$n + k$	$n + k$	$n + k$	$n + k$	稳
基数排序	Radix	$n * k$	$n * k$	$n * k$	$n + k$	稳

忆排序面试我最强
选泡插，
快归堆希桶计基，
恩方恩老恩一三，
对恩加K恩乘K，
不稳稳稳不稳稳，
不稳不稳稳稳稳！

相关阅读:
【iOS】—— 单例模式
Leetcode 238. 除自身以外数组的乘积
关于vuex仓库管理
ROS1可视化利器---Webviz
springboot毕设项目超市收银与会员管理系统6l826（java+VUE+Mybatis+Maven+Mysql）
深入浅出三户模型
Jenkins - macOS 上安装
如何释放服务器内存
android V2签名三方app预置方法
Django更换数据库和迁移数据方案

原文地址：https://blog.csdn.net/static_eye/article/details/125594695