通信数据结构课件陈雄峰a第十章排序.pptVIP

重点：冒泡排序方法、快速排序方法、堆排序方法、基数排序方法； 难点：快速排序方法、堆排序方法、基数排序方法、桶排序方法。 知识点： 概述 插入排序 快速排序 选择排序 归并排序 基数排序 各种内排方法比较 概 述 排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。 排序方法的稳定性: 如果在对象序列中有两 个对象r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 对象r[i]排在r[j]前面。如果在排序之后, 对象r[i]仍在对象r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。 排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。 内排序分类 依不同原则 插入排序、交换排序、选择排序、归并排序、和计数排序等。 依所须工作量 简单排序---时间复杂度o(n2) 先进排序方法---时间复杂度o(n logn) 基数排序---时间复杂度o(d.n) 插入排序 (Insert Sorting) 基本思想 当插入第i (i ? 1) 个对象时, 前面的V[0], V[1], …, V[i-1]已经排好序。这时, 用V[i]的排序码与V[i-1], V[i-2], …的排序码顺序进行比较, 找到插入位置即将V[i]插入, 原来位置上的对象向后顺移。 算法分析 直接插入排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。 希尔排序 (Shell Sort) 基本思想设待排序对象序列有 n 个对象, 首先取一个整数 gap n 作为间隔, 将全部对象分为 gap 个子序列, 所有距离为 gap 的对象放在同一个子序列中, 在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = ?gap/2?，重复上述的子序列划分和排序工作。直到最后取 gap == 1, 将所有对象放在同一个序列中排序为止。 希尔排序方法又称为缩小增量排序。 交换排序 ( Exchange Sort ) 基本方法设待排序对象序列中的对象个数为n。一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录地关键字，如果发生逆序，则交换之，其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。 算法分析 起泡排序的时间复杂度为 o(n2)。 起泡排序是一种稳定的排序方法。 快速排序 (Quick Sort) 基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准, 按照该对象的排序码大小,将整个对象序列划分为左右两个子序列： 左侧子序列中所有对象的排序码都小于或等于基准对象的排序码 右侧子序列中所有对象的排序码都大于基准对象的排序码 基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。 基准对象也称为枢轴（或支点）记录。 选择排序 堆排序( Heap sort ) 基于初始堆(大顶堆)进行堆排序 最大堆堆顶V[0]具有最大的排序码, 将V[0]与 V[n-1]对调, 把具有最大排序码的对象交换到最后, 再对前面的n-1个对象, 使用堆的调整算法FilterDown(0, n-2), 重新建立最大堆, 具有次最大排序码的对象又上浮到V[0]位置。 再对调V[0]和V[n-2],调用FilterDown(0, n-3), 对前n-2个对象重新调整，…。 如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法， 归并排序 (Merge Sort) 归并将两个或两个以上的有序表合并成一个新的有序表。 两路归并 (2-way merging)原始序列initList[ ]中两个有序表 initList[l] … initList[m]和initList[m+1] … initList[n]，它们可归并成一个有序表, 存于另一对象序列mergedList的 l … n 中。 设变量 i 和 j 是表initList[l … m]和initList [m+1… n]的当前检测指针。k 是存放指针。 当 i 和 j 都在两个表的表长内变化时, 根据对应项的排序码的大小, 依次把排序码小的对象排放到新表 k 所指位置中； 当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。 基数排序 最低