排序算法

算法分類 ——?十種常見排序算法可以分為兩大類：

比較類排序：通過比較來決定元素間的相對次序，由于其時間復(fù)雜度不能突破O(nlogn)，因此也稱為非線性時間比較類排序。

非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序。?

算法復(fù)雜度

1. 冒泡排序

算法思想：

（1）比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；

（2）對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)；

（3）針對所有的元素重復(fù)以上的步驟，除了最后一個；

（4）重復(fù)步驟1~3，直到排序完成。

代碼：

void?bubbleSort(int?a[],?int?n)
{
??for(int?i?=0?;?i?a[j+1])
??????{
????????int?tmp?=?a[j]?;??//交換
????????a[j]?=?a[j+1]?;
????????a[j+1]?=?tmp;
??????}
????}
??}
}

?

2. 選擇排序

算法思想：

（1）在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置；

（2）從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末；

（3）以此類推，直到所有元素均排序完畢；

代碼：

void?selectionSort(int?arr[],?int?n)?{
????int?minIndex,?temp;
????for?(int?i?=?0;?i?

	?

	3. 插入排序

	算法思想：

	（1）從第一個元素開始，該元素可以認為已經(jīng)被排序；

	（2）取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；

	（3）如果該元素（已排序）大于新元素，將該元素移到下一位置；

	（4）重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；

	（5）將新元素插入到該位置后；

	（6）重復(fù)步驟2~5。

	

	代碼：
void?print(int?a[],?int?n?,int?i){
??cout<

	?

	算法分析：插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

	4.?快速排序

	快速排序的基本思想是通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。

	算法思想：

	（1）選取第一個數(shù)為基準

	（2）將比基準小的數(shù)交換到前面，比基準大的數(shù)交換到后面

	（3）遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序

	

	代碼：
void?QuickSort(vector&?v,?int?low,?int?high)?{
????if?(low?>=?high)??//?結(jié)束標志
????????return;
????int?first?=?low;??//?低位下標
????int?last?=?high;??//?高位下標
????int?key?=?v[first];??//?設(shè)第一個為基準

????while?(first?=?key)
????????????last--;
????????if?(first?

	?

	5.?堆排序

	堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子節(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。

	算法思想：

	（1）將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)；

	（2）將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；

	（3）由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成。

	

	代碼：
#include?
#include?
using?namespace?std;

//?堆排序：（最大堆，有序區(qū)）。從堆頂把根卸出來放在有序區(qū)之前，再恢復(fù)堆。

void?max_heapify(int?arr[],?int?start,?int?end)?{
????//建立父節(jié)點指標和子節(jié)點指標
????int?dad?=?start;
????int?son?=?dad?*?2?+?1;
????while?(son?<=?end)?{?//若子節(jié)點在范圍內(nèi)才做比較
????????if?(son?+?1?<=?end?&&?arr[son]??arr[son])?//如果父節(jié)點大于子節(jié)點代表調(diào)整完成，直接跳出函數(shù)
????????????return;
????????else?{?//否則交換父子內(nèi)容再繼續(xù)子節(jié)點與孫節(jié)點比較
????????????swap(arr[dad],?arr[son]);
????????????dad?=?son;
????????????son?=?dad?*?2?+?1;
????????}
????}
}

void?heap_sort(int?arr[],?int?len)?{
????//初始化，i從最后一個父節(jié)點開始調(diào)整
????for?(int?i?=?len?/?2?-?1;?i?>=?0;?i--)
????????max_heapify(arr,?i,?len?-?1);
????//先將第一個元素和已經(jīng)排好的元素前一位做交換，再從新調(diào)整(剛調(diào)整的元素之前的元素)，直到排序完成
????for?(int?i?=?len?-?1;?i?>?0;?i--)?{
????????swap(arr[0],?arr[i]);
????????max_heapify(arr,?0,?i?-?1);
????}
}

int?main()?{
????int?arr[]?=?{?3,?5,?3,?0,?8,?6,?1,?5,?8,?6,?2,?4,?9,?4,?7,?0,?1,?8,?9,?7,?3,?1,?2,?5,?9,?7,?4,?0,?2,?6?};
????int?len?=?(int)?sizeof(arr)?/?sizeof(*arr);
????heap_sort(arr,?len);
????for?(int?i?=?0;?i?

	?

	6. 歸并排序

	歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。? 算法思想：

	（1）把長度為n的輸入序列分成兩個長度為n/2的子序列；

	（2）對這兩個子序列分別采用歸并排序；

	（3）將兩個排序好的子序列合并成一個最終的排序序列。

	

	代碼：
void?print(int?a[],?int?n){
??for(int?j=?0;?j

	?

	7. 希爾排序

	1959年Shell發(fā)明，第一個突破O(n2)的排序算法，是簡單插入排序的改進版。它與插入排序的不同之處在于，它會優(yōu)先比較距離較遠的元素。希爾排序又叫縮小增量排序。 算法思想：

	（1）選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；

	（2）按增量序列個數(shù)k，對序列進行k 趟排序；

	（3）每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

	

	代碼：
void?shell_sort(T?array[],?int?length)?{
????int?h?=?1;
????while?(h?=?1)?{
????????for?(int?i?=?h;?i?=?h?&&?array[j]?

	?

	8. 計數(shù)排序

	計數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復(fù)雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

	算法思想：

	（1）找出待排序的數(shù)組中最大和最小的元素；

	（2）統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項；

	（3）對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）；

	（4）反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1。

	

	代碼：

	?
#include?
#include?
#include?

using?namespace?std;

//?計數(shù)排序
void?CountSort(vector&?vecRaw,?vector&?vecObj)
{
????//?確保待排序容器非空
????if?(vecRaw.size()?==?0)
????????return;

????//?使用?vecRaw?的最大值?+?1?作為計數(shù)容器?countVec?的大小
????int?vecCountLength?=?(*max_element(begin(vecRaw),?end(vecRaw)))?+?1;
????vector?vecCount(vecCountLength,?0);

????//?統(tǒng)計每個鍵值出現(xiàn)的次數(shù)
????for?(int?i?=?0;?i??0;?i--)?//?此處逆序是為了保持相同鍵值的穩(wěn)定性
????????vecObj[--vecCount[vecRaw[i?-?1]]]?=?vecRaw[i?-?1];
}

int?main()
{
????vector?vecRaw?=?{?0,5,7,9,6,3,4,5,2,8,6,9,2,1?};
????vector?vecObj(vecRaw.size(),?0);

????CountSort(vecRaw,?vecObj);

????for?(int?i?=?0;?i?

	?

	9. 桶排序

	將值為i的元素放入i號桶，最后依次把桶里的元素倒出來。

	算法思想：

	（1）設(shè)置一個定量的數(shù)組當作空桶子。

	（2）尋訪序列，并且把項目一個一個放到對應(yīng)的桶子去。

	（3）對每個不是空的桶子進行排序。

	（4）從不是空的桶子里把項目再放回原來的序列中。

	

	代碼：
void?Bucket_Sort(int?a[],?int?n,?int?max)?{
????int?i,?j=0;
????int?*buckets?=?(int*)malloc((max+1)*sizeof(int));
????//?將buckets中的所有數(shù)據(jù)都初始化為0
????memset(buckets,?0,?(max+1)?*?sizeof(int));
????//?1.計數(shù)
????for?(i?=?0;?i??0)?{
????????????a[j++]?=?i;
????????}
????}
}
?
int?main()?{
????int?arr[]?=?{?9,5,1,6,2,3,0,4,8,7?};
????Bucket_Sort(arr,?10,9);
????for?(int?i?=?0;?i?

	?

	10. 基數(shù)排序

	一種多關(guān)鍵字的排序算法，可用桶排序?qū)崿F(xiàn)。

	算法思想：

	取得數(shù)組中的最大數(shù)，并取得位數(shù)；

	arr為原始數(shù)組，從最低位開始取每個位組成radix數(shù)組；

	對radix進行計數(shù)排序（利用計數(shù)排序適用于小范圍數(shù)的特點）

	

	代碼：
int?maxbit(int?data[],?int?n)?//輔助函數(shù)，求數(shù)據(jù)的最大位數(shù)
{
????int?maxData?=?data[0];??///=?p)
????{
????????//p?*=?10;?//?Maybe?overflow
????????maxData?/=?10;
????????++d;
????}
????return?d;
/*????int?d?=?1;?//保存最大的位數(shù)
????int?p?=?10;
????for(int?i?=?0;?i?=?p)
????????{
????????????p?*=?10;
????????????++d;
????????}
????}
????return?d;*/
}
void?radixsort(int?data[],?int?n)?//基數(shù)排序
{
????int?d?=?maxbit(data,?n);
????int?*tmp?=?new?int[n];
????int?*count?=?new?int[10];?//計數(shù)器
????int?i,?j,?k;
????int?radix?=?1;
????for(i?=?1;?i?<=?d;?i++)?//進行d次排序
????{
????????for(j?=?0;?j?=?0;?j--)?//將所有桶中記錄依次收集到tmp中
????????{
????????????k?=?(data[j]?/?radix)?%?10;
????????????tmp[count[k]?-?1]?=?data[j];
????????????count[k]--;
????????}
????????for(j?=?0;?j?
?

	?

	　　審核編輯：湯梓紅