數(shù)據(jù)結構排序算法

1、 常見排序算法總結1. 基本概念排序：是將一組數(shù)據(jù)元素按某種特定要求(升或降序)排列成有規(guī)律序列的過程。排序可以分為內(nèi)部排序和外部排序兩種：1). 若整個排序過程不需要訪問外存便能完成，則稱此類排序為內(nèi)部排序。2). 若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，需要借助外存來完成，則稱此類排序為外部排序。/不涉及內(nèi)外存交換就地排序：若排序算法所需的輔助空間并不依賴于問題的規(guī)模n，即輔助空間為O(1)，則稱為就地排序。穩(wěn)定性：假設在待排序的元素中，存在兩個或兩個以上的元素具有相同的關鍵字，在用某種排序法排序后，若這些相同關鍵字的元素的相對次序仍然不變，則這種排序方法是穩(wěn)定的。

2、2. 常見內(nèi)部排序2.1 交換排序交換排序的基本思想是兩兩比較待排序記錄的關鍵字，若發(fā)生與排序要求相逆，則交換之，反復進行，直到數(shù)據(jù)有序。交換排序的主要方法有：冒泡排序和快速排序。1). 冒泡排序a. 算法思想已知一組無序數(shù)據(jù)元素Pn，需將按其關鍵字升序排列。第一趟對n個元素冒泡得到一個關鍵字最大的元素Pn-1，第二趟冒泡對n-1個元素得到一個關鍵字最大的元素Pn-2，依次類推，直到數(shù)據(jù)有序。b. 算法實現(xiàn)void buble(int arr, int n)bool flag;/用于判斷是否發(fā)生了交換int i;int temp;/臨時變量/反復多輪，從小到大排序。do /一輪排序flag =

3、 false;/反復比較所有相鄰的元素，循環(huán)比較n-1次。for(i = 1; i < n; i+) /如果順序不當，就交換他們。if(arri < arri - 1) temp = arri;arri = arri - 1;arri - 1 = temp;/記錄本輪已發(fā)生交換flag = true;n-;while(flag);/知道本輪沒有發(fā)生交換，循環(huán)退出。注：冒泡排序算法是穩(wěn)定的，時間復雜度是O(n2)。冒泡排序算法適合只有少量亂序的數(shù)據(jù)。 2). 快速排序a. 算法思想已知一組無序數(shù)據(jù)元素Pn，需將按其關鍵字升序排列。首先任取一個元素Px(通常選取首元素)作為基準，多次比

4、較Px與其它元素并交換。直到當Px可以排在序列的第k位，并且使P0Pk中的每一個元素小于Px，Pk+1Pn-1中的每一個元素不小于Px時，交換Px和Pk。再分別對P0Pk-1和Pk+1Pn-1兩組數(shù)據(jù)元素重復上述過程，直到數(shù)據(jù)有序。b. 算法實現(xiàn)/交換函數(shù)void swap(int *a, int *b)int temp;temp = *a;*a = *b;*b = temp;/快速排序void qsort(int arr, int n)int temp;int *L, *R;if(n <= 1) return;if( n = 2) if(arr1 < arr0) swap(&am

5、p;arr1, &arr0);return;swap(&arr0, &arrn / 2);temp = arr0;L = arr + 1;R = arr + n -1;while(L < R) while(L < R && *L < temp) L+;while(R > arr && *R >= temp) R-;if(L < R) swap(L, R);swap(arr, R);qsort(arr, R - arr);qsort(R + 1, n -(R - arr) - 1);注：快速排序是不穩(wěn)定的

