数据结构中的各种排序

A)需求分析:

1、冒泡排序

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上

而下对相邻的两个数挨次进行比较和调整，让较大的数往下沉，较

小的往上冒。

冒泡排序是稳定的。算法时间复杂度0(n2)—[n的平方]

2、选择排序

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；

然后在剩下的数之中再找最小的与第二个位置的数交换，如此循环

到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。算法复杂度0(n2)—[n的平方]

3、插入排序

直接插入排序是稳定的。算法时间复杂度0(n2)—[n的平方]

4、折半插入排序

折半插入排序是对插入排序的改进，主要通过二分查找，获得插入的位置

折半插入是一种稳定的排序排序时间复杂度0(n~2)附加空间0(1)

5、快速排序

快速排序是不稳定的。最理想情况算法时间复杂度0(nlog2n),最坏0(n2)

6、希尔排序

算法先将要排序的一组数按某个增量d分成若干组，每组中

记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量

对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成

一组，排序完成。

7、堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素

交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调

用渗透函数

实现排序的函数。有最大堆和至少堆之分

堆排序是不稳定的。算法时间复杂度0(nlog2n)»

8、归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法

(DivideandConquer)的一个非常典型的应用。

归并排序是一种较稳定的排序时间复杂度为时间O(nlogn)

9、基数排序

基数排序的方式可以采用LSD(Leastsignificantdigital)或者MSD

(Mostsignificantdigital),LSD的排序方式由键值的最右边开始,而

MSD则相反，由键值的最左边开始。

基数排序是一种不稳定的排序，时间复杂度为：0(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);〃技术排序函数

intcmpl(inta,intb);〃sort()函数里面的比较函数

intcmp2(inta,intb);〃sort()函数里面的比较函数

voidrand_sort(int*a);/随机产生函数

voiddisplay(int*a);/打/印数组

c)详细设计：

//12.cpp:Definestheentrypointfortheconsoleapplication.

//

Sinclude<iostream>

Sinclude<algorithm>

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,int1w,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);〃技术排序函数

intcmpl(inta,intb);〃sort()函数里面的比

较函数

intcmp2(inta,intb);〃sort()函数里面的比

较函数

voidrand_sort(int*a);〃随机产生函数

voiddisplay(int*a);〃打印数组

intmain(intargc,char*argv[])

{

srand(unsigned(time(NULL)));〃产生随即种子

插入排序

随机产生数据

rand_sort(a);

display(a);

排序之后的数据

insertsort(a);

display(a);

cout<<endl;

折半插入排序

随机产生数据

rand_sort(a);

display(a);

排序之后的数据

Binsertsort(a);

display(a);

cout<<endl;

冒泡排序

随机产生数据

rand_sort(a);

display(a);

排序之后的数据

bubble_sort(a);

display(a);

cout<<endl;

快速排序

随机产生数据

rand_sort(a);

display(a);

排序之后的数据

quick_sort(a,0,len-l);

display(a);

cout«endl;

选择排序

随机产生数据

rand_sort(a);

display(a);

排序之后的函数

select_sort(a);

display(a);

cout«endl;

归并排序

随机产生数据

rand_sort(a);

display(a);

排序之后的数据

merge_sort(a,0,len);

display(a);

cout«endl;

堆排序

随机产生数据

rand_sort(a);

display(a);

排序之后的数据

head_sort(a);

display(a);

cout«endl;

希尔排序

随机产生数据

rand_sort(a);

display(a);

排序之后的数据

shell_sort(a);

display(a);

cout«endl;

基数排序

随机产生数据

rand_sort(a);

display(a);

排序之后的数据

dadix_sort(a);

display(a);

cout«endl;

return0;

)

voidinsertsort(int*a)

(

inttemp;

for(inti=1;i<len;++i)

•u\ari

If(a1zL

temp-a

aaLI1

rintj=itempa-j

f{o

-ji

a-+i-

-j+T

aJ叩

-te

voidBinsertsort(int*a)〃折半插入排序函数

(

inttemp;

intlow,high,mid;

for(inti=1;i<len;++i)

(

temp=a[i];

low=0;

high=i-1;

while(low<=high)

(

mid=(low+high)/2;

if(temp<a[mid])

high=mid-1;

else

low=mid+1;

)

for(intj=i-1;j>high;—j)

(

a[j+l]=a[j];

)

a[j+l]=temp;

voidbubble_sort(int*a)〃冒泡排序

(

inttemp;

for(inti=1;i<len;++i)

(

for(intj=0;j<len-i;++j)

(

if(a[j]>a[j+l])

(

temp=a[j];

a[j]=a[j+l];

a[j+l]=temp;

)

)

)

)

voidquick_sort(int*a,intlow,inthigh)〃快速排序

(

if(low<high)

(

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<high)

while(a[lowj<=a[high]&&low<high)

—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;

)

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(intintt)〃选择最大数

(

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<high)

(

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<high;i=i*2+1)

(

if(a[i]<a[i+l])

(

++i；

)

if(a[low]>a[i])

(

break;

}

else

(

temp=a[low];

atlow]=a[i];

a[i]=temp;

low=i;

voidshell_insert(int*a,intdk)希尔插入函数

inttemp;

for(inti=dk;i<len;++i)

if(a[i]<a[i_dk])

temp=a[i];

for(intj=i-dk;j>=0&&temp<a[j]j=j-dk)

(

a[j+dk]=a[j];