[外语学习]第十一章排序.pptVIP

1 、交换式排序 2、选择式排序 3、插入式排序 4、归并排序 5、各种内排方法比较 排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。 数据表: 它是待排序数据对象的有限集合。 主关键字: 数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分对象, 作为排序依据，称为关键字。也称为排序码。 排序方法的稳定性: 如果在对象序列中有两 个对象r[i]和r[j], 它们的关键字k[i] == k[j] , 且在排序之前, 对象r[i]排在r[j]前面。如果在排序之后, 对象r[i]仍在对象r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 如记录对应关键字序列为：8，7，24，8’，19 使用某排序算法得到的序列：7，8，8’，19，24 则这种排序方法是稳定的 使用某排序算法得到的序列：7，8’，8，19，24 则这种排序方法是不稳定的 内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象数量太大，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。 排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。 内排序分类 依不同原则 交换式排序、选择式排序、插入式排序、归并排序、基数排序。 依所须工作量 简单排序---时间复杂度O(n2) 先进排序方法---时间复杂度O(n logn) 基数排序---时间复杂度O(d*n) 11.2 交换式排序 一、起泡排序 (Bubble Sort) 基本方法： 先将第一个记录的关键字和第二个记录的关键字进行比较，如果前者比后者大，则将两个记录交换。然后比较第二个和第三个记录的关键字，依次类推直到第n-1个记录和第n个记录进行比较交换完，这称为第一趟冒泡。经过一趟冒泡后，关键字最大的记录就被交换到了第n个位置。然后，对前n-1个记录进行同样的操作，则关键字是第二大的记录就被交换到了第n-1个位置上。重复以上过程，每趟负责排好一个记录，经过n-1趟后n个记录中有n-1个记录被排好，剩下的一个记录不必再排了，至此n个记录全部排好。 最坏的情形是算法执行n-1趟起泡,第i趟 (1? i? n) 做 n- i 次关键字比较, 执行 n-i 次对象交换。这样在最坏情形下总的关键字比较次数KCN和交换次数RMN为： 二、快速排序 (Quick Sort) 基本思想:是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准, 按照该对象的关键字大小,将整个对象序列划分为左右两个子序列： 左侧子序列中所有对象的关键字都小于基准对象的关键字 右侧子序列中所有对象的关键字都大于基准对象的关键字 基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。 基准对象也称为枢轴（或支点）记录。 一趟快速排序的具体做法是： 设两个指针low和high，设枢轴记录的关键字为key。 首先从high所指位置起向前有哪些信誉好的足球投注网站找到第一个关键字小于key的记录，使high和key的值交换。 再移动到low所在位置，然后从low所指位置起向后有哪些信誉好的足球投注网站，找到第一个关键字大于key的记录移动到high所指位置，使low和key的值交换。 重复这两步直至low=high为止。 算法实现过程中，先将基准记录保存在r[0]位置上，排序过程中只作r[low]或r[high]记录的移动，待一趟排序结束后再将基准记录移至正确位置上。 void quick_sort(int num[ ],int s,int t) {int i,j; i=s;j=t; num[0]=num[s]; while(ij) {while(jinum[0]num[j]) j--; if(ij) {num[i]=num[j]; i++;} while(ijnum[i]=num[0]) i++; if(ij) {num[j]=num[i]; j--;} } num[i]=num[0]; if(si) quick_sort(num,s,j-1); if(it) quick_sort(num,j+1,t); } 可以证明, 函数quick_sort的平均时间复杂度是O(nlog2n)。实验结果表明: 就平均计算时间而言, 快速排序是所有内排序方法中最好的一个。 快速排序是递归的。 快速排序是一种不稳定的排序方法。 最佳状况时间复杂度是O(nlog2n)