数据结构实验七(排序算法的实现)题目和源程序.doc

实验7：至少三种排序算法的程序实现（第十六周星期三7、8节）一、 实验目的1掌握简单插入排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。2对各种查找、排序技术的时间、空间复杂性有进一步认识。二 、实验要求1认真阅读和掌握和本实验相关的教材内容。2编写完整程序完成下面的实验内容并上机运行。3整理并上交实验报告。三、实验内容编写程序实现下述五种算法至少三种，并用以下无序序列加以验证：49，38，65，97，76，13，27，491简单插入排序2冒泡排序3快速排序4归并排序5堆排序四、思考与提高 1设有1000个无序的元素，希望用最快的速度挑出其中前10个最大的元素，采用哪一种排序方法最好？为什么？ 2如何构造一种排序方法，使五个整数至多用七次比较就可以完成排序任务？/*- * 07_排序.cpp - 排序的相关操作 * 对排序的每个基本操作都用单独的函数来实现 * 水上飘 2009年写 -*/ ds07.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include #include using namespace std;#define MAXSIZE 20typedef int KeyType;typedef structKeyType key; /关键字项KeyType data; /数据项RedType; /记录类型typedef structRedType arrMAXSIZE+1; /arr0闲置或用作哨兵单元int length; /顺序表长度SqList; /顺序表类型typedef SqList HeapType;/折半插入排序void bInsertSort(SqList &L)for (int i = 2; i = L.length; i+)L.arr0 = L.arri;/将其暂存到arr0int low = 1;int high = i - 1;while(low = high)/在arrlow.high中折半查找有序插入的位置int m = (low + high) / 2;/折半if(L.arr0.key = high + 1; j-)L.arrj + 1 = L.arrj;/记录后移L.arrhigh + 1 = L.arr0;/插入/for/BInsertSort/直接插入排序void insertSort(SqList &L)for(int i = 2; i = L.length; i+)if(L.arri.key L.arri-1.key)/if,需将L.arri插入有序子表L.arr0 = L.arri;/复制为哨兵L.arri = L.arri-1;int j;for(j = i - 2; L.arr0.key L.arrj.key; j-)L.arrj+1 = L.arrj;/记录后移L.arrj+1 = L.arr0;/插入到正确位置/if/for/InsertSort/冒泡排序void bubbleSort(SqList &L)RedType* temp = NULL;for(int i = 1; i L.length; i+)/第i趟排序for(int j = 1; j L.arrj+1.key)/交换前后的位置L.arr0 = L.arrj;L.arrj = L.arrj+1;L.arrj+1 = L.arr0;/if/for j/for i/bubbleSort/*交换顺序表中子表L.arrlow.high的记录,枢轴记录到位,并返回其所在位置*/int partition(SqList &L, int low, int high)L.arr0 = L.arrlow;/子表的第一个记录做枢轴记录KeyType pivotKey = L.arrlow.key;/枢轴记录关键字while(low high)/从表的两端交替向中间扫描while(low = pivotKey)high-;/whileL.arrlow = L.arrhigh;/将比枢轴小的记录移到低端while(low high & L.arrlow.key = pivotKey)low+;/whileL.arrhigh = L.arrlow;/将比枢轴大的记录移到高端/whileL.arrlow = L.arr0;/枢轴记录到位return low;/返回枢轴位置/paitition/对顺序表L中的子序列L.arrlow.high做快速排序void qSort(SqList &L, int low, int high)if(low high)/长度大于1KeyType pivotLoc = partition(L, low, high);/将L.arrlow.high一分为二qSort(L, low, pivotLoc-1);/对低子表递归排序，pivotLoc是枢轴位置qSort(L, pivotLoc+1, high);/对高子表递归排序/if/qSort/对顺序表L做快速排序void quickSort(SqList &L)qSort(L, 1, L.length);/quickSort/*调整H.arrs的关键字，使H.arrs.m成为一个大顶堆（对其中记录的关键字而言）*/void heapAdjust(HeapType &H, int s, int m)RedType rc = H.arrs;for(int j = 2 * s; j = m; j = j * 2)/沿key较大的孩子结点向下筛选if(j m & H.arrj.key H.arrj+1.key)j+;/j为key叫大记录的下标/ifif(!(rc.key 0; i-)/把H.arr1.H.length建成大顶堆heapAdjust(H, i, H.length);/forfor(int i = H.length; i 1; i-)/将堆记录当前未经排序的子序列H.arr1.i中的最后一个记录交换H.arr0 = H.arr1;H.arr1 = H.arri;H.arri = H.arr0;heapAdjust(H, 1, i-1);/将H.arr1.i-1重新调整为大顶堆/for/heapSort/初始化顺序表，给其赋值void setValue(SqList &L)KeyType data8 = 49,38,65,97,76,13,27,49;int n = 8;L.arr0.data = 0;L.length = n;for(int i = 1; i = L.length; i+)L.arri.data = datai-1;L.arri.key = L.arri.data;/for/setValue/输出顺序表void show(SqList &L)for(int i = 1; i = L.length; i+)if(i % 5 = 0)cout endl;cout setw(5) L.arri.data;cout endl;/show/调用排序函数进行排序void performance(SqList &L)cout 原始序列： endl;show(L);SqList LI = L;insertSort(LI);cout 直接插入排序结果： endl;show(LI);SqList LB = L;bInsertSort(LB);cout 折半插入排序结果： endl;show(LB);SqList LBB = L;bubbleSort(LBB);cout 冒泡排序结果： endl;show(LBB);SqList LQ = L;cout 快速排序结果： endl;quickSo