数据结构与算法基础--第14周01--第8章排序1--8.1排序概述
>排序:什么是排序?
- 将一组杂乱无章的数据按照一定规律顺次排列起来,即:
- 将无序序列排成一个有序序列(由小到大/由大到小)的运算。
>>排序方法的分类:
1、按数据存储介质:内部排序和外部排序
2、按比较器个数:串行排序和并行排序
3、按主要操作:比较排序和基数排序
4、按辅助空间:原地排序和非原地排序
5、按稳定性:稳定排序和非稳定排序
6、按自然性:自然排序和非自然排序
>>按照排序依据的原则:
- 插入排序:直接插入排序、折半插入排序、希尔排序
- 交换排序:冒泡排序、快速排序
- 选择排序:简单选择排序、堆排序
- 归并排序:2-路归并排序
- 基数排序
>>按照排序所需工作量:
- 简单排序方法:T(n)=O(n²)
- 基数排序:T(n)=O(d.n)
-
先进的排序方法:T(n)=O(nlogn)