目录
【实验目的】
【实验预习】
【实验内容】
1. 阅读、分析、完善和编写算法,实现内部排序的各种基本算法
(1)直接插入排序。阅读下列程序,理解对应各个函数的功能。参考程序如下:
(2)冒泡排序。阅读下列程序,完善算法代码。参考程序如下:
(3)简单选择排序。参考直接插入排序或冒泡排序算法,设计算法实现简单选择排序
2. 阅读、分析、完善和编写算法,实现内部排序的各种先进算法
(1)希尔排序。阅读下列程序,理解对应各个函数的功能。参考程序如下:
(2)快速排序。阅读下列程序,完善算法代码。参考程序如下:
(3)堆排序。阅读下列程序,完善算法代码。参考程序如下:
1. 掌握内部排序的基本算法(直接插入排序、简单选择排序、冒泡排序)
2. 掌握内部排序的先进算法(希尔排序、堆排序、快速排序、归并排序和基数排序)
3. 理解其他内部排序方法
1. 插入类排序、交换类排序和基数排序的基本原理
2. 内部排序中稳定的排序方法有哪些
3. 比较直接插入排序、简单选择排序、冒泡排序、希尔排序、堆排序、快速排序的排序效率
假设待排序序列为{49,38,65,97,76,13,27,49},采用一维数组slist[]存储待排序序列
#include
#include
#define MAX 50
void insertSort(int list[],int n);
void createList(int list[],int *n);
void printList(int list[],int n);
void insertSort(int list[],int n){ //函数功能:对输入的序列进行插入排序 int i,j,count=1;printf("对序列进行直接插入排序:\n");printf("初始序列如下:");printList(list,n);for(i=2;i<=n;i++){list[0]=list[i];j=i-1;while(j>0&&list[0]
#include
#include
#define MAX 50
void bubbleSort(int list[],int n);
void createList(int list[],int *n);
void printList(int list[],int n);
void bubbleSort(int list[],int n){int i=1,j,t,count=1,flag;printf("对序列进行冒泡排序:\n");printf("初始序列如下:");printList(list,n);for(flag=1,i=1;ilist[j+1]){t=list[j];list[j]=list[j+1];list[j+1]=t;flag=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 length;int slist[MAX];createList(slist,&length);bubbleSort(slist,length);printf("最终的排序结果:\n");printList(slist,length);return 0;
}
#include
#include
#define MAX 50
void selectSort(int list[],int n);
void createList(int list[],int *n);
void printList(int list[],int n);
void selectSort(int list[],int n){int i,j,k,t,count=1;printf("对序列进行简单选择排序:\n");printf("初始序列如下:");printList(list,n);for(i=1;i<=n-1;i++){k=i;for(j=i+1;j<=n;j++){if(list[j]
假设待排序序列为{49,38,65,97,76,13,27,49},采用一维数组slist[]存储待排序序列
#include
#include
#define MAX 50
void createList(int list[],int *n);
void printList(int list[],int n);
void ShellSort(int list[],int dlta[],int t,int n);
void Shellinsert(int list[],int dk,int n);
void createdlta(int n,int dlta[],int *t);
void ShellSort(int list[],int dlta[],int t,int n){ //函数功能:进行希尔排序
int i,k;
for(k=0;k
printf("\n第%d趟希尔排序,增量dlta=%d,排序结果为:\n",k+1,dlta[k]);
Shellinsert(list,dlta[k],n);
printList(list,n);
}
}
void Shellinsert(int list[],int dk,int n){ //函数功能:进行希尔排序的其中一轮排序
int i,j;
for(i=dk+1;i<=n;++i){
if(list[i]
list[0]=list[i];
for(j=i-dk;j>0&&list[0]
list[j+dk]=list[j];
}
list[j+dk]=list[0];
}
}
}
void createdlta(int n,int dlta[],int *t){ //函数功能:得到希尔排序的增量放在dlta数组中
int i=0;
while(n>1){
n/=2;
if(n%2==1||n==2)
dlta[i]=n;
else dlta[i]=n+1;
i++;
}
*t=i;
}
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 length,t;
int slist[MAX],dlta[MAX];
createList(slist,&length);
createdlta(length,dlta,&t);
ShellSort(slist,dlta,t,length);
printf("最终的排序结果:\n");
printList(slist,length);
return 0;
}
#include
#include
#define MAX 50
int times=0;
void createList(int list[],int *n);
void printList(int list[],int n);
void QuickSort(int list[],int n);
void QSort(int list[],int low,int high);
int Partition(int list[],int low,int high);
int Partition(int list[],int low,int high){
int pivotkey,control=0;
list[0]=list[low];
pivotkey=list[low];
while(low
while(low=pivotkey){
--high;
}
list[low]=list[high];
while(low
++low;
}
list[high]=list[low];
}
list[low]=list[0];
return low;
}
void QSort(int list[],int low,int high){
int pivotloc,i,pivotkey;
pivotkey=list[low];
if(low
printf("\n这是第%d次划分,枢轴值为:%d\n",++times,pivotkey);
pivotloc=Partition(list,low,high);
for(i=low;i<=high;i++){
if(list[i]==pivotkey&&i==pivotloc)
printf("[%d]",list[i]);
else
printf("%d",list[i]);
}
QSort(list,low,pivotloc-1);
QSort(list,pivotloc+1,high);
}
}
void QuickSort(int list[],int n){
QSort(list,1,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 length;
int slist[MAX];
createList(slist,&length);
printf("初始的排序序列:\n");
printList(slist,length);
QuickSort(slist,length);
printf("\n\n最终的排序结果:\n");
printList(slist,length);
}
#include
#include
#define MAX 50
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 heapAdjust(int list[],int u,int v){
int i=u,j,temp=list[i];
j=2*i;
while(j<=v){
if(jj++;
if(temp
list[i]=list[j];
i=j;
j=2*i;
}else{
break;
}
}
list[i]=temp;
}
void heapSort(int list[],int n){
int i=0,count=1;
for(i=n/2;i>0;i--){
heapAdjust(list,i,n);
}
for(i=n;i>1;i--){
list[0]=list[1];
list[1]=list[i];
list[i]=list[0];
heapAdjust(list,1,i-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 length;
int slist[MAX];
createList(slist,&length);
printf("初始的排序序列:\n");
printList(slist,length);
heapSort(slist,length);
printf("\n\n最终的排序结果:\n");
printList(slist,length);
return 0;
}