數(shù)據(jù)結(jié)構(gòu)中的各種排序

A)需求分析:

1、冒泡排序

在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上

而下對(duì)相鄰的兩個(gè)數(shù)挨次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較

小的往上冒。

冒泡排序是穩(wěn)定的。算法時(shí)間復(fù)雜度0(n2)—[n的平方]

2、選擇排序

在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；

然后在剩下的數(shù)之中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)

到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。

選擇排序是不穩(wěn)定的。算法復(fù)雜度0(n2)—[n的平方]

3、插入排序

直接插入排序是穩(wěn)定的。算法時(shí)間復(fù)雜度0(n2)—[n的平方]

4、折半插入排序

折半插入排序是對(duì)插入排序的改進(jìn)，主要通過(guò)二分查找，獲得插入的位置

折半插入是一種穩(wěn)定的排序排序時(shí)間復(fù)雜度0(n~2)附加空間0(1)

5、快速排序

快速排序是不穩(wěn)定的。最理想情況算法時(shí)間復(fù)雜度0(nlog2n),最壞0(n2)

6、希爾排序

算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中

記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量

對(duì)它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成

一組，排序完成。

7、堆排序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆的最后一個(gè)元素

交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)

用滲透函數(shù)

實(shí)現(xiàn)排序的函數(shù)。有最大堆和至少堆之分

堆排序是不穩(wěn)定的。算法時(shí)間復(fù)雜度0(nlog2n)?

8、歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法

(DivideandConquer)的一個(gè)非常典型的應(yīng)用。

歸并排序是一種較穩(wěn)定的排序時(shí)間復(fù)雜度為時(shí)間O(nlogn)

9、基數(shù)排序

基數(shù)排序的方式可以采用LSD(Leastsignificantdigital)或者M(jìn)SD

(Mostsignificantdigital),LSD的排序方式由鍵值的最右邊開(kāi)始,而

MSD則相反，由鍵值的最左邊開(kāi)始。

基數(shù)排序是一種不穩(wěn)定的排序，時(shí)間復(fù)雜度為：0(d(n+radix))

B)概要設(shè)計(jì)：

voidinsertsort(int*a);〃插入排序函數(shù)

voidBinsertsort(int*a);〃折半插入排序函數(shù)

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);勵(lì)/并排序

voidmsort(int*a,intlow,inthigh,intmid);〃歸并排序調(diào)用

函數(shù)

voidhead_sort(int*a);〃堆排序函數(shù)

voidhead_adgust(int*a,intlow,inthigh);//堆排序調(diào)用

函數(shù)

intmax_select_sort(int*a,intt);選/擇最大數(shù)

voidshell_insert(int*a,intdk);〃希爾排序調(diào)用函數(shù)

voidshell_sort(int*a);〃希爾排序函數(shù)

voiddadix_sort(int*a);〃技術(shù)排序函數(shù)

intcmpl(inta,intb);〃sort()函數(shù)里面的比較函數(shù)

intcmp2(inta,intb);〃sort()函數(shù)里面的比較函數(shù)

voidrand_sort(int*a);/隨機(jī)產(chǎn)生函數(shù)

voiddisplay(int*a);/打/印數(shù)組

c)詳細(xì)設(shè)計(jì)：

//12.cpp:Definestheentrypointfortheconsoleapplication.

//

Sinclude<iostream>

Sinclude<algorithm>

usingnamespacestd;

inta[15];〃排序數(shù)組

intlen=15;〃數(shù)組長(zhǎng)度

voidinsertsort(int*a);〃插入排序函數(shù)

voidBinsertsort(int*a);〃折半插入排序函數(shù)

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);力幺并排序調(diào)用函

數(shù)

voidhead_sort(int*a);〃堆排序函數(shù)

voidhead_adgust(int*a,intlow,inthigh);〃堆排序調(diào)

用函數(shù)

intmax_select_sort(int*a,intt)〃選擇最大數(shù)

voidshell_insert(int*a,intdk);〃希爾排序調(diào)用函

數(shù)

voidshell_sort(int*a);〃希爾排序函數(shù)

voiddadix_sort(int*a);〃技術(shù)排序函數(shù)

intcmpl(inta,intb);〃sort()函數(shù)里面的比

較函數(shù)

intcmp2(inta,intb);〃sort()函數(shù)里面的比

較函數(shù)

voidrand_sort(int*a);〃隨機(jī)產(chǎn)生函數(shù)

voiddisplay(int*a);〃打印數(shù)組

intmain(intargc,char*argv[])

{

srand(unsigned(time(NULL)));〃產(chǎn)生隨即種子

插入排序

隨機(jī)產(chǎn)生數(shù)據(jù)

rand_sort(a);

display(a);

排序之后的數(shù)據(jù)

insertsort(a);

display(a);

cout<<endl;

折半插入排序

隨機(jī)產(chǎn)生數(shù)據(jù)

rand_sort(a);

display(a);

排序之后的數(shù)據(jù)

Binsertsort(a);

display(a);

cout<<endl;

冒泡排序

隨機(jī)產(chǎn)生數(shù)據(jù)

rand_sort(a);

display(a);

排序之后的數(shù)據(jù)

bubble_sort(a);

display(a);

cout<<endl;

快速排序

隨機(jī)產(chǎn)生數(shù)據(jù)

rand_sort(a);

display(a);

排序之后的數(shù)據(jù)

quick_sort(a,0,len-l);

display(a);

cout?endl;

選擇排序

隨機(jī)產(chǎn)生數(shù)據(jù)

rand_sort(a);

display(a);

排序之后的函數(shù)

select_sort(a);

display(a);

cout?endl;

歸并排序

隨機(jī)產(chǎn)生數(shù)據(jù)

rand_sort(a);

display(a);

排序之后的數(shù)據(jù)

merge_sort(a,0,len);

display(a);

cout?endl;

堆排序

隨機(jī)產(chǎn)生數(shù)據(jù)

rand_sort(a);

display(a);

排序之后的數(shù)據(jù)

head_sort(a);

display(a);

cout?endl;

希爾排序

隨機(jī)產(chǎn)生數(shù)據(jù)

rand_sort(a);

display(a);

排序之后的數(shù)據(jù)

shell_sort(a);

display(a);

cout?endl;

基數(shù)排序

隨機(jī)產(chǎn)生數(shù)據(jù)

rand_sort(a);

display(a);

排序之后的數(shù)據(jù)

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)〃折半插入排序函數(shù)

(

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)〃選擇最大數(shù)

(

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)〃歸并排序調(diào)用函

數(shù)

(

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)〃調(diào)整的最大堆

(

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)希爾插入函數(shù)

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