（1）冒泡、直插、选择、快速、希尔、归并排序算法进行比较； （2）待排序的元素的关键字为整数。其中的数

Question

用MFC单文档编写
(1) 对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；
(2) 待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生(如10000个)，至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。
(3) 演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表，用饼图或条形图进行表示，以便比较各种排序的优劣。

Answer 1

1.冒泡排序已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。 优点：稳定，比较次数已知；缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。 初始关键字 [49 3865 97 76 13 27 49]第一趟排序后 [38 4965 76 13 27 49] 97第二趟排序后 [38 4965 13 27 49] 76 97第三趟排序后 [38 4913 27 49] 65 76 97第四趟排序后 [38 1327 49] 49 65 76 97第五趟排序后 [38 1327] 49 49 65 76 97第六趟排序后 [13 27]38 49 49 65 76 97第七趟排序后 [13] 2738 49 49 65 76 97最后排序结果 13 2738 49 49 76 76 97 #include <iostream>using namespace std;void main()   {      int i,j,k;      int a[8]={49,38,65,97,76,13,27,49};      for(i=7;i>=0;i--)       {          for(j=0;j<i;j++)            {                if(a[j]>a[j+1])                   {                     k=a[j];                     a[j]=a[j+1];                     a[j+1]=k;                   }             }        }          for(i=0;i<8;i++)       cout<<a<<endl;  } 2.选择排序 ①初始状态：无序区为R[1..n]，有序区为空。 ②第1趟排序    在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。…… ③第i趟排序第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区.这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 优点：稳定，比较次数与冒泡排序一样；缺点：相对之下还是慢。 初始关键字 [49 3865 97 76 13 27 49]第一趟排序后 13 〔38 65 97 76 49 27 49]第二趟排序后 13 27 〔65 97 76 49 38 49]第三趟排序后 13 2738 [97 76 49 65 49]第四趟排序后 13 2738 49 [49 97 65 76]第五趟排序后 13 2738 49 49 [97 97 76]第六趟排序后 13 2738 49 49 76 [76 97]第七趟排序后 13 2738 49 49 76 76 [ 97]最后排序结果 13 2738 49 49 76 76 97 #include <iostream>using namespace std;void main(){  int i,j,k,t;  int R[8]={49,38,65,97,76,13,27,49};  for(i=0;i<7;i++)    {     k=i;    for(j=i+1;j<8;j++)         if(R[j]<R[k])         k=j;      if(k!=i)        {        t=R[j];R[j]=R[k];R[k]=t;        }    }for(i=0;i<8;i++)       cout<<R<<endl;  }

