排序算法(部編)課件

排序算法專題主要內(nèi)容:一、選擇排序二、插入排序三、冒泡排序四、合并排序五、快速排序七、計(jì)數(shù)排序六、桶排序其它的排序：堆排序，留在后面介紹排序就是把一組無(wú)序的關(guān)鍵字，通過(guò)算法變成一組有序的關(guān)鍵字。一、選擇排序算法思想：對(duì)于一組關(guān)鍵字{K1,K2,…,Kn},首先從K1,K2,…,Kn中選擇最小值,假如它是Ki,則將Ki與K1對(duì)換,然后從K2,K3,…,Kn中選擇最小值Ki,再將Ki與K2對(duì)換.如此進(jìn)行選擇和調(diào)換n-2趟,第(n-1)趟,從Kn-1、Kn中選擇最小值Ki將Ki與Kn-1對(duì)換,最后剩下的就是該序列中的最大值,一個(gè)由小到大的有序序列就這樣形成.即:在要排序的一組數(shù)中,選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換,然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換,如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。舉例：對(duì)下面一組關(guān)鍵字，要求按照從大到小排序

a[1]a[2]a[3]a[4]a[5]a[6]a[7]13287499123748從A[1]到a[7]找最大的數(shù)9812347從A[2]到a[7]找最大的數(shù)9

871234從A[3]到a[7]找最大的數(shù)9

8

74123從A[4]到a[7]找最大的數(shù)9

8

7

4312從A[5]到a[7]找最大的數(shù)9

8

7

4

321從A[6]到a[7]找最大的數(shù)9

8

7

4

3

21排序結(jié)束for(i=1;i<n;i++){for(j=i+1;j<=n;j++)if(a[j]>a[i]){a[0]=a[i];a[i]=a[j];a[j]=a[0];}}核心代碼該算法缺點(diǎn)就是元素交換的次數(shù)太多。改進(jìn)算法：

for(i=1;i<=n;i++){

k=i;for(j=i+1;j<=n;j++)if(a[k]<a[j])k=j;if(k!=i){a[0]=a[i];a[i]=a[k];a[k]=a[0];}}二、插入排序算法思想：設(shè)有一組關(guān)鍵字{K1,K2,…,Kn},排序開(kāi)始就認(rèn)為K1是一個(gè)有序序列,讓K2插入上述表長(zhǎng)為1的有序序列,使之成為一個(gè)表長(zhǎng)為2的有序序列,然后讓K3插入上述表長(zhǎng)為2的有序序列,使之成為一個(gè)表長(zhǎng)為3的有序序列,依次類(lèi)推,最后讓Kn插入上述表長(zhǎng)為n-1的有序序列,得一個(gè)表長(zhǎng)為n的有序序列。第一趟:

[55]

22

44

11

33第二趟:

[22

55]

44

11

33第三趟:

[22

44

55]

11

33第四趟:

[11

22

44

55]

33第五趟:[1122

33

44

55]解決問(wèn)題關(guān)鍵是找插入的位置。需要寫(xiě)一個(gè)函數(shù)find(x,y),來(lái)確定第y個(gè)插入元素x在已經(jīng)有序的序列中的位置。intfind(intx,inty)//該函數(shù)就是確定第y個(gè)元素x，在有序序列中的位置。{intk=y;//函數(shù)值通過(guò)K來(lái)返回，K初始化為y，設(shè)插入在y位置。for(inti=1;i<=y;i++)//從第1個(gè)元素開(kāi)始和X比較找到第一個(gè)比X小的數(shù)if(a[i]>=x){k=i;break;}//記下第一個(gè)比X小的數(shù)的位置，退出循環(huán)returnk;//此時(shí)的k即為X要插入的位置。}程序核心代碼：for(inti=1;i<=n;i++){intk;cin>>m;k=find(m,i);for(intj=i;j>=k;j--)a[j+1]=a[j];a[k]=m;

}程序采用了邊讀入邊插入的方法。蘭色部分為后面元素后移。三、冒泡排序算法思想：讓j取1至n-1,將r[j]與r[j+1]比較,如果r[j]<r[j+1],則把記錄r[j]與r[j+1]交換位置,否則不進(jìn)行交換.最后是r[n-1]與r[n]比較，關(guān)鍵字較小的記錄就換到r[n]的位置上,到此第一趟冒泡結(jié)束。最小關(guān)鍵字的記錄就象最輕的氣泡冒到頂部一樣換到了文件的最后.(2)讓j取1至n-2,重復(fù)上述的比較對(duì)換操作,最終r[n-1]之中存放的是剩余n-1個(gè)記錄(r[n]除外)中關(guān)鍵字最小的記錄.(3)讓j取1至2,經(jīng)過(guò)一系列對(duì)聯(lián)對(duì)比交換之后,r[3]之中是剩余若干記錄中關(guān)鍵字最小的記錄.(4)讓j取1至1,將r[1]與r[2]對(duì)比,把關(guān)鍵字較小的記錄交換到r[2]之中。至此，經(jīng)過(guò)n-1次冒泡，r[1]到r[n]中的數(shù)就成了有序的數(shù)。舉例：對(duì)下面一組關(guān)鍵字，要求按照從大到小排序

