【一】需求分析课程题目是排序算法的实现，课程设计一共要设计八种排序算法。

这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。

为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。

【二】概要设计1.堆排序⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。

将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。

算法的平均时间复杂度为O(N log N)。

⑵程序实现及核心代码的注释：for(j=2*i+1; j<=m; j=j*2+1){if(j<m-1&&(su[j]<su[j+1]))j++;if(temp>=su[j])break;su[i]=su[j];i=j;}su[i]=temp;}void dpx() //堆排序{int i,temp;cout<<"排序之前的数组为："<<endl;output();for(i=N/2-1; i>=0; i--){head(i,N);}for(i=N-1; i>0; i--){temp=su[i];su[i]=su[0];su[0]=temp;head(0,i-1);}cout<<"排序之后的数组为："<<endl;output();}2.归并排序⑴算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。

⑵程序实现及核心代码的注释：int is2[1000];void bin(int low,int mid,int high){int i=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];}void g(int a,int b){if(a<b){int mid=(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; i<N; i++)if(su[i]< su[i-m]){temp=su[i];for(j=i-m; j>=0&&(temp<su[j]); j-=m)su[j+m]=su[j];su[j+m]=temp;}}}4.冒泡排序⑴算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。

⑵程序实现及核心代码的注释：for(i=0; i<N; i++){flag=true;for(j=0; j<N-1-i; j++){if(su[j]>su[j+1]){temp=su[j];su[j]=su[j+1];su[j+1]=temp;flag=false;}}break;}cout<<"排序之后的数组为："<<endl;output();}int K;int find(int i,int j){int temp;bool flag=true;temp=su[i];while(i<j){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];}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; i<N; i++){head=su[i];for(j=0; j<i; j++){if(head<su[j]){for(k=i; k>j; k--){su[k]=su[k-1];}su[j]=head;break;}}}for(i=1; i<N; i++){head=su[i];for(j=0; j<i; j++){if(head<su[j]){for(k=i; k>j; 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）程序实现及核心代码的注释：int find(int i,int j){int temp;bool flag=true;temp=su[i];while(i<j){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();return i;}void qsort(int low,int high){if(low<high){int mid=find(low,high);qsort(low,mid-1);qsort(mid+1,high);}}6.基数排序（1）算法的基本思想：基数排序是属于“分配式排序”，又称“桶子法”，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

最高位优先法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。

再将各组连接起来，便得到一个有序序列。

（2）程序实现及核心代码的注释：for(i=0; i<N; i++){if(max<su[i])max=su[i];a[H(su[i])][b[H(su[i])]++]=su[i];}k=0;for(i=0; i<10; i++){if(b[i]!=0){for(j=0; j<b[i]; j++){su[k++]=a[i][j];}}}cout<<"第一躺排序之后的数组为："<<endl;output();///第二次if(max/10==0)return ;for(i=0; i<10; i++)b[i]=0;for(i=0; i<N; i++){a[HH(su[i])][b[HH(su[i])]++]=su[i];}k=0;for(i=0; i<10; i++){if(b[i]!=0){for(j=0; j<b[i]; j++){su[k++]=a[i][j];}}}cout<<"第二躺排序之后的数组为："<<endl;output();///第三次if(max/100==0)return ;for(i=0; i<10; i++)b[i]=0;for(i=0; i<N; i++){a[HHH(su[i])][b[HHH(su[i])]++]=su[i];}k=0;for(i=0; i<10; i++){if(b[i]!=0){for(j=0; j<b[i]; j++){su[k++]=a[i][j];}}}7.折半排序⑴算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。