老邱排序分册讲述.doc
文本预览下载声明
实验十 排序实验题
1. 分别用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序算法对相同的待排序列进行排序，输出排序结果；
2. 统计排序过程中“比较”操作的执行次数和记录“移动”的次数。
【存储结构】
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{ int key; //关键字项
InfoType otherinfo; //其他数据项
}DataType;
typedef struct
{ DataType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元
int length;
}SqList;
//分别用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序算法对相同的待排序列进行排序，输出排序结果
//直接插入排序
#include stdio.h
#include iostream.h
#include stdlib.h
#define MAXSIZE 20
typedef int KeyType;
typedef char InfoType ;
typedef struct
{
KeyType key;
InfoType otherType ;
}RedType ;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}SqList;
void InsertSort(SqList L)
{
int i,j;
for(i=2;i=L.length ;++i)
if(L.r [i].key L.r [i-1].key )
{
L.r [0]=L.r [i];
L.r [i]=L.r [i-1];
for(j=i-2;L.r [0].key L.r [j].key ;--j)
L.r [j+1]=L.r [j];
L.r [j+1]=L.r [0];
}
}
void Input(SqList L)
{
coutinput n:endl;
cinL.length ;
for(int i=1;iL.length+1 ;i++)
cinL.r [i].key ;
}
void PrintList(SqList L)
{
for(int i=0;iL.length ;i++)
coutL.r [i+1].key ;
coutendl;
}
void main()
{
SqList L;
L.length =0;
Input(L);
PrintList(L);
coutInsertSort:endl;
InsertSort(L);
PrintList(L);
}
/*
input n:
9
13
23
11
67
98
43
76
90
56
13 23 11 67 98 43 76 90 56
InsertSort:
11 13 23 43 56 67 76 90 98
Press any key to continue
*/
//分别用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序和简单选择排序算法对相同的待排序列进行排序，输出排序结果
//折半插入排序
#include stdio.h
#include iostream.h
#include stdlib.h
#define MAXSIZE 20
typedef int KeyType;
typedef char InfoType ;
typedef struct
{
KeyType key;
InfoType otherType ;
}RedType ;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}SqList;
void InsertSort(SqList L)
{
int i,j;
for(i=2;i=L.length ;++i)
if(L.r [i].key L.r [i-1].key )
{
L.r [0]=L.r [i];
L.r [i]=L.r [i-1];
for(j=i-2;L.r [0].key L.r [j].key ;--j)
L.r [j+1]=L.r [j];
L.r [j+1]=L.r [0];
}
}
void Input(SqList L)
{
coutinput n:endl;
cinL.length ;
for(int i=1;iL.length+1 ;i+
显示全部