内部排序
【sort】既是一种 排序过程，也是一种 分类过程 【稳定性】排序结果中，相同关键词的相对位置没有发生变化
分类¶
内部排序算法分类
| 类别 | 思想 | 种类 |
|---|---|---|
| 插入类 | 将元素 插入 到有序序列中 | 直接插入排序；折半插入排序；希尔排序；二路插入排序；表插入排序 |
| 交换类 | 在无序序列中进行两两 交换，最终会在一端得到一个最值 这也就是该元素的最终位置 |
起泡排序；快速排序 |
| 选择类 | 从无序序列中 选择 出最值元素，并加入到有序序列中 | 简单选择排序；树形选择排序；堆排序 |
| 归并类 | 通过 归并 两个或两个以上的子序列 | 二路归并排序 |
| 基数类 | 不需要关键字之间的比较和移动 基于多关键字排序的思想，把一个逻辑关键字拆分成多个关键字 例如：准备10个桶，编号为0-9，按照数字的某一位进行归类，然后按顺序选出 |
基数排序 |
各算法简介¶
| 算法名称 | 介绍 | 评价 | 平均 | 最好 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|---|---|---|
| 直接插入排序 | 每趟选一个插入 | 已经有序的话，只要遍历一次，不需要插入 | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | 稳定 |
| 折半插入排序 | |||||||
| 希尔排序 | 用步长划分成子序列，分别插入排序 | \(O(nlog_2n)\) | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | 不稳定 | |
| 冒泡排序 | 两两交换 | 已经有序的话，只要遍历一次，没有交换就结束 | \(O(n^2)\) | \(O(n)\) | \(O(n^2)\) | \(O(1)\) | 稳定 |
| 快速排序 | 比小明高的站右边，矮的左边 | 越有序越费劲 | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(n^2)\) | \(O(log_2n)\) | 不稳定 |
| 简单选择排序 | 每趟选出一个最值 | 比较次数与初始序列无关 | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | 不稳定 |
| 堆排序 | 用堆来选择最值 | 比较次数与初始修了有关 | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(1)\) | 不稳定 |
| 二路归并排序 | 分成n个子序列，两两序列归并 | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(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)，除了堆排序 |