搜索
【一】需求分析课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。【二】概要设计1.堆排序⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(NlogN)。⑵程序实现及核心代码的注释：for(j=2*i+1;j=m;j=j*2+1){if(jm-1&&(su[j]su[j+1]))j++;if(temp=su[j])break;su[i]=su[j];i=j;}su[i]=temp;}voiddpx()//堆排序{inti,temp;cout排序之前的数组为：endl;output();for(i=N/2-1;i=0;i--){head(i,N);}for(i=N-1;i0;i--){temp=su[i];su[i]=su[0];su[0]=temp;head(0,i-1);}cout排序之后的数组为：endl;output();}2.归并排序⑴算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。⑵程序实现及核心代码的注释：intis2[1000];voidbin(intlow,intmid,inthigh){inti=low,j=mid+1,k=low;while(i=mid&&j=high)if(su[i]=su[j])//此处为排序顺序的关键，用小于表示从小到大排序is2[k++]=su[i++];elseis2[k++]=su[j++];while(i=mid)is2[k++]=su[i++];while(j=high)is2[k++]=su[j++];for(i=low;i=high;i++)//写回原数组su[i]=is2[i];}voidg(inta,intb){if(ab){intmid=(a+b)/2;g(a,mid);g(mid+1,b);bin(a,mid,b);}}3.希尔排序⑴算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的“逐段分割”，而是将分隔某个“增量”的记录组成一个子序列。⑵程序实现及核心代码的注释：while(m){m/=2;if(m!=0){for(i=m;iN;i++)if(su[i]su[i-m]){temp=su[i];for(j=i-m;j=0&&(tempsu[j]);j-=m)su[j+m]=su[j];su[j+m]=temp;}}}4.冒泡排序⑴算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。⑵程序实现及核心代码的注释：for(i=0;iN;i++){flag=true;for(j=0;jN-1-i;j++){if(su[j]su[j+1]){temp=su[j];su[j]=su[j+1];su[j+1]=temp;flag=false;}}if(flag==true)break;}cout排序之后的数组为：endl;output();}intK;intfind(inti,intj){inttemp;boolflag=true;temp=su[i];while(ij){if(flag){while(temp=su[j]){j--;if(i=j)break;}if(i=j)break;su[i]=su[j];while(temp=su[i]){i++;if(i=j)break;}if(i=j)break;su[j]=su[i];flag=false;}else{while(temp=su[i]){i++;if(i=j)break;}su[j]=su[i];if(i=j)break;while(temp=su[j]){j--;if(i=j)break;}su[i]=su[j];flag=true;}}for(i=1;iN;i++){head=su[i];for(j=0;ji;j++){if(headsu[j]){for(k=i;kj;k--){su[k]=su[k-1];}su[j]=head;break;}}}for(i=1;iN;i++){head=su[i];for(j=0;ji;j++){if(headsu[j]){for(k=i;kj;k--){su[k]=su[k-1];}su[j]=head;break;}}}5.快速排序（1）任取待排序记录序列中的某个记录作为基准，按照该记录的关键字大小，将整个记录序列划分为左右两个子序列。左侧子序列中所有记录的关键字都小于或等于基准记录的关键字。右侧子序列中所有记录的关键字都大于基准记录的关键字。取序列第一个记录为枢轴记录，其关键字为Pivotkey；指针low指向序列第一个记录位置（low=1），指针high指向序列最后一个记录位置（High=SeqList.Len）(2)从high指向的记录开始，向前找到第一个关键字的值小于Pivotkey的记录，将其放到low指向的位置，low++(3)从low指向的记录开始，向后找到第一个关键字的值大于Pivotkey的记录，将其放到high指向的位置，high—重复2、3，直到low==high，将枢轴记录放在low（high）指向的位置。（2）程序实现及核心代码的注释：intfind(inti,intj){inttemp;boolflag=true;temp=su[i];while(ij){if(flag){while(temp=su[j]){j--;if(i=j)break;}if(i=j)break;su[i]=su[j];while(temp=su[i]){i++;if(i=j)break;}if(i=j)break;su[j]=su[i];flag=false;}else{while(temp=su[i]){i++;if(i=j)break;}su[j]=su[i];if(i=j)break;while(temp=su[j]){j--;if(i=j)break;}su[i]=su[j];flag=true;}}su[i]=temp;cout排完K++次顺序后的结果endl;output();returni;}voidqsort(intlow,inthigh){if(lowhigh){intmid=find(low,high);qsort(low,mid-1);qsort(mid+1,high);}}6.基数排序（1）算法的基本思想：基数排序是属于“分配式排序”，又称“桶子法”，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。最高位优先法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。（2）程序实现及核心代码的注释：for(i=0;iN;i++){if(maxsu[i])max=su[i];a[H(su[i])][b[H(su[i])]++]=su[i];}k=0;for(i=0;i10;i++){if(b[i]!=0){for(j=0;jb[i];j++){su[k++]=a[i][j];}}}cout第一躺排序之后的数组为：endl;output();///第二次if(max/10==0)return;for(i=0;i10;i++)b[i]=0;for(i=0;iN;i++){a[HH(su[i])][b[HH(su[i])]++]=su[i];}k=0;for(i=0;i10;i++){if(b[i]!=0){for(j=0;jb[i];j++){su[k++]=a[i][j];}}}cout第二躺排序之后的数组为：endl;output();///第三次if(max/100==0)return;for(i=0;i10;i++)b[i]=0;for(i=0;iN;i++){a[HHH(su[i])][b[HHH(su[i])]++]=su[i];}k=0;for(i=0;i10;i++){if(b[i]!=0){for(j=0;jb[i];j++){su[k++]=a[i][j];}}}7.折半排序⑴算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，这般插入排序的时间复杂度仍为O（n2）。⑵程序实现及核心代码的注释：for(i=1;iN;i++){temp=su[i];low=0;high=i-1;while(low=high){m=(low+high)/2;if(tempsu[m])high=m-1;elselow=m+1;}for(j=i;jhigh+1;j--)su[j]=su[j-1];su[high+1]=temp;}8.直接插入排序⑴算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。⑵程序实现及核心代码的注释：for(i=1;iN;i++){head=su[i];for(j=0;ji;j++){if(headsu[j]){for(k=i;kj;k--){su[k]=su[k-1];}su[j]=head;break;}}}【三】详细设计程序代码:#includeiostream#includecstdio#includecstdlib#includealgorithm#includecmath#defineH(X)(X%10)#defineHH(X)(X%100/10)#defineHHH(X)(X/100)usingnamespacestd;//intss[10000]={32,37,64,87,16,12,24,32};//将要排序的数组intss[10000]={372,209,53,942,547,234,645,468,7,83};//将要排序的数组intsu[10000];//将要排序的数组intN=10;//数组的长度voidinput()//数组的输入函数{cout请输入要排序的数组的长度N：;cinN;cout请输入需要排序的数组：endl;for(inti=0;iN;i+