数据结构中的各种排序.docx
《数据结构中的各种排序.docx》由会员分享，可在线阅读，更多相关《数据结构中的各种排序.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构中的各种排序
A）需求分析：
1、冒泡排序
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上
而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较
小的往上冒。
冒泡排序是稳定的。
算法时间复杂度O（n2）--[n的平方]
2、选择排序
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环
到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。
算法复杂度O（n2）--[n的平方]
3、插入排序
直接插入排序是稳定的。
算法时间复杂度O（n2）--[n的平方]
4、折半插入排序
折半插入排序是对插入排序的改进，主要通过二分查找，获得插入的位置
折半插入是一种稳定的排序排序时间复杂度O（n^2）附加空间O
（1）
5、快速排序
快速排序是不稳定的。
最理想情况算法时间复杂度O（nlog2n），最坏O（n2）
6、希尔排序
算法先将要排序的一组数按某个增量d分成若干组，每组中
记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序。
当增量减到1时，整个要排序的数被分成
一组，排序完成。
7、堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素
交换位置。
所以堆排序有两个函数组成。
一是建堆的渗透函数，二是反复调用渗透函数
实现排序的函数。
有最大堆和最少堆之分
堆排序是不稳定的。
算法时间复杂度O（nlog2n）。
8、归并排序
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（DivideandConquer）的一个非常典型的应用。
归并排序是一种较稳定的排序时间复杂度为时间O（nlogn）
9、基数排序
基数排序的方式可以采用LSD（Leastsignificantdigital）或MSD（Mostsignificantdigital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
基数排序是一种不稳定的排序，时间复杂度为：
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）;//直接选择排序
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_sort（int*a）;//希尔排序函数
voiddadix_sort（int*a）;//技术排序函数
intcmp1（inta,intb）;//sort（）函数里面的比较函数
intcmp2（inta,intb）;//sort（）函数里面的比较函数
voidrand_sort（int*a）;//随机产生函数
voiddisplay（int*a）;//打印数组
C）详细设计：
//12.cpp:
Definestheentrypointfortheconsoleapplication.
//
#include"stdafx.h"
#include"stdlib.h"
#include"time.h"
#include
#include
usingnamespacestd;
inta[15];//排序数组
intlen=15;//数组长度
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）;//直接选择排序
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_sort（int*a）;//希尔排序函数
voiddadix_sort（int*a）;//技术排序函数
intcmp1（inta,intb）;//sort（）函数里面的比较函数
intcmp2（inta,intb）;//sort（）函数里面的比较函数
voidrand_sort（int*a）;//随机产生函数
voiddisplay（int*a）;//打印数组
intmain（intargc,char*argv[]）
{
srand（unsigned（time（NULL）））;//产生随即种子
cout<<"*******1.插入排序*********"<cout<<"随机产生数据:
"<rand_sort（a）;
display（a）;
cout<<"排序之后的数据"<insertsort（a）;
display（a）;
cout<cout<<"*******2.折半插入排序*********"<cout<<"随机产生数据:
"<rand_sort（a）;
display（a）;
cout<<"排序之后的数据"<Binsertsort（a）;
display（a）;
cout<cout<<"*******3.冒泡排序*********"<cout<<"随机产生数据:
"<rand_sort（a）;
display（a）;
cout<<"排序之后的数据"<bubble_sort（a）;
display（a）;
cout<cout<<"*******4.快速排序*********"<cout<<"随机产生数据:
"<rand_sort（a）;
display（a）;
cout<<"排序之后的数据"<quick_sort（a,0,len-1）;
display（a）;
cout<cout<<"*******5.选择排序*********"<cout<<"随机产生数据:
"<rand_sort（a）;
display（a）;
cout<<"排序之后的函数"<select_sort（a）;
display（a）;
cout<cout<<"*******6.归并排序*********"<cout<<"随机产生数据:
"<rand_sort（a）;
display（a）;
cout<<"排序之后的数据"<merge_sort（a,0,len）;
display（a）;
cout<cout<<"*******7.堆排序*********"<cout<<"随机产生数据:
"<rand_sort（a）;
display（a）;
cout<<"排序之后的数据"<head_sort（a）;
display（a）;
cout<cout<<"*******8.希尔排序*********"<cout<<"随机产生数据:
"<rand_sort（a）;
display（a）;
cout<<"排序之后的数据"<shell_sort（a）;
display（a）;
cout<cout<<"*******9.基数排序*********"<cout<<"随机产生数据:
"<rand_sort（a）;
display（a）;
cout<<"排序之后的数据"<dadix_sort（a）;
display（a）;
cout<return0;
}
voidinsertsort（int*a）
{
inttemp;
for（inti=1;i{
if（a[i-1]>a[i]）
{
temp=a[i];
a[i]=a[i-1];
for（intj=i-1;temp{
a[j+1]=a[j];
}
a[j+1]=temp;
}
}
}
voidBinsertsort（int*a）//折半插入排序函数
{
inttemp;
intlow,high,mid;
for（inti=1;i{
temp=a[i];
low=0;
high=i-1;
while（low<=high）
{
mid=（low+high）/2;
if（temp{
high=mid-1;
}
else
low=mid+1;
}
for（intj=i-1;j>high;--j）
{
a[j+1]=a[j];
}
a[j+1]=temp;
}
}
voidbubble_sort（int*a）//冒泡排序
{
inttemp;
for（inti=1;i{
for（intj=0;j{
if（a[j]>a[j+1]）
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
voidquick_sort（int*a,intlow,inthigh）//快速排序
{
if（low{
intmid;
mid=one_quick_sort（a,low,high）;
quick_sort（a,low,mid-1）;
quick_sort（a,mid+1,high）;
}
}
intone_quick_sort（int*a,intlow,inthigh）//一趟快速排序
{
inttemp;
while（low{
while（a[low]<=a[high]&&low{
--high;
}
temp=a[low];
a[low]=a[high];
a[high]=temp;
while（a[low]<=a[high]&&low{
++low;
}
temp=a[high];
a[high]=a[low];
a[low]=temp;
}
returnlow;
}
voidselect_sort（int*a）//直接选择排序
{
intn,temp;
intt=len-1;
for（intj=len-1;j>=0;--j,--t）
{
n=max_select_sort（a,t）;
if（j!
=n）
{
temp=a[n];
a[n]=a[j];
a[j]=temp;
}
}
}
intmax_select_sort（int*a,intt）//选择最大数
{
inttemp=a[0];
intflag=0;
for（inti=0;i<=t;++i）
{
if（a[i]>temp）
{
temp=a[i];
flag=i;
}
}
returnflag;
}
voidmerge_sort（int*a,intlow,inthigh）//归并排序
{
if（low{
intmid=（low+high）/2;
merge_sort（a,low,mid）;
merge_sort（a,mid+1,high）;
msort（a,low,high,mid）;
}
}
voidmsort（int*a,intlow,inthigh,intmid）//归并排序调用函数
{
inti=low,j=mid+1,*b,r=0;
b=newint[high-low];
while（i<=mid&&j<=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<=high）
{
b[r]=a[j];
++j;
++r;
}
for（i=low,j=0;i<=high;++i,++j）
{
a[i]=b[j];
}
}
voidhead_sort（int*a）//推排序
{
inttemp;
for（inti=len/2-1;i>=0;--i）
{
head_adgust（a,i,len）;
}
for（i=len-1;i>=0;--i）
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
head_adgust（a,0,i-1）;
}
}
voidhead_adgust（int*a,intlow,inthigh）//调整的最大堆
{
inttemp;
for（inti=2*low+1;i{
if（a[i]{
++i;
}
if（a[low]>a[i]）
{
break;
}
else
{
temp=a[low];
a[low]=a[i];
a[i]=temp;
low=i;
}
}
}
voidshell_insert（int*a,intdk）希尔插入函数
{
inttemp;
for（inti=dk;i{
if（a[i]{
temp=a[i];
for（intj=i-dk;j>=0&&temp{
a[j+dk]=a[j];
}
a[j+dk]=temp;
}
}
}
voidshell_sort（int*a）//希尔排序
{
intdks[3]={4,3,1};//定义步长
for（inti=0;i<3;++i）
{
shell_insert（a,dks[i]）;
}
}
voiddadix_sort（int*a）//基数排序
{
sort（a,a+15,cmp2）;
sort（a,a+15,cmp1）;
}
intcmp1（inta,intb）//个位数比较函数
{
if（a/10
{
return1;
}
return0;
}
intcmp2（inta,intb）//十位数比较函数
{
if（a%10{
return1;
}
return0;
}
voidrand_sort（int*a）//产生随机数据函数
{
for（inti=0;i{
a[i]=rand（）%100;
}
}
voiddisplay（int*a）//打印排序好之后的函数
{
for（inti=0;i{
cout<}
cout<}
D）调试分析;
1、测试数据：
测试数据主要通过函数rang_sort（），自动生成一系列数据
2、各个模块分别测试，1-9分别测试了9种排序
E）课程总结：
通过数据结构大型作业，算法主要在于思想，以及思路的严谨性。
实战型很强。
通过练习，编程能力以及算法思想大大提高。
升级会员 