实验7 ：至少三种排序算法的程序实现 （第十六周星期三7 、8 节） 一、 实验目的 1 ．掌握简单插入排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。 2 ．对各种查找、排序技术的时间、空间复杂性有进一步认识。 二 、实验要求 1 ．认真阅读和掌握和本实验相关的教材内容。 2 ．编写完整程序完成下面的实验内容并上机运行。 3 ．整理并上交实验报告。 三、实验内容 编写程序实现下述五种算法至少三种，并用以下无序序列加以验证： 49，38，65，97，76，13，27，49 1．简单插入排序 2．冒泡排序 3．快速排序 4．归并排序 5．堆排序 四、思考与提高 1 ．设有 1 0 0 0 个无序的元素，希望用最快的速度挑出其中前 1 0 个最大的元素，采用哪一种排序方法最好？为什么？ 2 ．如何构造一种排序方法，使五个整数至多用七次比较就可以完成排序任务？ /*---------------------------------------- * 07_排序.cpp -- 排序的相关操作 * 对排序的每个基本操作都用单独的函数来实现 * 水上飘 2009 年写 ----------------------------------------*/ // ds07.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include #include using namespace std; #define MAXSIZE 20 typedef int KeyType; typedef struct{ KeyType key; //关键字项 KeyType data; //数据项 }RedType; //记录类型 typedef struct{ RedType arr[MAXSIZE+1]; //arr[0]闲置或用作哨兵单元 int length; //顺序表长度 }SqList; //顺序表类型 typedef SqList HeapType; //折半插入排序 void bInsertSort(SqList &L) { for (int i = 2; i <= L.length; i++){ L.arr[0] = L.arr[i];//将其暂存到 arr[0] int low = 1; int high = i - 1; while(low <= high){//在 arr[low...high]中折半查找有序插入的位置 int m = (low + high) / 2;//折半 if(L.arr[0].key < L.arr[m].key) high = m - 1;//插入点在低半区 else low = m + 1;//插入点在高半区 }//while for(int j = i - 1; j >= high + 1; j--) L.arr[j + 1] = L.arr[j];//记录后移 L.arr[high + 1] = L.arr[0];//插入 }//for }//BInsertSort //直接插入排序 void insertSort(SqList &L) { for(int i = 2;...
