第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
数据结构实验七（排序算法的实现）题目和源程序.doc
实验 7：至少三种排序算法的程序实现
（第十六周星期三 7、8 节）
一、 实验目的
1．掌握简单插入排序、冒泡排序、快速排序、堆排序以及归并排序的
算法并加以应用。
2．对各种查找、排序技术的时间、空间复杂性有进一步认识。
二 、实验要求
1．认真阅读和掌握和本实验相关的教材内容。
2．编写完整程序完成下面的实验内容并上机运行。
3．整理并上交实验报告。
三、实验内容
编写程序实现下述五种算法至少三种，并用以下无序序列加以验证：
49，38，65，97，76，13，27，49
1．简单插入排序
2．冒泡排序
3．快速排序
4．归并排序
5．堆排序
四、思考与提高
1．设有 1000 个无序的元素，希望用最快的速度挑出其中前 10 个最大的
元素，采用哪一种排序方法最好？为什么？
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];
int length;
//顺序表长度
//arr[0]闲置或用作哨兵单元
}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; i <= L.length; i++){
if(L.arr[i].key < L.arr[i-1].key){//if"<",需将 L.arr[i]插入有序子表
L.arr[0] = L.arr[i];//复制为哨兵
L.arr[i] = L.arr[i-1];
int j;
for(j = i - 2; L.arr[0].key < L.arr[j].key; j--)
L.arr[j+1] = L.arr[j];//记录后移
L.arr[j+1] = L.arr[0];//插入到正确位置
}//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.length-i; j++){//第 j 次排序
if(L.arr[j].key > L.arr[j+1].key){
//交换前后的位置
L.arr[0] = L.arr[j];
L.arr[j] = L.arr[j+1];
L.arr[j+1] = L.arr[0];
}//if
}//for j
}//for i
}//bubbleSort
/*交换顺序表中子表 L.arr[low...high]的记录,
枢轴记录到位,并返回其所在位置*/
int partition(SqList &L, int low, int high)
{
L.arr[0] = L.arr[low];//子表的第一个记录做枢轴记录
KeyType pivotKey = L.arr[low].key;//枢轴记录关键字
while(low < high){//从表的两端交替向中间扫描
while(low < high && L.arr[high].key >= pivotKey){
high--;
}//while
L.arr[low] = L.arr[high];//将比枢轴小的记录移到低端
while(low < high && L.arr[low].key <= pivotKey){
low++;
}//while
L.arr[high] = L.arr[low];//将比枢轴大的记录移到高端
}//while
L.arr[low] = L.arr[0];//枢轴记录到位
return low;//返回枢轴位置
}//paitition
//对顺序表 L 中的子序列 L.arr[low...high]做快速排序
void qSort(SqList &L, int low, int high)
{
if(low < high){//长度大于 1
KeyType pivotLoc = partition(L, low, high);//将 L.arr[low...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.arr[s]的关键字，使 H.arr[s...m]成为一个大顶堆
（对其中记录的关键字而言）*/
void heapAdjust(HeapType &H, int s, int m)
{
RedType rc = H.arr[s];
for(int j = 2 * s; j <= m; j = j * 2){//沿 key 较大的孩子结点向下筛选
if(j < m && H.arr[j].key < H.arr[j+1].key){
j++;//j 为 key 叫大记录的下标
}//if
if(!(rc.key < H.arr[j].key)){
break;//rc 应插入在位置 s 上
}//if
H.arr[s] = H.arr[j];
s = j;
}//for
H.arr[s] = rc;//插入
}//heapAdjust
//对顺序表 H 进行堆排序
void heapSort(HeapType &H)
{
for(int i = H.length/2; i > 0; i--){//把 H.arr[1...H.length]建成大顶堆
heapAdjust(H, i, H.length);
}//for
for(int i = H.length; i > 1; i--){
//将堆记录当前未经排序的子序列 H.arr[1...i]中的最后一个记录交换
H.arr[0] = H.arr[1];
H.arr[1] = H.arr[i];
H.arr[i] = H.arr[0];
heapAdjust(H, 1, i-1);//将 H.arr[1...i-1]重新调整为大顶堆
}//for
}//heapSort
//初始化顺序表，给其赋值
void setValue(SqList &L)
{
KeyType data[8] = {49,38,65,97,76,13,27,49};
int n = 8;
L.arr[0].data = 0;
L.length = n;
for(int i = 1; i <= L.length; i++){
L.arr[i].data = data[i-1];
L.arr[i].key = L.arr[i].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.arr[i].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;
quickSort(LQ);
show(LQ);
HeapType H = L;
cout << "堆排序结果：" << endl;
heapSort(H);
show(H);
}//performance
int _tmain(int argc, _TCHAR* argv[])
{
SqList L;
setValue(L);
performance(L);
cin.get();
return 0;
}
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
