第 10 章 排序总结.ppt

文档介绍：排序:将数据元素的一个任意序列,重新排列成一个按关键
字有序的序列。
概述
稳定的排序方法不稳定的排序方法。
插入排序
直接插入排序
排序过程:先将序列中第 1 个记录看成是一个有序子序列,
然后从第 2 个记录开始逐个进行插入,直至整个序列有序。
T(n)=O(n²)
时间复杂度:
空间复杂度:S(n)=O(1)
直接插入排序是稳定排序
其他插入排序
1、折半插入排序:用折半查找方法确定插入位置的排序。
T(n)=O(n²)
时间复杂度:
空间复杂度:S(n)=O(1)
折半插入排序是稳定排序
希尔排序(缩小增量排序)
基本思想:对待排序列先作“宏观”调整,再作“微观”调整。
排序过程:先取一个正整数 d1 < n,把所有相隔 d1 的记录放
在一组内,组内进行直接插入排序;然后取 d2 < d1,重复上述分
组和排序操作;直至 di = 1,即所有记录放进一个组中排序为止。
其中 di 称为增量。
交换排序
1、冒泡排序
结束条件:“在一趟排序过程中仅第一、二个记录交换过”
或:“没有进行过交换记录的操作”。
时间复杂度:
T(n) = O(n2)
空间复杂度:S(n) = O(1)
稳定性:稳定排序
2、一趟快速排序(一次划分)
3、快速排序
时间复杂度:
T(n) = O(nlogn)
空间复杂度: S(n) = O(1)
稳定性:不稳定排序
选择排序
简单选择排序
时间复杂度:O(n2)
空间复杂度:O(1)
不稳定
堆排序
堆的定义:n 个元素的序列(k1, k2, …, kn),当且仅当满足下
列关系时,称之为堆。
或
(i = 1, 2, …, n/2)
ki  k2i