数据结构实验报告六排序

一、实验目的

1、掌握内部排序的基本算法；
2、分析比较内部排序算法的效率。

二、实验内容和要求

1.运行下面程序：

#include <stdlib.h>
#include <stdio.h>
#define MAX 50
int slist[MAX]; /*待排序序列*/void insertSort(int list[], int n);
void createList(int list[], int *n);
void printList(int list[], int n);
void heapAdjust(int list[], int u, int v);
void heapSort(int list[], int n);/*直接插入排序*/
void insertSort(int list[], int n)
{int i = 1, j = 0, node = 0, count = 1;printf("对序列进行直接插入排序：\n");printf("初始序列为：");printList(list, n);for(i = 2; i <= n; i++){node = list[i];j = i - 1;while(j >= 0 && node < list[j]){list[j+1] = list[j];--j;}list[j+1] = node;printf("第%d次排序结果：", count++);printList(list, n);}
}
/*堆排序*/
void heapAdjust(int list[], int u, int v)
{int i = u, j , temp = list[i];j = 2 * i;while (j <= v){if(j < v && list[j] < list[j+1])j++; /*若右孩子较大，则把j修改为右孩子的下标*/if(temp < list[j]){list[i] = list[j]; /*将list[j]调到父亲的位置上*/i = j;j = 2 * i; /*修改i和j的值，以便继续向下筛选*/}elsebreak; /*筛选完成，终止循环*/}list[i] = temp; /*被筛结点的值放入最终位置*/
}
void heapSort(int list[], int n)
{int i = 0, temp = 0, count = 1;printf("对序列进行堆排序：\n");printf("初始序列为：");printList(list, n);for (i = n  / 2; i > 0; i--)heapAdjust(list, i, n); /*建立初始堆*/printf("建立的初始堆为：");printList(list, n);for(i = n ; i > 1; i--){/*循环，完成堆排序*/temp = list[1];list[1] = list[i];list[i] = temp; /*将第一个元素同当前区间内最后一个元素对换*/heapAdjust(list, 1 , i-1); /*筛选出list[1]结点*/printf("第%d次排序结果：", count++);printList(list, n);}
}
/*生成待排序序列*/
void createList(int list[], int *n)
{int i = 1,a;printf("请输入待排序序列(长度小于50,以输入一个字符结束):\n");while(scanf("%d",&a)==1){list[i] = a;i++;}*n=i-1;getchar();
}
/*输出排序结果*/
void printList(int list[], int n)
{int i = 1;for(; i <= n; i++){printf("  %d  ", list[i]);if(i % 10 ==0 && i != 0)printf("\n");}printf("\n");
}int main()
{int choice=1,length;while(choice!=0){printf("\n");printf("***** 内部排序算法演示程序 *****\n");printf("\n1. 直接插入排序 \n");printf("\n2. 堆排序 \n");printf("\n0. 退出\n");printf("\n请选择：");scanf("%d", &choice);getchar();switch(choice){case 1:{createList(slist, &length);insertSort(slist, length);break;}case 2:{createList(slist, &length);heapSort(slist, length);break;}default:choice=0;}printf("\n");}return 0;
}

输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束）

1）直接插入排序运行结果（写出每一趟的状态）：

对序列进行直接插入排序：
初始序列为： 49 38 65 97 13 27 49
第1次排序结果： 38 49 65 97 13 27 49
第2次排序结果： 38 49 65 97 13 27 49
第3次排序结果： 38 49 65 97 13 27 49
第4次排序结果： 13 38 49 65 97 27 49
第5次排序结果： 13 27 38 49 65 97 49
第6次排序结果： 13 27 38 49 49 65 97
实验六（1）

2）堆排序运行结果（写出每一趟的状态）：

对序列进行堆排序：
初始序列为： 49 38 65 97 13 27 49
建立的初始堆为： 97 49 65 38 13 27 49
第1次排序结果： 65 49 49 38 13 27 97
第2次排序结果： 49 38 49 27 13 65 97
第3次排序结果： 49 38 13 27 49 65 97
第4次排序结果： 38 27 13 49 49 65 97
第5次排序结果： 27 13 38 49 49 65 97
第6次排序结果： 13 27 38 49 49 65 97
实验六（2）

2、在1题中补充希尔排序算法。

算法代码：

void shellSort(int list[], int n)
{int i,j,d,temp,count=1;printf("对序列进行希尔排序：\n");printf("初始序列为：");printList(list, n);for(d=n/2;d>0;d/=2){for(i=d+1;i<=n;i++){temp=list[i];j=i-d;while(j>=1&&temp<list[j]){list[j+d]=list[j];j=j-d;}list[j+d]=temp;}printf("第%d次排序结果：", count++);printList(list, n);}
}

输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束）

运行结果（写出每一趟的状态）：

对序列进行希尔排序：
初始序列为： 49 38 65 97 13 27 49
第1次排序结果： 49 13 27 49 38 65 97
第2次排序结果： 13 27 38 49 49 65 97
实验六（3）

3、在1题中补充快速排序算法。

算法代码：

