快速排序算法设计(10003809386j) 一实验目的使学生掌握常用内部排序的基本概念和基本方法使学生掌握常用内部排序方法的性能评价；使学生掌握排序方法在实际问题中的应用；二实验环境所需硬件环境为微机；所需软件环境为Microsoft Visual C++ 6.0；三实验内容此部分仅用写出要求的实验代码,并加上必要的注释#include <stdio.h>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OVERFLOW -2#define OK 1#define FAILURE 0#define TRUE 1#define FALSE 0#define ERROR -1typedef int ElemType;typedef int Status;void PrintElem(ElemType *e){printf("%5d",*e);}#include <stdlib.h>#include "ElemType.c"int p[6];//记录比较次数int q[6];//记录移动次数void InsertSort(int *L,int n)// 直接插入排序{ int i,j;for(i=2;i<=n;i++){if(L[i]<L[i-1]){L[0]=L[i];L[i]=L[i-1];for(j=i-2;L[0]<L[j];j--){ L[j+1]=L[j];p[0]++;q[0]++;}L[j+1]=L[0];q[0]+=3;}p[0]++;}}void ShellInsert(int *L,int n,int dk)// 希尔排序{ int i,j;for(i=dk+1;i<=n;i++){if(L[i]<L[i-dk]){L[0]=L[i];for(j=i-dk;j>0&&L[0]<L[j];j-=dk){L[j+dk]=L[j];p[1]++;q[1]++;}L[j+dk]=L[0];q[1]+=2;}p[1]++; }}void ShellSort(int *L,int n) // 希尔排序{ int dalt[6]={13,11,7,5,3,1};int i;for(i=0;i<6;i++)ShellInsert(L,n,dalt[i]);}void buddlesort(int *L,int n)// 冒泡排序{ int i,j,k,m;for(i=n,k=1;i>1&&k;i--){ k=0;for(j=1;j<i;j++){if(L[j]>L[j+1]){ m=L[j];L[j]=L[j+1];L[j+1]=m;k=1;q[2]+=3;}p[2]++; }}}int Partition(int *L,int low,int high){ int k;L[0]=L[low];k=L[low];while(low<high){ while(low<high&&L[high]>=k) {high--;p[3]++;}L[low]=L[high];while(low<high&&L[low]<=k) {low++;p[3]++;} L[high]=L[low];p[3]+=2;q[3]+=2; }L[low]=L[0];q[3]+=3;return low;}void QSort(int *L,int low,int high){ int k;if(low<high){ k=Partition(L,low,high);QSort(L,low,k-1);QSort(L,k+1,high); } }void QuikSort(int *L,int n)// 快速排序{ QSort(L,1,n); }void HeapAdjust(int *L,int s,int m)// 堆排序{ int j,t;t=L[s];for(j=2*s;j<=m;j*=2){if(j<m&&L[j]<L[j+1]){j++;p[4]++;}if(t>=L[j]) break;p[4]+=2;q[4]++;L[s]=L[j];s=j;}L[s]=t;q[4]+=2;}void HeapSort(int *L,int n) // 堆排序{ int i,t;for(i=n/2;i>0;i--)HeapAdjust(L,i,n);for(i=n;i>1;i--){t=L[1];L[1]=L[i];L[i]=t;q[4]+=3;HeapAdjust(L,1,i-1); }}void Merge(int *SR,int *TR,int i,int m,int n) { int j,k,t;for(j=m+1,k=i;i<=m&&j<=n;++k){ if(SR[i]<SR[j]){TR[k]=SR[i];i++;}else{TR[k]=SR[j];j++;}q[5]++;p[5]++;}if(i<=m)for(t=i;t<=m;t++){ TR[k]=SR[t];q[5]++;k++;}if(j<=n)for(t=j;t<=n;t++){ TR[k]=SR[t];q[5]++;k++;}}void MSort(int *SR,int *TR1,int s,int t){ int *TR2=(int *)malloc(sizeof(int)*t);int m;if(s==t){TR1[s]=SR[s];q[5]++;}else{ m=(s+t)/2;MSort(SR,TR2,s,m);MSort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);}}void MergeSort(int *L,int n)// .归并排序{MSort(L,L,1,n); }int main(){ //主函数1int k,i,a[10]={5,8,1,11,23,41,16,44,14,9};int L[101];printf("原数字排列为：");for(i=0;i<10;i++)L[i+1]=a[i];for(i=0;i<10;i++)printf("%d,",L[i+1]);printf("\n-------------主菜单-------------\n"); printf("1.直接插入排序\n");printf("2.希尔排序\n");printf("3.冒泡排序\n");printf("4.快速排序\n");printf("5.堆排序\n");printf("6.归并排序\n");printf("7.退出\n");printf("--------------------------------\n");while(1){ printf("请选择选项：");scanf("%d",&k);switch(k){ case 1:printf("使用直接排序方法得到的结果是：\n");InsertSort(L,10);for(i=0;i<10;i++) printf("%d,",L[i+1]); printf("\n");break;case 2:for(i=0;i<10;i++) L[i+1]=a[i];printf("使用希尔排序方法得到的结果是：\n");ShellSort(L,10);for(i=0;i<10;i++) printf("%d,",L[i+1]); printf("\n");break;case 3:for(i=0;i<10;i++) L[i+1]=a[i];printf("使用冒泡排序方法得到的结果是：\n");buddlesort(L,10);for(i=0;i<10;i++) printf("%d,",L[i+1]); printf("\n");break;case 4:for(i=0;i<10;i++) L[i+1]=a[i];printf("使用快速排序方法得到的结果是：\n");QuikSort(L,10);for(i=0;i<10;i++) printf("%d,",L[i+1]); printf("\n");break;case 5:for(i=0;i<10;i++) L[i+1]=a[i];printf("使用堆排序方法得到的结果是：\n");HeapSort(L,10);for(i=0;i<10;i++)printf("%d,",L[i+1]);printf("\n");break;case 6:for(i=0;i<10;i++) L[i+1]=a[i];printf("使用归并排序方法得到的结果是：\n");MergeSort(L,10);for(i=0;i<10;i++)printf("%d,",L[i+1]);printf("\n");break;case 7:printf("已退出！");exit(0);break;default:printf("\nInput error!"); }}return 0; }#include<stdio.h>//主函数2#include<stdlib.h>#include "Sort.c"int main(){int L[101],i,k;for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;printf("\n-------------主菜单-------------\n");printf("1.直接插入排序\n");printf("2.希尔排序\n");printf("3.冒泡排序\n");printf("4.快速排序\n");printf("5.堆排序\n");printf("6.归并排序\n");printf("7.退出\n");printf("--------------------------------\n");while(1){ printf("请选择选项：");scanf("%d",&k);switch(k){case 1:InsertSort(L,100);printf("1.直接插入排序的比较次数和移动次数分别为：%d,%d\n",p[0],q[0]);break;case 2:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;ShellSort(L,100);printf("2.希尔排序的比较次数和移动次数分别为：%d,%d\n",p[1],q[1]);break;case 3:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;buddlesort(L,100);printf("3.冒泡排序的比较次数和移动次数分别为：%d,%d\n",p[2],q[2]);break;case 4:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;QuikSort(L,100);printf("4.快速排序的比较次数和移动次数分别为：%d,%d\n",p[3],q[3]);break;case 5:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;HeapSort(L,100);printf("5.堆排序的比较次数和移动次数分别为：%d,%d\n",p[4],q[4]);break;case 6:for(i=0;i<100;i++)L[i+1]=100 + rand() % (1000 - 100) ;MergeSort(L,100);printf("6.归并排序的比较次数和移动次数分别为：%d,%d\n",p[5],q[5]);break;case 7:printf("已退出！");exit(0);break;default:printf("\nInput error!"); }}return 0; }四实验分析及问题思考1.分析和总结各种内部排序方法的优缺点；直接插入排序优点:移动元素次数少，只需要一个辅助空间缺点：效率不高冒泡排序优点：比较简单，空间复杂度较低，是稳定的缺点：时间复杂度太高，效率不好简单选择排序优点：所需移动记录的次数比较少，最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录缺点：简单选择排序是不稳定排序快速排序优点：极快，数据移动少缺点：不稳定希尔排序优点：快，数据移动少缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取归并排序优点：归并排序是稳定的排序方法缺点：需要一个与原始序列同样大小的辅助序列堆排序优点：在最坏情况下时间复杂度也为O(nlogn)，并且它仅需一个记录大小供交换用的辅助存储空间缺点：记录数较少时不提倡使用基数排序优点：基数排序法的效率高于其它的比较性排序法，稳定的排序快速排序算法设计(10003809386j) 实验自评检查表实验内容自评结果（在对应格内打√）不熟练一般比较熟练熟练简单排序方法直接插入排序√起泡排序√简单选择排序√先进排序方法快速排序√希尔排序√归并排序√实验的心得体会通过这次实验，我更加清楚地了解了各个算法的实现过程，学会应用随机数表，而且自己体会到了各个算法的时间复杂度。