6、，時間復雜度是O(nlgn)。2.2 插入排序插入排序的基本思想是每次將一個待排序的元素按其關鍵字的大小，插到前面的有序元素中，反復進行，直到數(shù)據(jù)有序。插入排序方法主要有：直接插入排序、折半插入排序和希爾排序。1). 直接插入排序a. 算法思想已知一組無序數(shù)據(jù)元素Pn，需將按其關鍵字升序排列。假設前面(n-1) (n>=2)個元素已經(jīng)是排好順序的，現(xiàn)在要把第n個元素插到前面的有序元素中，使得這n個元素也是有序的，如此反復，直到數(shù)據(jù)有序。其中查找插入位置時采用順序查找。b. 算法實現(xiàn)void insert(int arr, int n)int i, j;int temp;for(i = 1

7、; i < n; i+) /從小到大排序，反復n-1次。if(arri >= arri -1) continue;temp = arri;/另存一份for(j = i; j > 0 && arrj - 1 > temp; j-) arrj = arrj - 1;arrj = temp;/插入備份注：直接插入排序算法是穩(wěn)定的，時間復雜度是O(n2)。2). 折半插入排序a. 算法思想已知一組無序數(shù)據(jù)元素Pn，需將按其關鍵字升序排列。假設前面(n-1) (n>=2)個元素已經(jīng)是排好順序的，現(xiàn)在要把第n個元素插到前面的有序元素中，使得這n個元素也是有序的

8、，如此反復，直到數(shù)據(jù)有序。其中查找插入位置時采用二分查找。b. 算法實現(xiàn)void binaryInsert(int arr, int n)int i, j, low, mid, high;int temp;for(i = 1; i < n; +i) /從小到大排序，反復n-1次。temp = arri;/另存一份low = 0;high = i - 1;while(low <= high) /二分查找待插入位置(high+1)mid = (low + high) / 2;if(arri < arrmid) high = mid - 1;else low = mid + 1;f

9、or(j = i - 1; j >= high + 1; -j) arrj + 1 = arrj;/后移元素，留出插入空位。arrhigh + 1 = temp;/插入備份注：折半插入排序算法是穩(wěn)定的，時間復雜度是O(n2)。3). 希爾排序a. 算法思想已知一組無序數(shù)據(jù)元素Pn，需將按其關鍵字升序排列。先將要排序的一組元素按某個增量d分成若干組，每組中元素的下標相差d。對每組中全部元素進行排序。然后再用一個較小的增量對它進行分組，在每組中再進行排序，直到增量減小到1時，整個要排序的數(shù)被分在一組，排序完成，數(shù)據(jù)有序。b. 算法實現(xiàn)void shellSort(int array, int

10、 n)int i, j, d;int temp, flag;d = n;/外循環(huán)控制增量(分組)，直到d為1時止。do d = d / 2;/中間循環(huán)是在某一個分組值下，分別對各組進行組內(nèi)排序，若發(fā)生了元素交換，繼續(xù)循環(huán)，直到各組內(nèi)無元素交換為止。do flag = 0;/內(nèi)循環(huán)是從第一個元素開始，按某個d值的間距進行組內(nèi)比較，若有逆序，則進行交換。for(i = 0; i < n - d; +i) j = i + d;if(arrayi > arrayj) temp = arrayi;arrayi = arrayj;arrayj = temp;flag = 1;while(fla

11、g);while(d > 1);注： 希爾排序是不穩(wěn)定的，時間復雜度是O(n1.3)。同時希爾排序的時間復雜度依賴于所取增量序列，一般認為是O(nlgn)。2.3 選擇排序選擇排序的基本思想是每次從待排序的元素中選出關鍵字最小的元素，順序存放在有序序列的后面，反復進行，直到數(shù)據(jù)有序。選擇排序方法主要有：直接選擇排序和堆排序。1). 直接選擇排序a. 算法思想已知一組無序數(shù)據(jù)元素Pn，需將按其關鍵字升序排列。第一趟，從n個元素中選出關鍵字最小的一個元素與第一個位置的元素交換。第二趟，從剩下的元素中再選擇關鍵字最小的元素與第二個位置的元素交換。第三趟，如此反復，直到數(shù)據(jù)有序。 b. 算法實現(xiàn)

