单元实验二 排序算法,排序的分类,内部排序,外部排序,插入排序（直插排序、二分插入排序、希尔排序）,交换排序（冒泡排序、快速排序）,选择排序（简单选择排序、树型排序、堆排序）,归并排序（二路归并排序、多路归并排序）,分配排序（多关键字排序、基数排序）,多路平衡归并排序,置换选择排序,最佳归并树,排序,基本要求,1用随机函数产生1000个（或更多）整数（或浮点数），保存在文件（intfile.dat / realfile.dat）中，然后将文件中的所有整数（或浮点数）读入一个数组A。 （1）用冒泡法对数组A排序； （2）用简单选择排序方法对数组A排序； （3）用直接插入排序法对数组A排序； 将上述排序算法分别用函数实现，输出每种排序过程中元素的比较次数、交换（或移动）次数，以及排序过程所消耗的时间（以s或ms为单位）；,数据结构定义,#define MAXSIZE 100 typedef int Keytype; / 定义关键字类型为整型 typedef char InfoType100; typedef struct KeyType key; / 关键字项 InfoType otherinfo; / 其他数据项 RedType; / 记录类型 typedef struct RedType rMAXSIZE+1; / r0闲置或用作哨兵 int length; / 顺序表长度 SqList; / 顺序表类型,直接插入排序,直接插入排序(Straight Insertion Sorting)的基本思想是：n个待排序的元素由一个有序表和一个无序表组成，开始时有序表中只包含一个元素。排序过程中，每次从无序表中取出第一个元素，将其插入到有序表中的适当位置，使有序表的长度不断加长，完成排序过程。,有序序列R1.i-1,Ri,无序序列 Ri.n,有序序列R1.i,无序序列 Ri+1.n,直接插入排序算法,void InsertSort(SqList / InsertSort,计算直接插入排序算法中关键字的比较(蓝色)次数和移动（红色）次数,for(i = 2; i = L.length; i+) if (L.ri.key L.ri-1.key) L.r0 = L.ri; L.ri = L.i-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if,if (L.ri.key L.ri-1.key) L.r0 = L.ri; /L.r0为监视哨 L.ri = L.ri-1; for(j = i - 2; L.r0.key L.rj.key; j-) L.rj+1 = L.rj; L.rj+1 = L.r0; /if,冒泡排序,冒泡排序(Bubble Sorting)的基本思想是：将相邻位置的关键字进行比较，若为逆序则交换之。,无序序列R1.n-i+1,有序序列 Rn-i+2.n,n-i+1,无序序列R1.n-i,有序序列 Rn-i+1.n,比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上,第 i 趟起泡排序,若在一趟排序过程中没有进行过交换记录的操作，则整个排序过程终止。,冒泡排序算法,以顺序表作为存储结构的冒泡排序算法,void BubbleSort(SqList /if / BubbleSort,计算冒泡排序算法中关键字的比较次数和记录移动次数,for(i = 1, exchanged = TRUE; i L.length /for /if,exchanged =FALSE; for(j = 1; j L.rj+1.key ) L.r0 = L.rj; L.rj = L.rj+1; L.rj+1 = L.r0; exchanged =TRUE; /if,简单选择排序,简单选择排序的基本思想是：第一趟在n个记录中选取最小记录作为有序序列的第一个记录，第二趟在n-1个记录中选取最小记录作为有序序列的第二个记录，第i趟在n-i+1个记录中选取最小的记录作为有序序列多中的第i个记录。,有序序列R1.i-1,无序序列 Ri.n,第 i 趟 简单选择排序,从中选出关键字最小的记录,有序序列R1.i,无序序列 Ri+1.n,简单选择排序算法,以顺序表作为存储结构的简单选择排序算法,void SelectSort(SqList /for / SelectSort,计算简单选择排序算法中关键字的比较次数和记录移动次数,for(i = 1; i L.length; i+) for(k = i, j =i; k = L.length; k+) if (L.rk.key L.rj.key) j = k; if (j != i) L.ri L.rj; /for /if,for(k = i+1, j = i; k = L.length; k+) if (L.rk.key L.rj.key) j = k; if (j != i) L.ri L.rj; /*1次交换，3次移动*/,基本要求,1用随机函数产生1000个（或更多）整数（或浮点数），保存在文件（intfile.dat / realfile.dat）中，然后将文件中的所有整数（或浮点数）读入一个数组A。 （1）用冒泡法对数组A排序； （2）用简单选择排序方法对数组A排序； （3）用直接插入排序法对数组A排序； 将上述排序算法分别用函数实现，输出每种排序过程中元素的比较次数、交换（或移动）次数，以及排序过程所消耗的时间（以s或ms为单位）；,基本要求,2将问题1中所有1000个（或更多）整数读入数组A，用快速排序算法对数组A中的元素排序，输出排序结果、排序过程中元素的比较和交换（移动）次数、排序算法消耗的时间; 3. 利用上面实现的任意一种排序算法，对实验题目一所产生的学生信息文件studinfo.dat，读取其中的所有学生信息： （1）按学号排序输出学生信息； （2）按姓名排序输出学生信息； （3）按三门课程的平均分从高到低排序输出学生信息（除了学生基本信息外，还要输出每个学生的平均成绩），最后再加一行输出信息：每门课程的平均成绩。,快速排序,快速排序(Quick Sorting)是迄今为止所有内排序算法中速度最快的一种。其基本思想是：取待排序序列中的某个元素作为基准（也成为枢轴元素，一般取第一个元素），通过一趟排序，将待排序列划分为左右两个子序列，左子序列元素的关键字均小于或等于基准元素的关键字，右子序列的关键字则大于或等于基准元素的关键字，然后分别对两个子序列继续进行排序，直至整个序列有序。,无 序 的 记 录 序 列,无序的左子序列,无序的右子序列,枢轴,一次划分,分别进行快速排序,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,49,04,9,i,j,快速排序中的一趟划分,aj与pivot比较，aj小则ajai,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,快速排序中的一趟划分,ai与pivot比较， ai大则ai aj；否则i增1,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,快速排序中的一趟划分,ai与pivot比较， ai大则ai aj；否则i增1,快速排序中的一趟划分,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,aj与pivot比较， aj小则aj ai；否则j减1,快速排序中的一趟划分,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,ai与pivot比较， ai大则ai aj；否则i加1,快速排序中的一趟划分,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,aj与pivot比较， aj小则ai aj；否则j减1,快速排序中的一趟划分,38,65,97,13,27,49,55,1,2,3,4,5,6,7,8,04,9,49,pivot,i与j相等时，完成一次划分， 枢轴元素归位,快速排序中的一趟划分,38,27,13,49,97,49,55,1,2,3,4,5,6,7,8,04,65,9,int Partition(SqList / 返回枢轴元素最后确定的位置 /Partition,38,65,97,13,27,49,55,49,04,8,40,30,20,15,9,25,1,2,3,4,5,6,7,8,10,5,9,i,j,快速排序中的一趟划分,10,10,快速排序,int Partition(SqList /返回枢轴元素的位置 /Partition,void QSort(SqList / 右子序列进行快速排序 /if /QSort,快速排序过程分析,选作内容,用随机函数产生至少10000个整数，保存在文件（intfile.dat）中 （1）通过建立大顶（根）堆实现堆排序，最后输出排序结果； （2）通过建立小顶（根）堆实现堆排序，每找出一个小元素就输出它，从小到大输出排序结果。,选作内容,用随机函数产生至少10000个整数，保存在文件（intfile.dat）中，对其中的数据进行归并排序，最后将排序结果写入文件； 产生两个已经排序的整数数据文件，将两个文件的数据归并成一个有序序列存入文件保存。,堆排序,堆的定义 对于n个元素的序列k1,k2,.,kn，当且仅当满足以下关系时，称之为堆。,或,12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49,是小顶堆,12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49,不是堆,堆排序,堆(完全二叉树),96,83,38,11,27,9,(a) 大顶堆(max heap),12,36,85,47,24,30,(b) 小顶堆(min heap),53,91,96,83,27,38,11,9,12,36,24,85,47,30,53,91,堆排序,对一组待排序记录的关键字，首先把它们按堆的定义建成小(大)顶堆，然后输出堆顶的最小(大)关键字所代表的记录，再对剩余的关键字建堆，以便得到次小(大)的关键字，如此反复进行，直到全部关键字排成有序序列为止。,实现堆排序需要解决两个问题： (1) 如何建堆？ (2) 输出堆顶元素后，如何将剩余元素重新调整为一个新堆？,堆排序过程示例,下面是一个小顶堆，输出堆顶元素后（即将序列末端元素与堆顶元素交换），将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则将其孩子中的较小者与之交换，即将非堆的子树推向叶子方向,12,36,85,47,24,30,53,91,交换堆顶元素与序列末端的元素,比较,比较-,交换,return,堆排序过程示例(续),输出堆顶元素后，将剩余元素重新调整为一个新堆的方法是：从树根开始，若以某结点为根的子树不是堆，则将其孩子中的较小者与之交换，即将非堆的子树推向叶子方向,继续向叶子方向调整,比较,比较,交换,堆排序过程示例(续),一旦已调整为堆，则输出堆顶元素，重复将剩余元素重新调整为一个