int count=1;
int Partition(int list[], int i, int j, int n)
{list[0]=list[i];int pivotkey=list[i];while(i<j){while(i<j&&list[j]>=pivotkey)--j;list[i]=list[j];while(i<j&&list[i]<=pivotkey)++i;list[j]=list[i];}list[i]=list[0];printf("第%d次排序结果：", count++);printList(list, n);return i;
}
void quickSort(int list[], int i, int j, int n)
{int pivot;if(i<j){pivot=Partition(list, i, j, n);quickSort(list,i,pivot-1,n);quickSort(list,pivot+1,j,n);}
}

输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束）

运行结果（写出每一趟的状态）：

对序列进行快速排序：
初始序列为： 49 38 65 97 13 27 49
第1次排序结果： 27 38 13 49 97 65 49
第2次排序结果： 13 27 38 49 97 65 49
第3次排序结果： 13 27 38 49 49 65 97
第4次排序结果： 13 27 38 49 49 65 97
实验六（4）

三、补充后完整代码

#include <stdlib.h>
#include <stdio.h>
#define MAX 50
int slist[MAX]; /*待排序序列*/void insertSort(int list[], int n);
void createList(int list[], int *n);
void printList(int list[], int n);
void heapAdjust(int list[], int u, int v);
void heapSort(int list[], int n);
void shellSort(int list[], int n);
int Partition(int list[], int i, int j, int n);
void quickSort(int list[], int i, int j, int n);/*直接插入排序*/
void insertSort(int list[], int n)
{int i = 1, j = 0, node = 0, count = 1;printf("对序列进行直接插入排序：\n");printf("初始序列为：");printList(list, n);for(i = 2; i <= n; i++){node = list[i];j = i - 1;while(j >= 0 && node < list[j]){list[j+1] = list[j];--j;}list[j+1] = node;printf("第%d次排序结果：", count++);printList(list, n);}
}
/*堆排序*/
void heapAdjust(int list[], int u, int v)
{int i = u, j, temp = list[i];j = 2 * i;while (j <= v){if(j < v && list[j] < list[j+1])j++; /*若右孩子较大，则把j修改为右孩子的下标*/if(temp < list[j]){list[i] = list[j]; /*将list[j]调到父亲的位置上*/i = j;j = 2 * i; /*修改i和j的值，以便继续向下筛选*/}elsebreak; /*筛选完成，终止循环*/}list[i] = temp; /*被筛结点的值放入最终位置*/
}
void heapSort(int list[], int n)
{int i = 0, temp = 0, count = 1;printf("对序列进行堆排序：\n");printf("初始序列为：");printList(list, n);for (i = n  / 2; i > 0; i--)heapAdjust(list, i, n); /*建立初始堆*/printf("建立的初始堆为：");printList(list, n);for(i = n ; i > 1; i--){/*循环，完成堆排序*/temp = list[1];list[1] = list[i];list[i] = temp; /*将第一个元素同当前区间内最后一个元素对换*/heapAdjust(list, 1, i-1);  /*筛选出list[1]结点*/printf("第%d次排序结果：", count++);printList(list, n);}
}
/*希尔排序*/
void shellSort(int list[], int n)
{int i,j,d,temp,count=1;printf("对序列进行希尔排序：\n");printf("初始序列为：");printList(list, n);for(d=n/2; d>0; d/=2){for(i=d+1; i<=n; i++){temp=list[i];j=i-d;while(j>=1&&temp<list[j]){list[j+d]=list[j];j=j-d;}list[j+d]=temp;}printf("第%d次排序结果：", count++);printList(list, n);}
}
/*快速排序*/
int count=1;
int Partition(int list[], int i, int j, int n)
{list[0]=list[i];int pivotkey=list[i];while(i<j){while(i<j&&list[j]>=pivotkey)--j;list[i]=list[j];while(i<j&&list[i]<=pivotkey)++i;list[j]=list[i];}list[i]=list[0];printf("第%d次排序结果：", count++);printList(list, n);return i;
}
void quickSort(int list[], int i, int j, int n)
{int pivot;if(i<j){pivot=Partition(list, i, j, n);quickSort(list,i,pivot-1,n);quickSort(list,pivot+1,j,n);}
}
/*生成待排序序列*/
void createList(int list[], int *n)
{int i = 1,a;printf("请输入待排序序列(长度小于50,以输入一个字符结束):\n");while(scanf("%d",&a)==1){list[i] = a;i++;}*n=i-1;getchar();
}
/*输出排序结果*/
void printList(int list[], int n)
{int i = 1;for(; i <= n; i++){printf("  %d  ", list[i]);if(i % 10 ==0 && i != 0)printf("\n");}printf("\n");
}int main()
{int choice=1,length;while(choice!=0){printf("\n");printf("***** 内部排序算法演示程序 *****\n");printf("\n1. 直接插入排序 \n");printf("\n2. 堆排序 \n");printf("\n3. 希尔排序 \n");printf("\n4. 快速排序 \n");printf("\n0. 退出\n");printf("\n请选择：");scanf("%d", &choice);getchar();switch(choice){case 1:{createList(slist, &length);insertSort(slist, length);break;}case 2:{createList(slist, &length);heapSort(slist, length);break;}case 3:{createList(slist, &length);shellSort(slist, length);break;}case 4:{createList(slist, &length);printf("对序列进行快速排序：\n");printf("初始序列为：");printList(slist, length);quickSort(slist, 1, length, length);break;}default:choice=0;}printf("\n");}return 0;
}