a[1]a[2]a[3]a[4]a[5]a[6]a[7]13287493287491387492

1第一趟第二趟第三趟第四趟第五趟第六趟排序結(jié)束87493

2

18794

3

2

1897

4

3

2

198

7

4

3

2

19

8

7

4

3

2

1for(inti=1;i<n;i++)for(intj=1;j<=n-i;j++)if(a[j]<a[j+1]){inttmp=a[j+1];a[j+1]=a[j];a[j]=tmp;}核心代碼：優(yōu)化：如果待排序是下面這樣的數(shù)據(jù)。很顯然除了第一趟排序在最后一次比較發(fā)生了交換外，以后每一趟都不會(huì)發(fā)生交換。排序在第一趟冒泡后就已經(jīng)有序了，可以結(jié)束了。54312for(inti=1;i<n;i++){boolflag=true;//引入了一個(gè)標(biāo)記變量flag,循環(huán)中交換過(guò)就改變值for(intj=1;j<=n-i;j++)if(a[j]>a[j+1]){inttmp=a[j+1];a[j+1]=a[j];a[j]=tmp;flag=false;}//if(flag)break;//flag的值沒(méi)改變過(guò)，說(shuō)明沒(méi)發(fā)生過(guò)交換。}四、合并排序算法思想：歸并是指將若干個(gè)已排序的子文件合并成一個(gè)有的文件。歸并排序的實(shí)現(xiàn)有兩種方法：自底向上和自頂向下。采用分治法進(jìn)行的自頂向下的算法形式更為簡(jiǎn)潔。具體實(shí)現(xiàn)：設(shè)歸并排序的當(dāng)前區(qū)間是r[low…h(huán)igh]，分治法的三個(gè)步驟：（1）分解：將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn)。mid=(low+high)/2（2）求解：遞歸地對(duì)兩個(gè)子區(qū)間r[low…mid]和r[mid+1…h(huán)igh]進(jìn)行歸并排序。（3）合并：將已排好的兩個(gè)區(qū)間r[low…mid]和r[mid+1…h(huán)igh]歸并為一個(gè)有序的區(qū)間r[low…h(huán)igh]遞歸的終結(jié)條件是：low=high,即子區(qū)間的長(zhǎng)度為1。voidmerge(intl,intm,intr){intb[101];inth,t,k;k=0;h=l;t=m+1;while((h<=m)&&(t<=r)){k++;if(a[h]<a[t]){b[k]=a[h];h++;}else{b[k]=a[t];t++;}}while(h<=m){k++;b[k]=a[h];h++;}while(t<=r){k++;b[k]=a[t];t++;}for(into=1;o<=k;o++)a[l+o-1]=b[o];}voidmergesort(intx,inty){intmid;if(x>=y)return;mid=(x+y)/2;mergesort(x,mid);mergesort(mid+1,y);merge(x,mid,y);}#include<iostream>usingnamespacestd;inta[101];//定義全局?jǐn)?shù)組voidmerge(intl,intm,intr);//聲明合并函數(shù)voidmergesort(intx,inty);//聲明歸并排序函數(shù)intmain(){intn;cin>>n;for(inti=1;i<=n;i++)cin>>a[i];mergesort(1,n);for(inti=1;i<=n;i++)cout<<a[i]<<'';cout<<endl;system("pause");return0;}五、快速排序在待排序的n個(gè)記錄中任取一個(gè)記錄(通常取第一個(gè)記錄)，把該記錄放入最終位置后，整個(gè)數(shù)據(jù)區(qū)間被此記錄分割成兩個(gè)子區(qū)間。所有關(guān)鍵字比該記錄關(guān)鍵字小的放置在前子區(qū)間中,所有比他大的放置在后子區(qū)間中，并把該記錄排在這個(gè)兩個(gè)子區(qū)間的中間，這個(gè)過(guò)程稱為一趟快速排序。之后對(duì)所有的兩個(gè)子區(qū)間分別重復(fù)上述過(guò)程,直至每個(gè)子區(qū)間內(nèi)只有一個(gè)記錄為止。一趟快排的做法：設(shè)兩個(gè)指示器i和j，他們的初值分別為指向無(wú)序區(qū)中的第一個(gè)和最后一個(gè)記錄。假設(shè)無(wú)序區(qū)中記錄為R[s…t]，則i的初值為s,j的初值為t，首先將R[mid]移至臨時(shí)變量tmp中作為基準(zhǔn)，令j自t起向左掃描直至R[j]<tmp時(shí)，將R[j]移至i所指的位置上，然后令i自i+1起向右掃描直至R[i]>tmp時(shí)，將R[i]移至j所指的位置上，依次重復(fù)直至i=j，此時(shí)所有R[k](k=s,s+1,…,j-1)的關(guān)鍵字都小于tmp而所有R[k](k=j+1,j+2,…,t)的關(guān)鍵字必大于tmp，則可將tmp中的記錄移至i所指位置R[i]，它將無(wú)序中記錄分割成R[s…j-1]和R[j+1…t]，以便分別進(jìn)行排序。voidqsort(intx,inty){inttmp;inth=x,r=y;tmp=a[((h+r)/2)];while(h<r){while(a[h]<tmp)h++;while(a[r]>tmp)r--;if(h<=r){inttmp2=a[h];a[h]=a[r];a[r]=tmp2;h++;r--;}}if(x<r)qsort(x,r);if(y>h)qsort(h,y);return;}核心代碼：六、桶排序基本思想：若待排序的記錄的關(guān)鍵字在一個(gè)明顯有限范圍內(nèi)(整型)時(shí),可設(shè)計(jì)有限個(gè)有序桶,每個(gè)桶裝入一個(gè)值,順序輸出各桶的值,將得到有序的序列。注：桶排序不是基于關(guān)鍵字值比較的排序。例：對(duì)1、3、5、7、2、0、60、100、40、60排序思路：用上述待排序的數(shù)，作為數(shù)組下標(biāo)。對(duì)于上面的數(shù)，定義一個(gè)A[101],數(shù)組開(kāi)始每個(gè)元素的值為0。在讀入數(shù)據(jù)的過(guò)程中，如果讀入1令a[1]加1，讀入3，令a[3]加1…，依此處理。得到一個(gè)數(shù)組A。然后，i從0到100進(jìn)行如下處理：for(inti=0;i<=100;i++)while(a[i]>0){cout<<i<<‘‘;a[i]--;}核心代碼：#include<iostream>usingnamespacestd;intmain(){inta[1001],i,n,tmp;memset(a,0,sizeof(a));//初始化為0cin>>n;for(i=1;i<=n;i++)//邊讀人，邊把數(shù)放入桶中{cin>>tmp;a[tmp]++;}for(i=0;i<=1000;i++)//對(duì)于有數(shù)的桶進(jìn)入輸出while(a[i]>0)//可能有多個(gè)相同的關(guān)鍵字{cout<<i<<'';a[i]--;}cout<<endl;system("pause");return