12、void select(int arr, int n)int i, j;int min;/最小元素下標for(i = 0; i < n - 1; i+) min = i;/將第一個元素作為最小元素for(j = i + 1; j < n; j+) /反復查找其后n-1個更小的元素if(arrj < arrmin) /發(fā)現(xiàn)更小的，則記錄其下標。min = j;if(i != min) /防止相同位置的交換。int temp;temp = arri;arri = arrmin;arrmin = temp;注：選擇排序是不穩(wěn)定的，時間復雜度是O(n2)。2). 堆排序堆排序是一種樹

13、形選擇排序，是對直接選擇排序的有效改進。a.堆的定義如下：具有n個元素的序列(h1, h2, ., hn)，當且僅當滿足(hi>=h2i, hi>=2i+1)或(hi<=h2i, hi<=2i+1) (i=1, 2, ., n/2)時稱之為堆。注：若將此序列Pn看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹，樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子結點的關鍵字。a. 算法思想已知一組無序數(shù)據(jù)元素Pn，需將按其關鍵字升序排列。初始時把Pn看作是以P0為樹根，P1.2.3.n-1依次從左向右逐層排列的一棵順序存儲的完全二叉樹，調(diào)整它們的存

14、儲順序， 使之成為一個堆。然后將根節(jié)點與堆的最后一個節(jié)點交換，再對前面n-1個元素重新調(diào)整使之成為堆，并將根節(jié)點與新堆的最后一個節(jié)點交換，依此類推，直到數(shù)據(jù)有序。b. 算法實現(xiàn)/建堆/調(diào)整成大根堆/array是待調(diào)整數(shù)組，length是數(shù)組的長度，i是待調(diào)整元素的位置(下標)。void heapAdjust(int array, int length, int i)int temp;/保存開始待調(diào)整的元素int child;for(temp = arrayi; 2 * i + 1 < length; i = child) /2*i+1為待調(diào)整元素左子樹的位置，若默認下標從1開始，則為右子

15、樹位置。/保存左子節(jié)點的位置child = 2 * i + 1;/獲取子節(jié)點中較大的節(jié)點位置，要么左子樹位置，要么右子樹位置。if(child < length -1 && arraychild < arraychild + 1) +child;/判斷較大的子節(jié)點是否大于父節(jié)點，若是，把較大的子節(jié)點向上移動，替換其父節(jié)點。不用擔心，父節(jié)點之前已經(jīng)另存了一份。if(arraychild > temp) arrayi = arraychild;arraychild = temp;else break;arrayi = temp;/最后把開始元素放到合適的位置上/堆

16、排序void heapSort(int array, int length)int i;/創(chuàng)建堆/若默認第一個節(jié)點的下標為0，操作從length/2-1位置開始。/若默認第一個節(jié)點的下標為1，操作從length/2位置開始。for(i = length / 2 - 1; i >= 0; -i) heapAdjust(array, length, i);/調(diào)整堆/從最后一個元素開始對序列進行調(diào)整，不斷的縮小調(diào)整的范圍直到第一個元素。for(i = length - 1; i > 0; -i) /把第一個元素和當前的最后一個元素交換，保證當前的最后一個位置的元素都是在現(xiàn)在的這個序列之中

17、最大的。 int temp;temp = array0;array0 = arrayi;arrayi = temp;/重新從下標為0的位置開始調(diào)整成堆，不斷縮小調(diào)整的范圍，每一次調(diào)整完畢保證第一個元素是當前序列的最大值。heapAdjust(array, i , 0);/對根結點重新調(diào)整使之成為大根堆注：堆排序是不穩(wěn)定的，時間復雜度是O(nlgn)。2.4 歸并排序歸并排序的基本思想是把待排序序列分為若干個子序列，每個子序列是有序的，然后再把有序子序列合并為整體有序序列。若將兩個有序表合并成一個有序表，稱為二路歸并。a. 二路歸并算法思想定義兩個數(shù)組temp1m, temp2n，分別將待合并數(shù)

