数据结构课程设计-排序算法演示系统(3)

if(i

R[i].key=R[0].key; num++;

//输出语句包括排序的结果及次数

printf(\第%d趟快速排序的结果为：\\n\\t\\t\ for(k=1;k<=L;k++)

{ printf(\ }

getchar(); printf(\

if(low

图三 快速排序

- 8 -

4.1.3 直接插入排序

核心思想

经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止 核心代码

void Insertsort() {

int i,j,k,m=0,x=0; //初始化比较次数变量m，移动次数变量x printf(\原始数据为：（按回车键开始排序）\\n\\t\\t\ for(k=1;k<=L;k++) { printf(\ }

getchar(); printf(\ //主要运行部分 for(i=2;i<=L;i++) { if(R[i].key

- 9 -

}

printf(\第%d趟直接插入排序的结果为：\\n\\t\\t\ for(k=1;k<=L;k++) { printf(\ } getchar(); printf(\}

printf(\

printf(\比较次数是：\\t\\t\printf(\

printf(\移动次数是：\\t\\t\printf(\

printf(\排序最终结果是：\\n\\t\\t\for(i=1;i<=L;i++)

{ printf(\}

图四 直接插入排序

4.1.4 希尔排序 核心思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进

- 10 -

行直接插入排序；然后，取第二个增量d2

void Shellsort() {

int i,j,gap,x,k,y=0,m=0; //初始化比较次数变量m，移动次数变量y printf(\原始数据为：（按回车键开始排序）\\n\\t\\t\ for(k=1;k<=L;k++) { printf(\ }

getchar(); printf(\ //函数主要部分 gap=L/2; while(gap>0) { for(i=gap+1;i<=L;i++) { j=i-gap; while(j>0) { if(R[j].key>R[j+gap].key) { x=R[j].key;//交换语句 R[j].key=R[j+gap].key; R[j+gap].key=x; j=j-gap; y++;//移动次数++ } else { j=0; } } } gap=gap/2; m++;//比较次数++ //输出语句包括排序的结果及次数 printf(\第%d趟希尔排序的结果为：\\n\\t\\t\ for(k=1;k<=L;k++)

- 11 -

}

{ printf(\ } getchar(); printf(\}

printf(\比较次数是：\\t\\t\printf(\

printf(\移动次数是：\\t\\t\printf(\

printf(\排序最终结果是：\\n\\t\\t\for(i=1;i<=L;i++) { printf(\}

printf(\

图五 希尔排序

4.1.5 直接选择排序 核心思想

第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R{1}~R[n-1]中选取最小值，与R[2]交换，....， 第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取

- 12 -