内部排序

【sort】既是一种 排序过程，也是一种 分类过程 【稳定性】排序结果中，相同关键词的相对位置没有发生变化

分类

内部排序算法分类

类别	思想	种类
插入类	将元素 插入 到有序序列中	直接插入排序；折半插入排序；希尔排序；二路插入排序；表插入排序
交换类	在无序序列中进行两两 交换，最终会在一端得到一个最值 这也就是该元素的最终位置	起泡排序；快速排序
选择类	从无序序列中 选择 出最值元素，并加入到有序序列中	简单选择排序；树形选择排序；堆排序
归并类	通过 归并 两个或两个以上的子序列	二路归并排序
基数类	不需要关键字之间的比较和移动 基于多关键字排序的思想，把一个逻辑关键字拆分成多个关键字 例如：准备10个桶，编号为0-9，按照数字的某一位进行归类，然后按顺序选出	基数排序

各算法简介

算法名称	介绍	评价	平均	最好	最坏	空间	稳定性
直接插入排序	每趟选一个插入	已经有序的话，只要遍历一次，不需要插入	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
折半插入排序
希尔排序	用步长划分成子序列，分别插入排序		$O(nlo{g}_{2}n)$	$O(n)$	$O(n^2)$	$O(1)$	不稳定
冒泡排序	两两交换	已经有序的话，只要遍历一次，没有交换就结束	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
快速排序	比小明高的站右边，矮的左边	越有序越费劲	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(n^2)$	$O(lo{g}_{2}n)$	不稳定
简单选择排序	每趟选出一个最值	比较次数与初始序列无关	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
堆排序	用堆来选择最值	比较次数与初始修了有关	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(1)$	不稳定
二路归并排序	分成n个子序列，两两序列归并		$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(n)$	稳定
基数排序	不比较，分配收集		$O(d(n+r_d))$	$O(d(n+r_d))$	$O(d(n+r_d))$	$O(r_d)$	稳定

性能表

性能	分析
平均时间复杂度	1. 快速、希尔、归并和堆排序的时间复杂度为O(nlog2n)，其他都是O(n2) 2. 特殊：基数排序O(d(n+rd))；d为关键字位数，r为一位的关键字取值范围，n为数量 【助记】“快些以nlog2n的速度归队”：快（快速排序）、些（希尔排序）、归（归并排序）、队（堆排序）
最坏时间复杂度	1. 快速排序的时间复杂度为O(n2) 2. 其他都和平均情况相等
最好时间复杂度	1. 直接插容易插变成O(n)，起泡起的好变成O(n) 2. “容易插”、“起的好”都是指初始序列已经有序
空间复杂度	1. 快速排序O(log2n) 2. 归并排序O(n) 3. 基数排序O(rd) 4. 其他都是O(1)
稳定性	【助记】考研复习痛苦啊，心情不稳定（不稳定的算法），快（快速排序）些（希尔排序）选（简单选择排序）一堆（堆排序）好友来聊天吧。这4种不是稳定的，其他自然都是稳定的
排序原理	1. 经过一趟排序，就能保证一个元素到达最终位置：起泡、快速（交换类的两种），简单选择、堆（选择类的两种） 2. 排序方法的元素比较次数和原始序列无关：简单选择排序、折半插入排序 3. 排序方法的排序趟数和原始序列有关：交换类的排序 4. 比较类的算法，最坏情况下时间复杂度至少O(log2n)
其他	简单普通的排序方法的升级版的平均复杂度都为O(nlog2n)，最坏的情况都是和没改进的时候一样O(n^2)，除了堆排序

参考文章

1. 十大经典排序算法（动图演示）
2. 10大经典排序算法动图演示，看这篇就够了！（配相应代码）
3. 树形选择排序