18、組mergeend-start+1的兩部分元素拷貝到定義的數(shù)組中，并設置相應的監(jiān)視哨。合并時，依次比較temp1i和temp2j的大小，并將較小的元素拷貝到mergek中，然后讓相應元素的下標加1，依此類推，直到合并成功。b. 算法實現(xiàn)/合并void Merge(int array, int start, int mid, int end) int temp110, temp210; int n1, n2;int i, j, k; n1 = mid - start + 1; n2 = end - mid; for (int i = 0; i < n1; +i) /拷貝前半部分元素 tem

19、p1i = arraystart + i; for (int i = 0; i < n2; i+) /拷貝后半部分元素 temp2i = arraymid + i + 1; temp1n1 = temp2n2 = 5211314;/拷貝完成后，分別將后一個下標對應的元素設置為足夠大。好處是兩部分數(shù)組元素將完全合并，無剩余。 for (k = start, i = 0, j = 0; k <= end; k+) /逐個判斷兩部分數(shù)組中元素的大小次序，然后放到相應的位置。 if (temp1i <= temp2j) arrayk = temp1i; i+; else arrayk

20、 = temp2j; j+; /劃分void MergeSort(int array, int start, int end) if(start < end) int mid; mid = (end + start) / 2; MergeSort(array, start, mid);/ 對前半部分進行劃分MergeSort(array, mid + 1, end);/對后半部分進行劃分Merge(array, start, mid, end);/合并前后兩部分 注：歸并排序是穩(wěn)定的，時間復雜度是O(nlgn)。2.5 基數(shù)排序基數(shù)排序的基本思想是將所有待排元素(必須是正整數(shù))統(tǒng)一認為是

21、數(shù)位相同的數(shù)，數(shù)位較短的在最左邊補零。然后從最邊位(最左邊或最右邊)開始， 依次進行一次穩(wěn)定排序，這樣從一邊一直到另一邊的排序完成之后， 數(shù)據(jù)有序。a. 算法思想基數(shù)排序是一種分配排序，排序過程無須比較關鍵字，而是通過“分配”和“收集”過程來實現(xiàn)排序。從最低位關鍵字起，按照關鍵字位值的不同將序列中的元素"分配"到"基"個隊列中，然后再"收集"之，如此重復d次即可。其中：d為位值的個數(shù)，位值的取值范圍的長度(又稱基)為radix。/數(shù)字范圍：0-9，基為：10b. 算法實現(xiàn)#define BITNUM 6/位值個數(shù)#define RAD

22、IX 10/基值#define MAX_SPACE 50/最大可用空間/靜態(tài)鏈表結點類型定義typedef struct BitNode int data;/數(shù)據(jù)域int bitsBITNUM;/數(shù)據(jù)位值域int next;/指針域bitnode;/靜態(tài)鏈表類型定義typedef struct StaticLinkList bitnode rMAX_SPACE;/待排序序列，r0為頭結點，頭結點的數(shù)據(jù)域用于存放其它信息。int length;/當前長度int bitnum;/位置個數(shù)linklist;/定義數(shù)組類型，用于分別指向基值個隊列。typedef int arraytypeRADIX;

23、/分配/建立RADIX個隊列，使同一隊列中元素的bitsi相同。/front0.RADIX-1和rear0.RADIX-1分別指向各隊列中第一個和最后一個元素。void distribute(bitnode R, int i, arraytype front, arraytype rear)int j, p;for(j = 0; j < RADIX; +j) /各隊列初始化為空frontj = rearj = 0;for(p = R0.next; p; p = Rp.next) j = Rp.bitsi;/映射i位值if(!frontj) frontj = p;/若frontj為空，則把p位置對應的元素鏈接到frontj的頭指針上。else Rrearj.next = p;/若frontj的頭指針上已經(jīng)鏈接了，這時讓上一個以j為位值的元素的next指向當前元素。rearj = p;/尾指針指向新的元素下標/收集/本算法按bitsi值從小到大地將front0.RADIX-1所指各隊列依次鏈接成為一個靜態(tài)鏈表void collect(bitno