资源描述：
《数据结构中的各种排序.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、A）需求分析：1、冒泡排序在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]2、选择排序在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。选择排序是不稳定的。算法复杂度O(n2)--[n的平方]3、插入排序直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]4、折半插入排序折
2、半插入排序是对插入排序的改进，主要通过二分查找，获得插入的位置折半插入是一种稳定的排序排序时间复杂度O(n^2)附加空间O(1)5、快速排序快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)6、希尔排序算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。7、堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组
3、成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。有最大堆和最少堆之分堆排序是不稳定的。算法时间复杂度O(nlog2n)。8、归并排序归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。归并排序是一种较稳定的排序时间复杂度为时间O(nlogn)9、基数排序基数排序的方式可以采用LSD（Leastsignificantdigital）或MSD（Mostsignificantdigital），LSD的排序方式由键值的最右边开始，而MSD则相反
4、，由键值的最左边开始。基数排序是一种不稳定的排序，时间复杂度为：O(d(n+radix))B）概要设计：voidinsertsort(int*a);//插入排序函数voidBinsertsort(int*a);//折半插入排序函数voidbubble_sort(int*a);//冒泡排序voidquick_sort(int*a,intlow,inthigh);//快速排序intone_quick_sort(int*a,intlow,inthigh);//一趟快速排序voidselect_sort(int*a);//直接
5、选择排序voidmerge_sort(int*a,intlow,inthigh);//归并排序voidmsort(int*a,intlow,inthigh,intmid);//归并排序调用函数voidhead_sort(int*a);//堆排序函数voidhead_adgust(int*a,intlow,inthigh);//堆排序调用函数intmax_select_sort(int*a,intt);//选择最大数voidshell_insert(int*a,intdk);//希尔排序调用函数voidshell_sor
6、t(int*a);//希尔排序函数voiddadix_sort(int*a);//技术排序函数intcmp1(inta,intb);//sort()函数里面的比较函数intcmp2(inta,intb);//sort()函数里面的比较函数voidrand_sort(int*a);//随机产生函数voiddisplay(int*a);//打印数组A）详细设计：//12.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include
7、"stdlib.h"#include"time.h"#include#includeusingnamespacestd;inta[15];//排序数组intlen=15;//数组长度voidinsertsort(int*a);//插入排序函数voidBinsertsort(int*a);//折半插入排序函数voidbubble_sort(int*a);//冒泡排序voidquick_sort(int*a,intlow,inthigh);//快速排序intone_quick_so
8、rt(int*a,intlow,inthigh);//一趟快速排序voidselect_sort(int*a);//直接选择排序voidmerge_sort(int*a,intlow,inthigh);//归并排序voidmsort(int*a,intlow,inthigh,intmid);//归并排序调用函数voidhead_s
