数据结构排序算.docVIP

福州大学数计学院 《数据结构》上机实验报告 学号 姓名 班级 实验名称 排序算法 实验内容 常用排序算法的实现 实 验 目 的 和 要 求 熟悉并掌握各种排序算法的思想方法和实现该算法的基本技术 问 题 描 述 和 主 要 步 骤 实验内容：从键盘输入一组关键字序列分别实现下列排序: 1.实现简单选择排序、直接插入排序和冒泡排序。 2.实现快速排序算法。3.实现折半插入排序。4. 采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。 实验要点及说明： 一趟快速排序的具体做法是设置两个指针low和high,设立支点记录的关键字pivotkey，首先从high所指位置向前有哪些信誉好的足球投注网站找到第一个关键字小于pivotkey的记录和支点记录互换，然后从low所指向的记录向后有哪些信誉好的足球投注网站，找到第一个关键字大于pivotkey的记录和支点记录互换，重复这两个步骤直到low=high。 实 验 结 果 （ 截 图 表 示 ） 简单选择排序 // algo10-7.cpp 简单选择排序 #includestdio.h typedef int InfoType; // 定义其它数据项的类型 #includec10-1.h int SelectMinKey(SqList L,int i) { // 返回在L.r[i..L.length]中key最小的记录的序号 KeyType min; int j,k; k=i; // 设第i个为最小 min=L.r[i].key; for(j=i+1;j=L.length;j++) if(L.r[j].keymin) // 找到更小的 { k=j; min=L.r[j].key; } return k; } void SelectSort(SqList L) { // 对顺序表L作简单选择排序。算法10.9 int i,j; RedType t; for(i=1;iL.length;++i) { // 选择第i小的记录，并交换到位 j=SelectMinKey(L,i); // 在L.r[i..L.length]中选择key最小的记录 if(i!=j) { // 与第i个记录交换 t=L.r[i]; L.r[i]=L.r[j]; L.r[j]=t; } } } void print(SqList L) { int i; for(i=1;i=L.length;i++) printf((%d,%d),L.r[i].key,L.r[i].otherinfo); printf(\n); } #define N 8 void main() { RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}}; SqList l; int i; for(i=0;iN;i++) l.r[i+1]=d[i]; l.length=N; printf(排序前:\n); print(l); SelectSort(l); printf(排序后:\n); print(l); } 直接插入排序和折半插入排序 #includec1.h typedef int InfoType; // 定义其它数据项的类型 #includec9.h #includec10-1.h #includebo10-1.cpp void print(SqList L) { int i; for(i=1;i=L.length;i++) printf((%d,%d),L.r[i].key,L.r[i].otherinfo); printf(\n); } #define N 8 void main() { RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}}; SqList l1,l2,l3; int i; for(i=0;iN;i++) // 给l1.r赋值 l1.r[i+1]=d[i]; l1.length=N; l2=l3=l1; // 复制顺序表l2、l3与l1相同 printf(排序前:\n); print(l1); Inser