【算法】实验 2 排序
迪丽瓦拉
2024-04-23 09:00:36
0

目录

【实验目的】

【实验预习】

【实验内容】

1. 阅读、分析、完善和编写算法,实现内部排序的各种基本算法

(1)直接插入排序。阅读下列程序,理解对应各个函数的功能。参考程序如下:

(2)冒泡排序。阅读下列程序,完善算法代码。参考程序如下: 

(3)简单选择排序。参考直接插入排序或冒泡排序算法,设计算法实现简单选择排序

2. 阅读、分析、完善和编写算法,实现内部排序的各种先进算法 

(1)希尔排序。阅读下列程序,理解对应各个函数的功能。参考程序如下:

(2)快速排序。阅读下列程序,完善算法代码。参考程序如下:

(3)堆排序。阅读下列程序,完善算法代码。参考程序如下:


【实验目的】

1. 掌握内部排序的基本算法(直接插入排序、简单选择排序、冒泡排序)

2. 掌握内部排序的先进算法(希尔排序、堆排序、快速排序、归并排序和基数排序)

3. 理解其他内部排序方法

【实验预习】

1. 插入类排序、交换类排序和基数排序的基本原理

2. 内部排序中稳定的排序方法有哪些

3. 比较直接插入排序、简单选择排序、冒泡排序、希尔排序、堆排序、快速排序的排序效率

【实验内容】

1. 阅读、分析、完善和编写算法,实现内部排序的各种基本算法

假设待排序序列为{49,38,65,97,76,13,27,49},采用一维数组slist[]存储待排序序列

(1)直接插入排序。阅读下列程序,理解对应各个函数的功能。参考程序如下:

#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]

(2)冒泡排序。阅读下列程序,完善算法代码。参考程序如下: 

#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;
}

(3)简单选择排序。参考直接插入排序或冒泡排序算法,设计算法实现简单选择排序

#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]

2. 阅读、分析、完善和编写算法,实现内部排序的各种先进算法 

假设待排序序列为{49,38,65,97,76,13,27,49},采用一维数组slist[]存储待排序序列

(1)希尔排序。阅读下列程序,理解对应各个函数的功能。参考程序如下:

#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;
}

(2)快速排序。阅读下列程序,完善算法代码。参考程序如下:

#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);
}

(3)堆排序。阅读下列程序,完善算法代码。参考程序如下:

#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(j             j++;
        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;
}

相关内容