排序算法 排序(Sorting):将一串数据依照指定方式进行排列。 常用排序方式：数值顺序，字典顺序。 算法评价重要指标 时间复杂度（最差、平均) 设有n个数据，一般来说，好的排序算法性能是O(n log n),差的性能是 O(n2),而理想的性能是On)。 空问复杂度 算法在运行过程中临时占用存储空间的大小。 稳定排序算法：相同的数据，排序后仍维持原有相对次序。 http://math.ecnu.edu.cn/~jypan 2
http://math.ecnu.edu.cn/~jypan 2 排序算法 排序 (Sorting)：将一串数据依照指定方式进行排列。 常用排序方式：数值顺序，字典顺序。 时间复杂度（最差、平均） 设有 n 个数据，一般来说，好的排序算法性能是 O(n log n)，差的性能是 O(n2)，而理想的性能是 O(n)。 空间复杂度 算法在运行过程中临时占用存储空间的大小。 算法评价重要指标 稳定排序算法：相同的数据，排序后仍维持原有相对次序
常见排序算法 算法 平均时间复杂度 算法 平均时间复杂度 选择排序 0n2) 归并排序 O(n log n) 插入排序 O(n2) 堆排序 O(n log n) 希尔排序 O(n log2 n) 图书馆排序 O(n log n) 冒泡排序 0n2) 基数排序 O(n·) 快速排序 O(n log n) 桶排序 O(n+k) 计数排序 O(n+k) 鸽巢排序 O(n+D) http://math.ecnu.edu.cn/~jypan 3
http://math.ecnu.edu.cn/~jypan 3 常见排序算法 算法 平均时间复杂度 算法 平均时间复杂度 选择排序 O(n2) 归并排序 O(n log n) 插入排序 O(n2) 堆排序 O(n log n) 希尔排序 O(n log2 n) 图书馆排序 O(n log n) 冒泡排序 O(n2) 基数排序 O(n · k) 快速排序 O(n log n) 桶排序 O(n + k) 计数排序 O(n + k) 鸽巢排序 O(n + D) … … … …
华东师范大学数学科学学院 目录页 School of Mathematical Sciences,ECNU Contents 1 选择排序 4 冒泡排序 2 插入排序 5 快速排序 希尔排序 本讲假定是对数据进行从小到大排序 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 目录页 Contents 1 2 选择排序 插入排序 华东师范大学 数学科学学院 School of Mathematical Sciences, ECNU 3 希尔排序 本讲假定是对数据进行从小到大排序 4 5 冒泡排序 快速排序
1 选择排序 也称最小排序 基本思想 ·先找出最小值，将其与第一个位置的元素进行交换 ·对剩余的数据重复以上过程，直至排序结束 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 1 选择排序 —— 也称 最小排序 基本思想 ► 先找出最小值，将其与第一个位置的元素进行交换 ► 对剩余的数据重复以上过程，直至排序结束
选择排序：示例 原始序列：283 12 5 20 7 145 16 第1轮排序：28 3 12 5 20 14 5 16 第2轮排序：2 3812 20 7 14 5 16 第3轮排序：235 12 8 20 14 5 16 第4轮排序：235 5 14 12 16 第5轮排序：23 5 5 7 20 14 12 16 第6轮排序：2355 7 8 20 14 12 16 第7轮排序：23557 8 12 14 20 16 第8轮排序：2355 7 8 12 14 20 16 第9轮排序：235 578121416 20 MATLAB演示：sort_min.m http://math.ecnu.edu.cn/~jypan 6
http://math.ecnu.edu.cn/~jypan 6 选择排序：示例 原始序列： 2 8 3 12 5 20 7 14 5 16 第1轮排序：2 8 3 12 5 20 7 14 5 16 第2轮排序：2 3 8 12 5 20 7 14 5 16 第3轮排序：2 3 5 12 8 20 7 14 5 16 第4轮排序：2 3 5 5 8 20 7 14 12 16 第5轮排序：2 3 5 5 7 20 8 14 12 16 第6轮排序：2 3 5 5 7 8 20 14 12 16 第7轮排序：2 3 5 5 7 8 12 14 20 16 第8轮排序：2 3 5 5 7 8 12 14 20 16 第9轮排序：2 3 5 5 7 8 12 14 16 20 MATLAB 演示：sort_min.m