内部算法性能分析 第3章 总体设计
3.2.2“排序性能分析”菜单设计原理
“排序性能分析”菜单的算法是调用“内部操作过程”菜单的算法，根据这一原理而成的，就不一一的介绍了，请读者自已去理解“内部操作过程”的设计过程。
3.2.3设计内容
内部排序系统具体实现的功能包括：快速排序，冒泡排序，希尔排序，简单选择排序，堆排序，直接排序等这六大排序的集成六个主要的函数如下：
快速排序函数：partition();
希尔排序函数：Shellsort(); 简单选择排序函数：selectsort(); 堆排序函数：heap(); 直接排序函数：insertsort(); 起泡排序函数：Bubblesort();
排序数据类型定义：
ADT paixu{
数据对象：D={aij|aij属于{1，2，3…},i,j>0} 数据关系：R={|ai-1,ai∈D，i=2,...,n} 基本操作：
Insertsort();
初始条件：数组已经存在。
操作过程：将一个记录插入到已经排好序的有序列表中，从而得到了一个新的、记录新增1的有序表。
Bubblesort();
初始条件：数组已经存在。
操作过程：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，知道全部满足顺序要求为止。
Shellsort();
初始条件：数组已经存在。
操作过程：先取定一个正整数d1 7 内部算法性能分析 第3章 总体设计 组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。 Selectsort(); 初始条件：数组已经存在。 操作过程：每次从待排序的记录中选出键值最小（或最大）的记录，顺序放在已经排序的记录序列的最好，直到全部排完。 heapsort (); 初始条件：数组已经存在。 操作过程：对一组待排序的的键值，首先是把它们按堆的定义排列成一个序列，这就找到了最小键值，然后把最小的键值取出，用剩下的键值再重建堆，便得到次小键值，如此反复进行，知道把全部键值排好序为止。 partition()； 初始条件：数组已经存在。 操作过程：在待排序的n个记录中任取一个记录，以该记录的键值为基准用交换的方法将所有记录分成两部分，所有键值比它小的放在一边，大的放另一边，并把该记录放在中间，然后重复至完成。 } ADT 排序 8 内部算法性能分析 第4章 详细设计 第4章 详细设计 4.1冒泡排序 冒泡排序（BubbleSort）是我们大家都熟知的排序，其基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为1,2,...10-i。 算法：for(i=1;i<=L-6;i++)/*外循环：控制比较趟数*/ { for(j=L;j>=i+1;j--)/*内循环：进行每趟比较*/ { times++;/*比较次数*/ if(R[j] } changes+=3;/*移动次数*/ 冒泡排序的最好 、最坏 、平均情况下的时间复杂度都为 O (n2 ) ,故算法的平均时间复杂度也为 O (n2 ) 。但是若在某趟排序中未发现气泡位置的交换 ,则 9 内部算法性能分析 第4章 详细设计 说明待排序的无序区中所有气泡均满足轻者在上、重者在下的原则 ,即为正序 ,则冒泡排序过程可在此趟扫描后就终止 ;在每趟排序过程中 ,无序区 R [ i. . n]的范围可能会有较大改变 ,而不是递减 ;对某些不对称性情况 ,在排序过程中 ,可改变其扫描方向。 4.2直接插入排序 直接插入排序(Straight Insertion Sort)是一种最简单的排序方法，它基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。 第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。 值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。 算法：for(i=2;i<=L;i++) { if(R[i] { R[0]=R[i];j=i-1;//复制哨兵 while(R[0] { times++; changes++; R[j+1]=R[j];j--;//记录后移 10 内部算法性能分析 第4章 详细设计 } R[j+1]=R[0];//插入到正确位置 changes++; ｝ 按以上算法进行直接插入排序的过程如图4.1所示： 初始序列：i=1 [46] 58 15 45 90 18 10 62 i=2 [46 58] 15 45 90 18 10 62 i=3 [15 46 58] 45 90 18 10 62 i=4 [15 45 46 58] 90 18 10 62 i=5 [15 45 46 58 90] 18 10 62 i=6 [15 18 45 46 58 90] 10 62 i=7 [10 15 18 45 46 58 90] 62 i=8 [10 15 18 45 46 58 62 90] 图4.1直接插入排序过程 从算法的实现过程可见，在最坏情况下，线性插入排序每插入一个元素需要进行i-1次比较，需要插入元素为N-1个，所以最大比较次数为：N(N-1)/2,该算法的时间复杂性为O(N*N) 空间复杂度为O(1)，因此，直接插入排序属于稳定的排序 4.3希尔排序 希尔排序(Shell Sort)又称“缩小增量排序”(Diminishing Increment Sort)，它也是一种属于插入排序类的方法，但在时间效率上跟其他的几种排序方法有了较大的改进。 希尔排序基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 先看一下希尔排序的过程。初始关键字序列如下面所示。首先将该序列分成5个子序列{R1,,R6},{R2,R7}??{R5,R10},如下面所示，分别对每个子序列进行直接插入排序，排序完后，然后进行第二趟希尔排序，即分别对下列3个子序列： 11