總結(jié)一下常見的排序算法仑性。 排序分內(nèi)排序和外排序。內(nèi)排序:指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序脱篙。外排序:指在排序期間全部對象個(gè)數(shù)太多,不能同時(shí)存放在內(nèi)存,必須根據(jù)排序過程的要求,不斷在內(nèi)圃酵、外存之間移動(dòng)的排序。內(nèi)排序的方法有許多種,按所用策略不同,可歸納為五類:插入排序鼎姐、選擇排序、交換排序、歸并排序炕桨、分配排序和計(jì)數(shù)排序饭尝。插入排序主要包括直接插入排序，折半插入排序和希爾排序兩種;選擇排序主要包括直接選擇排序和堆排序;交換排序主要包括冒泡排序和快速排序;歸并排序主要包括二路歸并(常用的歸并排序)和自然歸并献宫。分配排序主要包括箱排序和基數(shù)排序钥平。計(jì)數(shù)排序就一種。
穩(wěn)定排序:假設(shè)在待排序的文件中,存在兩個(gè)或兩個(gè)以上的記錄具有相同的關(guān)鍵字,在用某種排序法排序后,若這些相同關(guān)鍵字的元素的相對次序仍然不變,則這種排序方法是穩(wěn)定的姊途。其中冒泡,插入,基數(shù),歸并屬于穩(wěn)定排序;選擇,快速,希爾,堆屬于不穩(wěn)定排序涉瘾。 下面是對這些常見排序算法的介紹。未來測試代碼的正確性捷兰，我們采取了隨機(jī)生成10個(gè)序列立叛，然后先使用C++STL中給出的排序算法sort來得到一個(gè)正確的排序，然后再使用我們的方法進(jìn)行排序得到結(jié)果贡茅，通過對比這兩者的結(jié)果來驗(yàn)證我們代碼的正確性秘蛇。
測試代碼如下：
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))//測試我們的方法是否正確 printf("%sOK%s\n",green,normal); else printf("%sNO%s\n",red,normal); }}
其中參數(shù)是要測試的方法，void (_sort)(int,int)是排序方法的指針顶考，我們所有的排序方法都寫成這種形式赁还。
- 直接插入排序 直接插入排序(straight insertion sort)的作法是：每次從無序表中取出第一個(gè)元素，把它插入到有序表的合適位置村怪，使有序表仍然有序秽浇。
第一趟比較前兩個(gè)數(shù),然后把第二個(gè)數(shù)按大小插入到有序表中; 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從后向前掃描浮庐，把第三個(gè)數(shù)按大小插入到有序表中甚负；依次進(jìn)行下去，進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過程审残。
直接插入排序?qū)儆诜€(wěn)定的排序梭域，時(shí)間復(fù)雜性為o(n^2)，空間復(fù)雜度為O(1)搅轿。
直接插入排序是由兩層嵌套循環(huán)組成的病涨。外層循環(huán)標(biāo)識并決定待比較的數(shù)值。 內(nèi)層循環(huán)為待比較數(shù)值確定其最終位置璧坟。直接插入排序是將待比較的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較既穆，所以外層循環(huán)是從第二個(gè)數(shù)值開始的。當(dāng)前一數(shù)值比待比較數(shù) 值大的情況下繼續(xù)循環(huán)比較雀鹃，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置幻工，結(jié)束該次循環(huán)。（從小到大）
值得注意的是黎茎，我們必需用一個(gè)存儲空間來保存當(dāng)前待比較的數(shù)值囊颅，因?yàn)楫?dāng)一趟比較完成時(shí)，我們要將待比較數(shù)值置入比它小的數(shù)值的后一位。插入排序類似玩牌時(shí)整理手中紙牌的過程踢代。
代碼如下：
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); }}
測試結(jié)果如下：
-
折半插入排序
折半插入排序（binary insertion sort）是對插入排序算法的一種改進(jìn)盲憎，由于排序算法過程中，就是不斷的依次將元素插入前面已排好序的序列中胳挎。由于前半部分為已排好序的數(shù)列饼疙，這樣我們不用按順序依次尋找插入點(diǎn)，可以采用折半查找的方法來加快尋找插入點(diǎn)的速度慕爬。
折半插入排序算法的具體操作為：在將一個(gè)新元素插入已排好序的數(shù)組的過程中宏多，尋找插入點(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ù)沒有變彪标，所以折半插入排序算法的時(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ù)制代碼
測試結(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)對插入排序作出了改進(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; }}
測試結(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會和2交換，那么原序列中2個(gè)5的相對前后順序就被破壞了烫沙，所以選擇排序不是一個(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ù)交換，再從第2到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]); }}
這兒感覺形式上有點(diǎn)類似下面的冒泡排序锌蓄。
方法三：
這是對方法二的改進(jìn)升筏，判斷過程中是否有交換發(fā)生，如果沒有交換煤率，說明已經(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è)長為n 的序列辆沦，堆排序的過程是從第n/2開始和其子節(jié)點(diǎn)共3個(gè)值選擇最大(大頂堆)或者最小(小頂堆),這3個(gè)元素之間的選擇當(dāng)然不會破壞穩(wěn)定性昼捍。但當(dāng)為n /2-1, n/2-2, ...1這些個(gè)父節(jié)點(diǎn)選擇元素時(shí)，就會破壞穩(wěn)定性肢扯。有可能第n/2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過去了妒茬，而第n/2-1個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒 有交換，那么這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開始多糠，而不是從0開始。所以浩考，這兒采用了一個(gè)技巧夹孔，讓int*b=a-1;這樣的話b[1]就相當(dāng)于對原數(shù)組從0開始似的,即a[0]。
-
冒泡排序
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)析孽。比較是相鄰的兩個(gè)元素比較搭伤，交換也發(fā)生在這兩個(gè)元素之間。所以袜瞬，如果兩個(gè)元素相等怜俐，是不用交換的；如果兩個(gè)相等的元素沒有相鄰邓尤，那么即使通過前面的兩兩交換把兩個(gè)相鄰起來佑菩，這時(shí)候也不會交換，所以相同元素的前后順序并沒有改 變裁赠，所以冒泡排序是一種穩(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）是對冒泡排序的一種改進(jìn)佩捞。由C. A. R. Hoare在1962年提出绞幌。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小一忱，然 后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序莲蜘，整個(gè)排序過程可以遞歸進(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ù)上面的過程算途，直到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開始計(jì))交換就會把元素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è)有 序的長序列，不斷合并直到原序列全部排好序蝎毡『窳可以發(fā)現(xiàn)，在1個(gè)或2個(gè)元素時(shí)沐兵，1個(gè)元素不會交換别垮，2個(gè)元素如果大小相等也沒有人故意交換，這不會破壞穩(wěn)定 性扎谎。那么蜕该，在短的有序序列合并的過程中劳殖，穩(wěn)定是是否受到破壞督暂？沒有蛮位，合并過程中我們可以保證如果兩個(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;}
-
自然歸并排序
下面的兩種形式是一樣的岩遗，開始我先采用的vector來記錄子序列的位置，后來發(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è)簡單的測試?yán)尤缦拢?div id="ep51a5u" class="image-package">