3.插入排序已知一组，一组无序数据b[1]、b[2]、……b[m]，需将其变成一个升序数列。先创建一个变量a。首先将不b[1]与b[2],如果b[1]大于b[2]则交换位置，否则不变；再比较b[2]与b[3]，如果b[3]小于b[2]，则将b[3]赋值给a，再将a与b[1]比较，如果a小于b[1]；则将b[2]，b[1]依次后移；在将a放在b[1]处以此类推，直到排序结束。初始关键字 [49 3865 97 76 13 27 59]     a   b[1] b[2]  b[3]  b[4] b[5]  b[6]  b[7] b[8]1-----49  49 >  38   65   97    76  13    27   5938   49   49   ……….38   38   49   ……….2-----38  38    49 < 65  97    76   13   27   593-----38  38    49  65 <97    76   13   27   594----38  38     49  65   97>   76   13   27   5976   38   49   65   97   97……..76   38   49   65   76   97……..以此类推void insertSort(Type* arr,long len){      long i=0,j=0;      for(i=1;i<len;i++)      {              j=i;              tmpData=arr[j];//tmpData用来储存数据             while(tmpData<arr[j-1]&&j>0)              {                     arr[j]=arr[j-1];                     j--;              }              arr[j]=tmpData;      }}4.缩小增量排序(希尔排序)由希尔在1959年提出，又称希尔排序。已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d<n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1。增量d(1, 3, 7,15, 31, …, 2^k-1)是使用最广泛的增量序列之一.优点：快，数据移动少；缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。初始：d＝5           49   38   65  97   76   13  27   49   55  44                   一趟结果           13   27   49 55   44   49  38   65   97 76  d=3     |----------------------|----------------------|---------------------|                                   二趟结果           13   44   49 38   27   49  55   65   97  76  d=1       三趟结果                13   27   38 44   49  49   55   65   76  97       #include <iostream>using namespace std;#define MAX 16          void shell_sort(int *x, int n){       inth, j, k, t;       for(h=n/2;h>0; h=h/2) /*控制增量*/       {              for(j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/              {                     t= *(x+j);                     for(k=j-h; (k>=0 && t<*(x+k)); k-=h)                     {                            *(x+k+h)= *(x+k);                     }                     *(x+k+h)= t;              }       }}void main(){       int*p, i, a[MAX];       p= a;       cout<<"InputMAX number for sorting :"<<endl;       for(i=0; i<MAX; i++)              cin>>*p++;       p=a;       shell_sort(p,MAX);       for(p=a, i=0; i<MAX; i++)       {              cout<<*p++<<endl;       }       cout<<endl;}

5.快速排序快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据<a[x]，a[k+1]~a[n]中的每一个数据>a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。优点：极快，数据移动少；缺点：不稳定。分段插入排序void QuickSort(int *pData, int left, intright){int i, j;int middle,iTemp;i = left;j = right;middle =pData[(left + right) / 2]; //求中间值do{while((pData < middle) && (i < right)) //从左扫描大于中值的数i++;while((pData[j] > middle) && (j > left)) //从右扫描小于中值的数j--;if (i <=j) //找到了一对值{//交换iTemp =pData;pData =pData[j];pData[j] =iTemp;i++;j--;}} while (i<= j) ; //如果两边扫描的下标交错，就停止（完成一次）//当左边部分有值(left<j)，递归左半边if(left<j)QuickSort(pData,left,j);//当右边部分有值(right>i)，递归右半边if(right>i)QuickSort(pData,i,right);} 6.归并排序算法合并排序（MERGESORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2  个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。例如数组A有7个数据，分别是： 49   38   65 97   76   13  27，那么采用归并排序算法的操作过程如图7所示：初始值 [49]   [38]  [65]   [97]   [76]  [13]   [27]第一次合并之后         [38    49]    [65    97]  [13     76]   [27]第二次合并之后         [38    49      65    97]  [13     27     76]第三次合并之后         [13    27      38    49    65      76    97]合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律,当有N个子序列时可以推断出合并的次数是X(2  >=N,符合此条件的最小那个X)。其时间复杂度为：O(nlogn).所需辅助存储空间为：O(n)归并排序：#include <stdio.h>void merge(int a[],int p,int q,int r){int n1=q-p+1,n2=r-q,i,j,k;int l[1002],R[1002];for (i=1;i<=n1;i++)l=a[p+i-1];for (j=1;j<=n2;j++)R[j]=a[q+j];R[n2+1]=l[n1+1]=999999;i=j=1;for (k=p;k<=r;k++){if (l<=R[j]){a[k]=l;i++;}else{a[k]=R[j];j++;}}}void mergesort(int a[],int p,int r){int q;if (p<r){q=(p+r)/2;mergesort(a,p,q);mergesort(a,q+1,r);merge(a,p,q,r);}}int main(){int a[1001],t,n,i;scanf("%d",&t);while (t--){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a);mergesort(a,1,n);for (i=1;i<=n;i++){printf("%d",a);if (i!=n)printf(" ");}printf("\n");}return 0;}

Answer 2

#include "stdio.h "
#include "stdlib.h "
#define Max 100 //假设文件长度
typedef struct{ //定义记录类型
int key; //关键字项
}RecType;
typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵
int n; //顺序表实际的长度
//==========直接插入排序法======
void InsertSort(SeqList R) { //对顺序表R中的记录R[1¨n]按递增序进行插入排序
int i,j;
for(i=2;i <=n;i++) //依次插入R[2]，……，R[n]
if(R[i].key <R[i-1].key){ //若R[i].key大于等于有序区中所有的keys，则R[i]留在原位 R[0]=R[i];j=i-1; //R[0]是R[i]的副本 do { //从右向左在有序区R[1¨i-1]中查找R[i] 的位置 R[j+1]=R[j]; //将关键字大于R[i].key的记录后移 j--; }while(R[0].key <R[j].key); //当R[i].key≥R[j].key 是终止
R[j+1]=R[0]; //R[i]插入到正确的位置上
}//endif
}
//==========冒泡排序======= typedef enum{FALSE,TRUE} Boolean; //FALSE为0，TRUE为1
void BubbleSort(SeqList R) { //自下向上扫描对R做冒泡排序
int i,j;
bool exchange; //交换标志 for(i=1;i <n;i++) { //最多做n-1趟排序
exchange=false; //本趟排序开始前，交换标志应为假
for(j=n-1;j> =i;j--){ //对当前无序区R[i¨n] 自下向上扫描
if(R[j+1].key <R[j].key){ //两两比较，满足条件交换记录
R[0]=R[j+1]; //R[0]不是哨兵，仅做暂存单元
R[j+1]=R[j];
R[j]=R[0];
exchange=true; //发生了交换，故将交换标志置为真
}
if(! exchange) return; //本趟排序未发生交换，提前终止算法
}// endfor（为循环）
}
//==========快速排序=======
//1.========一次划分函数=====
int Partition(SeqList R,int i,int j) {
// 对R[i¨j]做一次划分，并返回基准记录的位置
RecType pivot=R[i]; //用第一个记录作为基准
while(i <j) { //从区间两端交替向中间扫描，直到i=j
while(i <j &&R[j].key> =pivot.key) //基准记录pivot相当与在位置i上
j--; //从右向左扫描，查找第一个关键字小于pivot.key的记录R[j]
if(i <j) //若找到的R[j].key < pivot.key，则
R[i++]=R[j]; //交换R[i]和R[j]，交换后i指针加1
while(i <j &&R[i].key <=pivot.key) //基准记录pivot相当与在位置j上
i++; //从左向右扫描，查找第一个关键字小于pivot.key的记录R[i]
if(i <j) //若找到的R[i].key > pivot.key，则
R[j--]=R[i]; //交换R[i]和R[j]，交换后j指针减1
}
R[i]=pivot; //此时，i=j，基准记录已被最后定位
return i; //返回基准记录的位置
}
//2.=====快速排序===========
void QuickSort(SeqList R,int low,int high) { //R[low..high]快速排序
int pivotpos; //划分后基准记录的位置
if(low <high) { //仅当区间长度大于1时才排序
pivotpos=Partition(R,low,high); //对R[low..high]做一次划分，得到基准记录的位置
QuickSort(R,low,pivotpos-1); //对左区间递归排序
QuickSort(R,pivotpos+1,high); //对右区间递归排序
}
}
//======直接选择排序========
void SelectSort(SeqList R) {
int i,j,k;
for(i=1;i <n;i++){ //做第i趟排序（1≤i≤n-1）
k=i;
for(j=i+1;j <=n;j++) //在当前无序区R[i¨n]中选key最小的记录R[k]
if(R[j].key <R[k].key)
k=j; //k记下目前找到的最小关键字所在的位置
if(k!=i) { //交换R[i]和R[k]
R[0]=R[i];R[i]=R[k];R[k]=R[0];
} //endif
} //endfor
}
//======堆排序========
//==========大根堆调整函数=======
void Heapify(SeqList R,int low,int high) {
// 将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质
int large; //large指向调整结点的左、右孩子结点中关键字较大者
RecType temp=R[low]; //暂存调整结点
for(large=2*low; large <=high;large*=2){ //R[low]是当前调整结点
//若large> high,则表示R[low]是叶子，调整结束；否则先令large指向R[low]的左孩子
if(large <high && R[large].key <R[large+1].key)
large++; //若R[low]的右孩子存在且关键字大于左兄弟，则令large指向它
//现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者
if(temp.key> =R[large].key) //temp始终对应R[low]
break; //当前调整结点不小于其孩子结点的关键字，结束调整
R[low]=R[large]; //相当于交换了R[low]和R[large]
low=large; //令low指向新的调整结点，相当于temp已筛下到large的位置
}
R[low]=temp; //将被调整结点放入最终位置上
}
//==========构造大根堆==========
void BuildHeap(SeqList R) { //将初始文件R[1..n]构造为堆
int i;
for(i=n/2;i> 0;i--)
Heapify(R,i,n); //将R[i..n]调整为大根堆
}
//==========堆排序===========
void HeapSort(SeqList R) { //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i;
BuildHeap(R); //将R[1..n]构造为初始大根堆
for(i=n;i> 1;i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1]; R[1]=R[i];R[i]=R[0]; //将堆顶和堆中最后一个记录交换
Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质。
}
}
//==========二路归并排序===========
//===将两个有序的子序列R[low..m]和R[m+1..high]归并成有序的序列R[low..high]===
void Merge(SeqList R,int low,int m,int high) {
int i=low,j=m+1,p=0; //置初始值
RecType *R1; //R1为局部量
R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); //申请空间
while(i <=m && j <=high) //两个子序列非空时取其小者输出到R1[p]上
R1[p++]=(R[i].key <=R[j].key)? R[i++]:R[j++];
while(i <=m) //若第一个子序列非空，则复制剩余记录到R1
R1[p++]=R[i++];
while(j <=high) //若第二个子序列非空，则复制剩余记录到R1中
R1[p++]=R[j++];
for(p=0,i=low;i <=high;p++,i++)
R[i]=R1[p]; //归并完成后将结果复制回R[low..high]
}
//=========对R[1..n]做一趟归并排序========
void MergePass(SeqList R,int length) {
int i;
for(i=1;i+2*length-1 <=n;i=i+2*length)
Merge(R,i,i+length-1,i+2*length-1); //归并长度为length的两个相邻的子序列
if(i+length-1 <n) //尚有一个子序列，其中后一个长度小于length
Merge(R,i,i+length-1,n); //归并最后两个子序列
//注意：若i≤n且i+length-1≥n时，则剩余一个子序列轮空，无须归并
}
//========== 自底向上对R[1..n]做二路归并排序===============
void MergeSort(SeqList R) {
int length;
for(length=1;length <n;length*=2) //做[lgn]趟排序
MergePass(R,length); //有序长度≥n时终止
}
//==========输入顺序表========
void input_int(SeqList R) {
int i;
printf( "Please input num(int): ");
scanf( "%d ",&n);
printf( "Plase input %d integer: ",n);
for(i=1;i <=n;i++)
scanf( "%d ",&R[i].key);
}
//==========输出顺序表========
void output_int(SeqList R) {
int i;
for(i=1;i <=n;i++)
printf( "%4d ",R[i].key);
}
//==========主函数======
void main() {
int i;
SeqList R;
input_int(R);
printf( "\t******** Select **********\n ");
printf( "\t1: Insert Sort\n ");
printf( "\t2: Bubble Sort\n ");
printf( "\t3: Quick Sort\n ");
printf( "\t4: Straight Selection Sort\n ");
printf( "\t5: Heap Sort\n ");
printf( "\t6: Merge Sort\n ");
printf( "\t7: Exit\n ");
printf( "\t***************************\n ");
scanf( "%d ",&i); //输入整数1-7，选择排序方式
switch (i){
case 1: InsertSort(R);
break; //值为1，直接插入排序
case 2: BubbleSort(R);
break; //值为2，冒泡法排序
case 3: QuickSort(R,1,n);
break; //值为3，快速排序
case 4: SelectSort(R);
break; //值为4，直接选择排序
case 5: HeapSort(R);
break; //值为5，堆排序
case 6: MergeSort(R);
break; //值为6，归并排序
case 7: exit(0); //值为7，结束程序
}
printf( "Sort reult: ");
output_int(R);
}本回答被提问者和网友采纳

Answer 3

这种问题还真有人回答...