各种排序实验报告.doc

《各种排序实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【一】需求分析课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。【二】概要设计1.堆排序⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完

2、全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(NlogN)。⑵程序实现及核心代码的注释：for(j=2*i+1;j<=m;j=j*2+1){if(j=su[j])break;su[i]=su[j];i=j;}su[i]=temp;}voiddpx()//堆排序{inti,temp;cout<<"排序之前的数组为："<=0;i--){head

3、(i,N);}for(i=N-1;i>0;i--){temp=su[i];su[i]=su[0];su[0]=temp;head(0,i-1);}cout<<"排序之后的数组为："<

4、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(a

5、);bin(a,mid,b);}}3.希尔排序⑴算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的“逐段分割”，而是将分隔某个“增量”的记录组成一个子序列。⑵程序实现及核心代码的注释：while(m){m/=2;if(m!=0){for(i=m;i=0&&(temp

6、su[j+m]=temp;}}}4.冒泡排序⑴算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。⑵程序实现及核心代码的注释：for(i=0;i

7、+){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<<"排序之后的数组为："<=j)break;}if(i>=j)break;su[i]=su[j

8、];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>