總結(jié)一下常見(jiàn)的排序算法。 排序分內(nèi)排序和外排序。內(nèi)排序:指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序。外排序:指在排序期間全部對(duì)象個(gè)數(shù)太多,不能同時(shí)存放在內(nèi)存,必須根據(jù)排序過(guò)程的要求,不斷在內(nèi)、外存之間移動(dòng)的排序。內(nèi)排序的方法有許多種,按所用策略不同,可歸納為五類:插入排序、選擇排序、交換排序、歸并排序、分配排序和計(jì)數(shù)排序。插入排序主要包括直接插入排序，折半插入排序和希爾排序兩種;選擇排序主要包括直接選擇排序和堆排序;交換排序主要包括冒泡排序和快速排序;歸并排序主要包括二路歸并(常用的歸并排序)和自然歸并。分配排序主要包括箱排序和基數(shù)排序。計(jì)數(shù)排序就一種。
穩(wěn)定排序:假設(shè)在待排序的文件中,存在兩個(gè)或兩個(gè)以上的記錄具有相同的關(guān)鍵字,在用某種排序法排序后,若這些相同關(guān)鍵字的元素的相對(duì)次序仍然不變,則這種排序方法是穩(wěn)定的。其中冒泡,插入,基數(shù),歸并屬于穩(wěn)定排序;選擇,快速,希爾,堆屬于不穩(wěn)定排序。 下面是對(duì)這些常見(jiàn)排序算法的介紹。未來(lái)測(cè)試代碼的正確性，我們采取了隨機(jī)生成10個(gè)序列，然后先使用C++STL中給出的排序算法sort來(lái)得到一個(gè)正確的排序，然后再使用我們的方法進(jìn)行排序得到結(jié)果，通過(guò)對(duì)比這兩者的結(jié)果來(lái)驗(yàn)證我們代碼的正確性。
測(cè)試代碼如下：
void sort_test(void (_sort)(int,int)){ const int N=10; int orig[N]; int standard[N]; int arr[N]; srand(time(0)); for(int j=0;j<15;j++){ for(int i=0;i<N;i++) orig[i]=rand()%100;//隨機(jī)生成序列 cout<<"bef:"; print(orig,N); copy(orig,orig+N,standard); sort(standard,standard+N);//利用sort函數(shù)進(jìn)行排序 cout<<"std:"; print(standard,N); copy(orig,orig+N,arr); _sort(arr,N);//采用我們的方法進(jìn)行排序 cout<<"aft:"; print(arr,N); if(equal(standard,standard+N,arr))//測(cè)試我們的方法是否正確 printf("%sOK%s\n",green,normal); else printf("%sNO%s\n",red,normal); }}
其中參數(shù)是要測(cè)試的方法，void (_sort)(int,int)是排序方法的指針，我們所有的排序方法都寫(xiě)成這種形式。
- 直接插入排序 直接插入排序(straight insertion sort)的作法是：每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。
第一趟比較前兩個(gè)數(shù),然后把第二個(gè)數(shù)按大小插入到有序表中; 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從后向前掃描，把第三個(gè)數(shù)按大小插入到有序表中；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過(guò)程。
直接插入排序?qū)儆诜€(wěn)定的排序，時(shí)間復(fù)雜性為o(n^2)，空間復(fù)雜度為O(1)。
直接插入排序是由兩層嵌套循環(huán)組成的。外層循環(huán)標(biāo)識(shí)并決定待比較的數(shù)值。 內(nèi)層循環(huán)為待比較數(shù)值確定其最終位置。直接插入排序是將待比較的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較，所以外層循環(huán)是從第二個(gè)數(shù)值開(kāi)始的。當(dāng)前一數(shù)值比待比較數(shù) 值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置，結(jié)束該次循環(huán)。（從小到大）
值得注意的是，我們必需用一個(gè)存儲(chǔ)空間來(lái)保存當(dāng)前待比較的數(shù)值，因?yàn)楫?dāng)一趟比較完成時(shí)，我們要將待比較數(shù)值置入比它小的數(shù)值的后一位。插入排序類似玩牌時(shí)整理手中紙牌的過(guò)程。
代碼如下：
void insert_sort(int a[],int n){ _FUNC; for(int i=1;i<n;i++) { int t=a[i]; int j; for(j=i-1;j>=0&&a[j]>t;j--) { a[j+1]=a[j]; } a[j+1]=t; print(a,n); }}
測(cè)試結(jié)果如下：
-
折半插入排序
折半插入排序（binary insertion sort）是對(duì)插入排序算法的一種改進(jìn)，由于排序算法過(guò)程中，就是不斷的依次將元素插入前面已排好序的序列中。由于前半部分為已排好序的數(shù)列，這樣我們不用按順序依次尋找插入點(diǎn)，可以采用折半查找的方法來(lái)加快尋找插入點(diǎn)的速度。
折半插入排序算法的具體操作為：在將一個(gè)新元素插入已排好序的數(shù)組的過(guò)程中，尋找插入點(diǎn)時(shí)，將待插入?yún)^(qū)域的首元素設(shè)置為a[low],末元素設(shè)置為 a[high]，則輪比較時(shí)將待插入元素與a[m],其中m=(low+high)/2相比較,如果比參考元素小，則選擇a[low]到a[m-1]為新 的插入?yún)^(qū)域(即high=m-1)，否則選擇a[m+1]到a[high]為新的插入?yún)^(qū)域（即low=m+1），如此直至low<=high不成 立，即將此位置之后所有元素后移一位，并將新元素插入a[high+1]。
折半插入排序算法是一種穩(wěn)定的排序算法，比直接插入算法明顯減少了關(guān)鍵字之間比較的次數(shù)，因此速度比直接插入排序算法快，但記錄移動(dòng)的次數(shù)沒(méi)有變，所以折半插入排序算法的時(shí)間復(fù)雜度仍然為O(n^2)，與直接插入排序算法相同。
代碼如下：
復(fù)制代碼
void binary_insert_sort(int a[],int n){ for(int i=1;i<n;i++){ int low=0; int high=i-1; int t=a[i]; int mid; while(low<=high){ mid=(low+high)/2; if(t<a[mid]) high=mid-1; else low=mid+1; } for(int j=i;j>mid;j--) a[j]=a[j-1]; a[low]=t; }}
復(fù)制代碼
測(cè)試結(jié)果如下：
-
希爾排序
希爾排序（Shell Sort）又叫做縮小增量排序（diminishing increment sort），是一種很優(yōu)秀的排序法，算法本身不難理解，也很容易實(shí)現(xiàn)，而且它的速度很快。 基本思想：
先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入 排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)， 即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?br> 該方法實(shí)質(zhì)上是一種分組插入方法。插入排序（Insertion Sort）的一個(gè)重要的特點(diǎn)是，如果原始數(shù)據(jù)的大部分元素已經(jīng)排序，那么插入排序的速度很快（因?yàn)樾枰苿?dòng)的元素很少）。從這個(gè)事實(shí)我們可以想到，如果原 始數(shù)據(jù)只有很少元素，那么排序的速度也很快。－－希爾排序就是基于這兩點(diǎn)對(duì)插入排序作出了改進(jìn)。
下圖是希爾排序的一種實(shí)現(xiàn)方式：
void shell_sort(int a[],int n){ _FUNC; int gap=n/2; bool flag=true; while(gap>1||flag) { flag=false; for(int i=0;i+gap<n;i++) if(a[i]>a[i+gap]) { swap(a[i],a[i+gap]); flag=true; } print(a,n); if(gap>1) gap/=2; }}
測(cè)試結(jié)果如下：
另一種實(shí)現(xiàn)方式：
void shell_sort2(int a[],int n){// _FUNC; int gap=n/2; while(gap>0){ for(int i=gap;i<n;i++){ int t=a[i]; int j; for(j=i-gap;j>=0&&a[j]>t;j-=gap) a[j+gap]=a[j]; a[j+gap]=t; } gap/=2; }}
-
直接選擇排序
排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的，在剩余元素里面給第二個(gè)元素選擇第二小的，依次類推，直到第n-1個(gè)元素，第n個(gè) 元素不用選擇了，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了。那么，在一趟選擇，如果當(dāng)前元素比一個(gè)元素小，而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面，那么 交換后穩(wěn)定性就被破壞了。比較拗口，舉個(gè)例子，序列5 8 5 2 9，我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換，那么原序列中2個(gè)5的相對(duì)前后順序就被破壞了，所以選擇排序不是一個(gè)穩(wěn)定的排序算法。時(shí)間復(fù)雜度是O(n^2)
代碼如下：
復(fù)制代碼
void select_sort(int a[],int n){ for(int i=0;i<n-1;i++) { int min=a[i]; int index=i; for(int j=i+1;j<n;j++) if(a[j]<min) { min=a[j]; index=j; } swap(a[i],a[index]); }}
復(fù)制代碼
這個(gè)是最基本的：從中找出最小的然后和第一個(gè)數(shù)交換，再?gòu)牡?到n-1中找出最小的和第二個(gè)數(shù)交換
方法二：
void select_sort2(int a[],int n){ _FUNC; for(int i=n-1;i>0;i--){ for(int j=0;j<i;j++) if(a[j]>a[i]) swap(a[j],a[i]); }}
這兒感覺(jué)形式上有點(diǎn)類似下面的冒泡排序。
方法三：
這是對(duì)方法二的改進(jìn)，判斷過(guò)程中是否有交換發(fā)生，如果沒(méi)有交換，說(shuō)明已經(jīng)完成排序了。
void select_sort3(int a[],int n){ _FUNC; bool flag=true; for(int i=n-1;i>0&&flag;i--){ flag=false; for(int j=0;j<i;j++) if(a[j]>a[i]) swap(a[j],a[i]),flag=true; print(a,n); }}
5. 堆排序
我們知道堆的結(jié)構(gòu)是節(jié)點(diǎn)i的孩子為2i和2i+1節(jié)點(diǎn)，大頂堆要求父節(jié)點(diǎn)大于等于其2個(gè)子節(jié)點(diǎn)，小頂堆要求父節(jié)點(diǎn)小于等于其2個(gè)子節(jié)點(diǎn)。在一個(gè)長(zhǎng)為n 的序列，堆排序的過(guò)程是從第n/2開(kāi)始和其子節(jié)點(diǎn)共3個(gè)值選擇最大(大頂堆)或者最小(小頂堆),這3個(gè)元素之間的選擇當(dāng)然不會(huì)破壞穩(wěn)定性。但當(dāng)為n /2-1, n/2-2, ...1這些個(gè)父節(jié)點(diǎn)選擇元素時(shí)，就會(huì)破壞穩(wěn)定性。有可能第n/2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過(guò)去了，而第n/2-1個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒(méi) 有交換，那么這2個(gè)相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法。
堆排序的代碼如下：
void adjust(int b[],int m,int n){// int b=a-1; int j=m; int k=2m; while(k<=n){ if(k<n&&b[k]<b[k+1]) k++; if(b[j]<b[k]) swap(b[j],b[k]); j=k; k*=2; }}void heap_sort(int a[],int n){ _FUNC; int *b=a-1; for(int i=n/2;i>=1;i--) adjust(b,i,n); for(int i=n-1;i>=1;i--){ swap(b[1],b[i+1]); adjust(b,1,i); }}
需要注意的是，如果使用數(shù)組表示堆的話，要從下標(biāo)1開(kāi)始，而不是從0開(kāi)始。所以，這兒采用了一個(gè)技巧，讓int*b=a-1;這樣的話b[1]就相當(dāng)于對(duì)原數(shù)組從0開(kāi)始似的,即a[0]。
-
冒泡排序
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，是不用交換的；如果兩個(gè)相等的元素沒(méi)有相鄰，那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái)，這時(shí)候也不會(huì)交換，所以相同元素的前后順序并沒(méi)有改 變，所以冒泡排序是一種穩(wěn)定排序算法。
代碼如下：
復(fù)制代碼
void bubble_sort(int a[],int n){ _FUNC; for(int i=n-1;i>0;i--) for(int j=0;j<i;j++) if(a[j]>a[j+1]) swap(a[j],a[j+1]);}
復(fù)制代碼
下面的方法是加入了是否已經(jīng)排好序的判斷。
void bubble_sort2(int a[],int n){ bool flag=true; for(int i=n-1;i>0&&flag;i--){ flag=false; for(int j=0;j<i;j++) if(a[j]>a[j+1]) swap(a[j],a[j+1]),flag=true; }}
-
快速排序
快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年提出。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然 后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
快速排序有兩個(gè)方向，左邊的i下標(biāo)一直往右走，當(dāng)a[i] <= a[center_index]，其中center_index是中樞元素的數(shù)組下標(biāo)，一般取為數(shù)組第0個(gè)元素。而右邊的j下標(biāo)一直往左走，當(dāng)a[j] > a[center_index]。如果i和j都走不動(dòng)了，i <= j, 交換a[i]和a[j],重復(fù)上面的過(guò)程，直到i>j。交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交 換的時(shí)候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列為 5 3 3 4 3 8 9 10 11，現(xiàn)在中樞元素5和3(第5個(gè)元素，下標(biāo)從1開(kāi)始計(jì))交換就會(huì)把元素3的穩(wěn)定性打亂，所以快速排序是一個(gè)不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和 a[j] 交換的時(shí)刻。
下面的代碼中中樞元素采用的中間的元素：
復(fù)制代碼
void qsort(int a[],int l,int r){ int pvt=a[(l+r)/2]; int i=l,j=r; while(i<=j){ while(a[i]<pvt) i++; while(a[j]>pvt) j--; if(i<=j){ if(i!=j) swap(a[i],a[j]); i++; j--; } } if(j>l) qsort(a,l,j); if(i<r) qsort(a,i,r);}void quick_sort(int a[],int n){ qsort(a,0,n-1);}
復(fù)制代碼
- 二路歸并排序
歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個(gè)元素(認(rèn)為直接有序)或者2個(gè)序列(1次比較和交換),然后把各個(gè)有序的段序列合并成一個(gè)有 序的長(zhǎng)序列，不斷合并直到原序列全部排好序?？梢园l(fā)現(xiàn)，在1個(gè)或2個(gè)元素時(shí)，1個(gè)元素不會(huì)交換，2個(gè)元素如果大小相等也沒(méi)有人故意交換，這不會(huì)破壞穩(wěn)定 性。那么，在短的有序序列合并的過(guò)程中，穩(wěn)定是是否受到破壞？沒(méi)有，合并過(guò)程中我們可以保證如果兩個(gè)當(dāng)前元素相等時(shí)，我們把處在前面的序列的元素保存在結(jié) 果序列的前面，這樣就保證了穩(wěn)定性。所以，歸并排序也是穩(wěn)定的排序算法。
方法一：遞歸形式的歸并排序
void merge(int a[],int b[],int l,int m,int r){// int *b=new int[r-l+1]; int i,j,k; i=l; j=m+1; k=l; while(i<=m&&j<=r){ if(a[i]<a[j]) b[k++]=a[i++]; else b[k++]=a[j++]; } while(i<=m) b[k++]=a[i++]; while(j<=r) b[k++]=a[j++]; for(int s=l;s<=r;s++) a[s]=b[s];// delete[] b;}void msort(int a[],int b[],int l,int r){ if(l<r){ int m=(l+r)/2; msort(a,b,l,m); msort(a,b,m+1,r); merge(a,b,l,m,r); }}void merge_sort(int a[],int n){ _FUNC; int *b=new int[n]; msort(a,b,0,n-1); delete[] b;}
方法二：去除遞歸的方法
void merge_pass(int x[],int y[],int s,int n){ int i=0; while(i+2s-1<n){ merge(x,y,i,i+s-1,i+2s-1); i+=2*s; } if(i+s<n) merge(x,y,i,i+s-1,n-1); else for(int j=i;j<=n-1;j++) y[j]=x[j];}void merge_sort2(int a[],int n){ _FUNC; int *b=new int [n]; int s=1; while(s<n){ merge_pass(a,b,s,n); s+=s; merge_pass(b,a,s,n); s+=s; } delete[] b;}
-
自然歸并排序
下面的兩種形式是一樣的，開(kāi)始我先采用的vector來(lái)記錄子序列的位置，后來(lái)發(fā)現(xiàn)其實(shí)采用一個(gè)數(shù)組就可以了。兩種代碼都放在這兒吧。
形式1：
復(fù)制代碼
void merge_sort3(int a[],int n){ vector<int> st; for(int i=0;i<n-1;i++){ if(a[i]>a[i+1]) st.push_back(i); } st.push_back(n-1);// copy(st.begin(),st.end(),ostream_iterator<int>(cout," "));// cout<<endl; int *b=new int [n]; int l,m,r; l=0; if(!st.empty()) { m=st.front(); st.erase(st.begin()); } while(!st.empty()){ r=st.front(); st.erase(st.begin()); merge(a,b,l,m,r);// print(a,n);// copy(st.begin(),st.end(),ostream_iterator<int>(cout," "));// cout<<endl; m=r; }// print(a,n); delete [] b;}
復(fù)制代碼
形式2：
void merge_sort4(int a[],int n){ _FUNC; int *pos=new int[n]; int k=0; for(int i=0;i<n-1;i++){ if(a[i]>a[i+1]) pos[k++]=i; } pos[k++]=n-1; int *b=new int [n]; int l,m,r; l=0; int p=0; if(p<k) m=pos[p++]; while(p<k){ r=pos[p++]; merge(a,b,l,m,r); m=r; } delete [] b;}
-
箱排序
一個(gè)簡(jiǎn)單的測(cè)試?yán)尤缦拢?div id="u0z1t8os" class="image-package">
