目录
1、类别
| 排序算法 | 比较类排序 ——至少O(nlogn) | 交换排序 | 冒泡排序——稳定 |
| 快速排序 | |||
| 插入排序 | 简单插入排序——稳定 | ||
| 希尔排序 | |||
| 选择排序 | 简单选择排序 | ||
| 堆排序 | |||
| 归并排序 ——稳定 | 二路归并排序 | ||
| 多路归并排序 | |||
| 非比较排序 ——可优于O(nlogn)； ——稳定 | 计数排序 | ||
| 桶排序 | |||
| 基数排序 | |||
稳定：相同的两个数，在排序后，保持排序前的相对顺序。——不稳定，无法保证这一点。
2、冒泡排序 Bubble Sort
1、描述
- 比较相邻的元素。排列顺序与目标不一致，就交换它们。
- 从开始第一对到最后一对，做相同工作，这样会得到一个最数在端处。
- 在除 最数 外的数组中重复上述操作，会得到 新的/剩下 数组里的新最数。重复，直至排序完成。
2、分析
- 每次迭代，能保证一个最数排好序
- 迭代次数 n
- 第i次迭代时间：n-i
- 总时间 O（n^2）
- 空间复杂度：O（1）。不需要额外空间
- 稳定
3、选择排序? ?
特点：慢。——没有快的可能
1、描述
- 扫描所有元素，找出最大（或最小）值，取出
- 重复上一操作，直至所有元素排序完毕
2、分析
- 最坏和最好情况一样，需要扫描所有元素
- 迭代次数 n
- 第i次迭代时间：n-i
- 总时间 O（n^2）
- 空间复杂度：O（1）。不需要额外空间
- 可以稳定——设定 ：当值一样，取最早出现的
4、插入排序 Insertion Sort
当排序数量小，是最快的方法。——虽然时间复杂度O（n^2），但它的常数小
1、描述
- 从第一个元素开始，可以认为该元素已经被排序
- 取出下一个元素，在已排序的元素序列中，从后向前扫描。
- 如元素（已排序）大于新元素，将元素移到下一位置
- 重复上一操作，直至找到已排序元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复2~5操作
2、分析
- 迭代次数 n
- 第i次迭代时间
最好情况 1 最差情况 i 平均情况 i/2+ O(1) - 总时间
| 最好情况——已排序 | O（n) |
| 最差情况——逆排序 | O（n^2） |
| 平均情况 | O（n^2） |
- 空间复杂度：O（1）。不需要额外空间
- 可以稳定——设定 ：插入一个新数，插到相等值的数后
3、更进
插入时，把一个新元素和一个排好序的序列比较。——可以用二分查找
- 第i次迭代时间：log i
- 比较次数：O（nlogn）
- 但支持二分查找的数据结构，插入操作需要时间 O（n）
- 比较次数少了，但插入时间多了。仍 O（n^2）
5、希尔排序 Shell Sort / 缩小增量排序
简单插入排序的改进版。
会优先比较距离较远的元素。——与插入排序的不同之处
1、描述
整个待排列序列分割为若干子序列，分别进行直接插入排序
? ? ? ? ? ?
2、分析
- 迭代次数 log（n）
- 平均时间：O（n^1.3）
- 最坏时间 O（n^2）——可因gap选择策略而不同，有策略可以减至O（n^1.5）以下
- 空间复杂度：O（1）。不需要额外空间
- 不稳定
6、合并排序 Merge Sort
分治法的典型应用
1、描述
- 分：把长度为n的序列，分成两个长度为n/2的子序列
- 治：对两子序列分别采用合并排序
- 合：将两个排序好的子序列合并成一个最终的排序序列
2、分析
- 迭代次数 log n
- 总时间 O（nlogn）——运行时间很稳定，因合并时间 O（n）
- 空间 O（n）
- 稳定
7、堆排序 Heap Sort
特点：第i次迭代时，已找出了最大（或最小）的i个数
? ? ? ? ? ? ——用时O( i log(n) )
1、描述
- 近似完全二叉树
- 子节点总是小于（或大于）父节点，即最小堆（或最大堆）
2、分析
- 迭代次数 n
- 第i次迭代时间：log（i）
- 总时间 O（nlogn）
- 不稳定
8、快速排序 Quick Sort
最常用排序算法
1、描述
- 选择一个支点数，将所有数与这个支点比较
- 按比较结果，分成小于L，等于M，和大于R三类
- 在L和R里递归调用前两步，就可以将所有的数排好序
2、分析
- 迭代次数?
| 最好情况 | log n |
| 最坏情况 | n |
- 第i次迭代时间：<=n
- 总时间? ? ? ?平均：O（nlogn）；最坏O（n^2）
- 不稳定更快
9、计数排序 Counting Sort
数据分布在某区间，有大量重复
1、描述
- 遍历数据，每遇到一个值，计数数组里对应的值增加1
2、分析（值的空间为k）
- 时间复杂度 O（n+k）——线性的，很快
- 空间复杂度 O（n+k）
- 稳定
10、桶排序 Bucket Sort
划分多个区间（即桶），桶内排序
——高频细分，低频粗分，区间不用均匀，桶内元素均匀。
1、描述
- 类似，计数排序
2、分析（通的数量 k）
- 时间复杂度 O（n+k）
最坏情况，所有数集中在一个桶中，排序时间O（nlogn）
- 空间复杂度 O（n+k）
11、基数排序 Radix?Sort
比桶排序，更适合区间很大的情况
1、描述
- 先根据个位，划分10个桶，桶内排序
- 再根据十位.....
- ......
2、分析（类别个数 k——多位数排序，k=10；排序次数 d——多位数排序，d=位数）
- 每一次排序需要时间 O（n+k）
- 排序时间 O（d*（n+k））
- 空间复杂度 O（n+k）