还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
需求分析:
1、冒泡排序A在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数挨次进行比较和调整,让较大的数往下沉,较小的往上冒冒泡排序是稳定的算法时间复杂度0n2—[n的平方]
2、选择排序在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数之中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止选择排序是不稳定的算法复杂度0n2—[n的平方]
3、插入排序直接插入排序是稳定的算法时间复杂度0n2—[n的平方]
4、折半插入排序折半插入排序是对插入排序的改进,主要通过二分查找,获得插入的位置折半插入是一种稳定的排序排序时间复杂度0rT2附加空间
015、快速排序快速排序是不稳定的最理想情况算法时间复杂度0nlog2n,最坏0n
26、希尔排序算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序当增量减到1时,整个要排序的数被分成一组,排序完成
7、堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置所以堆排序有两个函数组成一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数有最大堆和至少堆之分堆排序是不稳定的算法时间复杂度0nlog2no
8、归并排序归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法Divide andConquer的一个非常典型的应用归并排序是一种较稳定的排序时间复杂度为时间Onlogn
9、基数排序基数排序的方式可以采用LSD Leastsignificant digital或者MSDMost significantdigital,LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始基数排序是一种不稳定的排序,时间复杂度为0dn+radix概要设计void insertsort int*a;〃插入排序函数Bvoid Binsertsort int*a;〃折半插入排序函数void bubble_sort int*a;〃冒泡排序if a[i]a[i_dk]{temp=a[i];for intj=i-dk;j=0tempa[j];j=j-dka[j+dk]=a[j];}a[j+dk]=temp;void shell_sort int*a//希尔排序{-int dks
[3]={4,3,1};//定义步长for int i=0;i3;++i shell_inserta,dks[i];}void dadix_sort int*a//基数排序sort a,a+15,cmp2;sorta,a+15,cmpl;}int cmplint a,int b//个位数比较函数if a/10b/10return1;return0;int cmp2int a,int b//十位数比较函数if a%10b%10return1;return0;void rand_sort int*a//产生随机数据函数for inti=0;ilen;++ia[i]=rand%100;}}void displayint*a〃打印排序好之后的函数for inti=0;ilen;++i{coutendl;}调试分析;
1、测试数据测试数据主要通过函数rang_sort,自动生成一系列数据D
2、各个模块分别测试,1-9分别测试了9种排序课程总结通过数据结构大型作业,算法主要在于思想,以及思路的严谨性实战型很强E通过练习,编程能力以及算法思想大大提高void quicksort int*a,int low,int high;〃快速排序int one_quick_sort int*a,int low,int high;〃一趟快速排序void select_sort int*a;//直接选择排序void merge_sort int*a,int low,int high;归/并排序void msort int*a,int low,int high,int mid;//归并排序调用函数void head_sort int*a;〃堆排序函数void head_adgustint*a,int low,int high;//堆排序调用函数int max_select_sort int int t;选/择最大数void shell_insertint*a,int dk;//希尔排序调用函数void shell_sort int*a;〃希尔排序函数void dadix_sort int*a;〃技术排序函数int cmplint a,int b;//sort函数里面的比较函数int cmp2int a,int b;//sort函数里面的比较函数void rand_sort int*a;/随机产生函数void displayint*a;/打/印数组详细设计//
12.cpp:Defines theentry pointfor theconsole application.C//int a
[15];〃排序数组int len=15〃数组长度#include iostream^include algorithmusing namespacestd;〃插入排序函数void insertsortint*a;void Binsertsort int*a;〃折半插入排序函数void bubble_sort int*a;〃冒泡排序void quick sort int*a,intint low,int high;〃快速排序one_quick_sortint*a,序int low,int high;〃一趟快速排void select_sort int*a;〃直接选择排序void merge_sort int*a,int low,int high;〃归并排序void msort int*a,int low,int high,int mid;力4并排序调用函数void headsort int*a;//堆排序函数void head_adgust int*a,int low,int high;//堆排序调用函数int max_select_sortint*a,int t;〃选择最大数void shellinsert int*a,int dk;//希尔排序调用函数void shell_sortint*a;//希尔排序函数//技术排序函数void dadix_sortint*a;int cmplint a,int b;〃sort函数里面的比较函数//sort函数里面的比int cmp2int a,int b;较函数〃随机产生函数void rand_sortint*a;〃打印数组void displayint*a;int mainintargc,char*argv[]srandunsignedtimeNULL;〃产生随即种子插入排序随机产生数据rand_sorta;displaya;排序之后的数据insertsorta;displaya;coutendl;折半插入排序随机产生数据rand_sorta;displaya;排序之后的数据Binsertsorta;displaya;coutendl;冒泡排序随机产生数据rand_sorta;displaya;排序之后的数据bubble_sort a;displaya;coutendl;快速排序随机产生数据rand_sorta;displaya;排序之后的数据quick_sorta,0,len-1;displaya;coutendl;选择排序随机产生数据rand sort a;displaya;排序之后的函数select_sorta;display a;coutendl;归并排序随机产生数据rand sorta;displaya;排序之后的数据merge_sorta,0,len;displaya;coutendl;堆排序随机产生数据rand sorta;displaya;排序之后的数据head_sorta;displaya;coutendl;希尔排序随机产生数据rand_sorta;displaya;排序之后的数据shell_sorta;displaya;coutendl;基数排序随机产生数据rand_sorta;displaya;排序之后的数据dadix_sorta;displaya;coutendl;return0;void insertsortint*a int temp;for inti=1;ilen;++i if a[i-1]a[i]temp=a[i];a[i]=a[i-l];for intj=i-1;tempa[j];--ja[j+l]=a[j];a[j+l]=temp;void Binsertsortint*a〃折半插入排序函数int temp;int low,high,mid;for inti=1;ilen;++i tempa[i];二low=0;high=i-1;while low=highmid=low+high/2;iftempa[mid]high=mid-1elselow=mid+1;for intj=i-1;jhigh;—j{a[j+l]=a[j];a[j+l]=temp;void bubble_sortint*a〃冒泡排序{int temp;for inti=1;ilen;++i{for intj=0;jlen-i;++j|if a[j]a[j+l]temp=a[j];a[j]=a[j+l];a[j+l]=temp;}void quicksortint*a,int low,int high〃快速排序{―if lowhigh int mid;mid=one_quick_sorta,low,high;quick_sorta,low,mid-1;quick_sorta,mid+1,high;〃一趟快速排序int onequicksortint*a,int low,int high{~~int temp;while lowhigh whilea[low]=a[high]lowhigh—high;temp=a[low];a[low]=a[high];a[high]=temp;while a[low]=a[high]low high{++low;temp=a[high];a[high]=a[low];a[low]=temp;}return low;void select_sortint*a〃直接选择排序{-int n,temp;int t=len-1;for intj=len-1;j=0;--j,--t n=max_select_sorta,t;if j!=n temp=a[n];a[n]=a[j];a[j]=temp;int max_select_sortint*a,intt〃选择最大数{int temp=a
[0];int flag=0;for inti=0;i=t;++i if a[i]temp temp=a[i];flag=i;return flag;void merge_sortint*a,int low,int high〃归并排序{―if lowhighint mid=1ow+high/2;merge_sorta,low,mid;merge_sorta,mid+1,high;msort a,low,high,mid;〃归并排序调用函void msortint*a,int low,int high,intmid数{inti=low,j=mid+1,*b,r=0;b=new int[high-1ow];whilei=midj=high{if a[i]=a[j]b[r]=a[i];++r;++i;}else{b[r]=a[j];++j;++r;}while i〈=mid b[r]=a[i];++r;++i;}while j=highb[r]=a[j];++j;++r;for i=low,j=0;i=high;++i,++j a[i]=b[j];void head_sortint*a〃推排序-int temp;for inti=len/2-1;i=0;i一一headadgusta,i,len;fori=len-1;i=0;i一一temp=a
[0];a
[0]=a[i];a[i]=temp;head_adgustavoid headadgustint*a,intlow,int high〃调整的最大堆int temp;for inti=2*low+1;ihigh i=i*2+1ifa[i]a[i+l]++i;ifa[low]a[i]{break;else{temp=a[low];a[low]=a[i];a[i]=temp;low二i;void shell_insertint*a,int dk希尔插入函数{int temp;for inti=dk;ilen;++i。