第九章内部排序-数据结敏构DATASTRUCTURE.ppt

计算机科学与工程系 计算机科学与工程系 第十章 排序 概述 插入排序 交换排序 选择排序 归并排序 基数排序 10.1 概述 1) 基本概念 排序：将一组记录按相应关键字的值递增或递减次序重新排列的过程。 关键字(key): 通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键字。 排序算法的稳定性: 如果在对象序列中有两个对象r[i]和r[j]，它们的关键字 k[i] == k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。 2）排序方法的分类 根据排序时使用的存储器不同，分为： 内部排序: 在内存实现，数据对象全部存放在内存，无内外存数据交换；适合少量数据，速度快。 外部排序: 排序期间全部对象太多，不能同时存放在内存，必须根据排序过程的要求，不断在内外存之间移动；适合大量数据，速度慢。 按实现策略，内排序分五大类： 插入排序: 直接插入、shell排序 交换排序：冒泡、快速排序 选择排序：简单选择、树型选择、堆排序 归并排序： 基数排序： 按排序所需工作量，内排序分为： 简单排序方法: O(n2) 简单排序 先进排序方法: O(nlogn) 堆排序、快速排序… 基数排序方法: O(dn) 基数排序 3）排序算法的评价标准 时间复杂度: 排序的时间开销用算法执行中的数据比较次数与数据移动次数来衡量。 空间复杂度: 算法执行时所需的附加空间。 稳定性: 简单性: 10.2 插入排序 (Insert Sorting) 1) 基本思想：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。 将顺序存储的 n 个待排序记录划分为两个区间：一个有序区，一个无序区; 初始时：有序区为[R1]，无序区为[R2….Rn]，令 i 指向无序区中第一个记录，初值 i =2。 当i≤n时，重复执行： 将当前无序区中第一个记录 Ri 插入到有序区的适当位置，使有序区变为：[R1’….Ri’]，无序区变为[Ri+1….Rn]。 当i〉n时，有序区变为[R1’….Rn’]，排序结束。 2）逐步求精：将 Ri 插入到有序区[R1….Ri-1]中适当位置，即保持仍然有序。 具体做法：当插入第 i 个对象时，前面的 R1, R2….Ri-1已经排好序。这时，用 R[i] 的关键字与R[i-1], R[i-2], …的关键字顺序进行比较，若比 R[i] 的关键字大，就后移一个位置，如此重复，直到找到适当的插入位置，即将R[i]插入。 4) 算法分析 时间复杂度：设待排序对象个数为 n，则共需n-1 趟插入排序。每趟排序过程中关键字比较次数和对象移动次数与对象的初始排列有关。 最好情况(正序): 最坏情况(逆序): 空间复杂度：使用了一个临时空间 O(1) 稳定性：直接插入排序是一种稳定的排序方法。 10.2.2 希尔排序 (缩小增量法） 1）基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。排序过程： 先将整个待排序记录以d1为步长分成若干子序列，把所有相隔为d1的记录放在同一组内； 在每个分组内进行直接插入排序； 在将整个待排序记录序列以d2(d2d1n)为步长重新分组和在每组内进行直接插入排序； 重复上步，直至dt=1，即所有记录放进一个组中进行直接插入排序。 4) 算法分析 10.3 交换排序 ( Exchange Sort ) 10.3.1 起泡排序 (Bubble Sort) 1）起泡排序的基本方法： 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止 2）算法实现 void bubble_Sort (int a[], int n ) //起泡排序算法 { for ( int i = n-1, change =1; i=1 change; i--) { change =0; for (j=0;ji; j++) if ( a[j] a[j+1] ) { Swap ( j +1, j