C++八大排序算法

1、插入排序1.直接插入排序原理：將數(shù)組分為無序區(qū)和有序區(qū)兩個(gè)區(qū)，然后不斷將無序區(qū)的第一個(gè)元素按大小順序插入到有序區(qū)中去，最終將所有無序區(qū)元素都移動(dòng)到有序區(qū)完成排序。要點(diǎn)：設(shè)立哨兵，作為臨時(shí)存儲(chǔ)和判斷數(shù)組邊界之用。實(shí)現(xiàn)：Void InsertSort(Node L,int length)Int i,j;/分別為有序區(qū)和無序區(qū)指針for(i=1;i<length;i+)/逐步擴(kuò)大有序區(qū)j=i+1;if(Lj<Li)L0=Lj;/存儲(chǔ)待排序元素While(L0<Li)/查找在有序區(qū)中的插入位置，同時(shí)移動(dòng)元素Li+1=Li;/移動(dòng)i-;/查找Li+1=L0;/將元素插入i=j-1;/還

2、原有序區(qū)指針2.希爾排序原理：又稱增量縮小排序。先將序列按增量劃分為元素個(gè)數(shù)相同的若干組，使用直接插入排序法進(jìn)行排序，然后不斷縮小增量直至為1，最后使用直接插入排序完成排序。要點(diǎn)：增量的選擇以及排序最終以1為增量進(jìn)行排序結(jié)束。實(shí)現(xiàn)：Void shellSort(Node L,int d)While(d>=1)/直到增量縮小為1Shell(L,d);d=d/2;/縮小增量Void Shell(Node L,int d)Int i,j;For(i=d+1;i<length;i+)if(Li<Li-d)L0=Li;j=i-d;While(j>0&&Lj>

3、L0)Lj+d=Lj;/移動(dòng)j=j-d;/查找Lj+d=L0;交換排序1.冒泡排序原理：將序列劃分為無序和有序區(qū)，不斷通過交換較大元素至無序區(qū)尾完成排序。要點(diǎn)：設(shè)計(jì)交換判斷條件，提前結(jié)束以排好序的序列循環(huán)。實(shí)現(xiàn)：Void BubbleSort(Node L)Int i ,j;Bool ischanged;/設(shè)計(jì)跳出條件For(j=n;j<0;j-)ischanged =false;For(i=0;i<j;i+)If(Li>Li+1)/如果發(fā)現(xiàn)較重元素就向后移動(dòng)Int temp=Li;Li=Li+1;Li+1=temp;Ischanged =true;If(!ischanged

4、)/若沒有移動(dòng)則說明序列已經(jīng)有序，直接跳出Break;2.快速排序原理：不斷尋找一個(gè)序列的中點(diǎn)，然后對中點(diǎn)左右的序列遞歸的進(jìn)行排序，直至全部序列排序完成，使用了分治的思想。要點(diǎn)：遞歸、分治實(shí)現(xiàn)：選擇排序1.直接選擇排序原理：將序列劃分為無序和有序區(qū)，尋找無序區(qū)中的最小值和無序區(qū)的首元素交換，有序區(qū)擴(kuò)大一個(gè)，循環(huán)最終完成全部排序。要點(diǎn)：實(shí)現(xiàn)：Void SelectSort(Node L)Int i,j,k;/分別為有序區(qū)，無序區(qū)，無序區(qū)最小元素指針For(i=0;i<length;i+)k=i;For(j=i+1;j<length;j+)If(Lj<Lk)k=j;If(k!=i

5、)/若發(fā)現(xiàn)最小元素，則移動(dòng)到有序區(qū)Int temp=Lk;Lk=Li;Li=Ltemp; 2.堆排序原理：利用大根堆或小根堆思想，首先建立堆，然后將堆首與堆尾交換，堆尾之后為有序區(qū)。要點(diǎn)：建堆、交換、調(diào)整堆實(shí)現(xiàn)：Void HeapSort(Node L)BuildingHeap(L);/建堆（大根堆）For(int i=n;i>0;i-)/交換Int temp=Li;Li=L0;L0=temp;Heapify(L,0,i);/調(diào)整堆Void BuildingHeap(Node L) For(i=length/2 -1;i>0;i-)Heapify(L,i,length);歸并排序原

6、理：將原序列劃分為有序的兩個(gè)序列，然后利用歸并算法進(jìn)行合并，合并之后即為有序序列。要點(diǎn)：歸并、分治實(shí)現(xiàn)：Void MergeSort(Node L,int m,int n)Int k;If(m<n)K=(m+n)/2;MergeSort(L,m,k);MergeSort(L,k+1,n);Merge(L,m,k,n);基數(shù)排序原理：將數(shù)字按位數(shù)劃分出n個(gè)關(guān)鍵字，每次針對一個(gè)關(guān)鍵字進(jìn)行排序，然后針對排序后的序列進(jìn)行下一個(gè)關(guān)鍵字的排序，循環(huán)至所有關(guān)鍵字都使用過則排序完成。要點(diǎn)：對關(guān)鍵字的選取，元素分配收集。實(shí)現(xiàn)：Void RadixSort(Node L,length,maxradix)In

7、t m,n,k,lsp;k=1;m=1;Int temp10length-1;Empty(temp); /清空臨時(shí)空間While(k<maxradix) /遍歷所有關(guān)鍵字For(int i=0;i<length;i+) /分配過程If(Li<m)Temp0n=Li;ElseLsp=(Li/m)%10; /確定關(guān)鍵字Templspn=Li;n+;CollectElement(L,Temp); /收集n=0;m=m*10;k+;C語言指針實(shí)現(xiàn)排序算法轉(zhuǎn)載C語言指針實(shí)現(xiàn)排序算法 相關(guān)知識(shí)介紹（所有定義只為幫助讀者理解相關(guān)概念，并非嚴(yán)格定義）：1、穩(wěn)定排序和非穩(wěn)定排序簡單地說就是所有

8、相等的數(shù)經(jīng)過某種排序方法后，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩(wěn)定的。反之，就是非穩(wěn)定的。比如：一組數(shù)排序前是a1,a2,a3,a4,a5，其中a2=a4，經(jīng)過某種排序后為a1,a2,a4,a3,a5，則我們說這種排序是穩(wěn)定的，因?yàn)閍2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩(wěn)定的了。2、內(nèi)排序和外排序在排序過程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲(chǔ)順序，稱為內(nèi)排序；在排序過程中，只有部分?jǐn)?shù)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱為外排序。3、算法的時(shí)間復(fù)雜度和空間復(fù)雜度所謂算法的時(shí)間復(fù)雜度，

9、是指執(zhí)行算法所需要的計(jì)算工作量。一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。=*/*=功能：選擇排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)=*/*=算法思想簡單描述：在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。 選擇排序是不穩(wěn)定的。算法復(fù)雜度O(n2)-n的平方=*/void select_sort(int *x, int n)int i, j, min, t;for (i=0; i<n-1; i+) /*要選擇的次數(shù)：0n-2共n-1次*/min =

10、i; /*假設(shè)當(dāng)前下標(biāo)為i的數(shù)最小，比較后再調(diào)整*/for (j=i+1; j<n; j+)/*循環(huán)找出最小的數(shù)的下標(biāo)是哪個(gè)*/if (*(x+j) < *(x+min) min = j; /*如果后面的數(shù)比前面的小，則記下它的下標(biāo)*/ if (min != i) /*如果min在循環(huán)中改變了，就需要交換數(shù)據(jù)*/t = *(x+i);*(x+i) = *(x+min);*(x+min) = t;/*=功能：直接插入排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)=*/*=算法思想簡單描述：在要排序的一組數(shù)中，假設(shè)前面(n-1) n>=2 個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第

11、n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。直接插入排序是穩(wěn)定的。算法時(shí)間復(fù)雜度O(n2)-n的平方=*/void insert_sort(int *x, int n)int i, j, t;for (i=1; i<n; i+) /*要選擇的次數(shù)：1n-1共n-1次*/*暫存下標(biāo)為i的數(shù)。注意：下標(biāo)從1開始，原因就是開始時(shí)第一個(gè)數(shù)即下標(biāo)為0的數(shù)，前面沒有任何數(shù)，單單一個(gè)，認(rèn)為它是排好順序的。*/t=*(x+i);for (j=i-1; j>=0 && t<*(x+j); j-) /*注意：j=i-1，j-，這里就是下標(biāo)

12、為i的數(shù)，在它前面有序列中找插入位置。*/*(x+j+1) = *(x+j); /*如果滿足條件就往后挪。最壞的情況就是t比下標(biāo)為0的數(shù)都小，它要放在最前面，j=-1，退出循環(huán)*/*(x+j+1) = t; /*找到下標(biāo)為i的數(shù)的放置位置*/*=功能：冒泡排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)=*/*=算法思想簡單描述：在要排序的一組數(shù)中，對當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。下面是一種改進(jìn)的冒泡算法，它記錄了每一遍掃描后最后下沉數(shù)的位置k

13、，這樣可以減少外層循環(huán)掃描的次數(shù)。冒泡排序是穩(wěn)定的。算法時(shí)間復(fù)雜度O(n2)-n的平方=*/void bubble_sort(int *x, int n)int j, k, h, t;for (h=n-1; h>0; h=k) /*循環(huán)到?jīng)]有比較范圍*/for (j=0, k=0; j<h; j+) /*每次預(yù)置k=0，循環(huán)掃描后更新k*/if (*(x+j) > *(x+j+1) /*大的放在后面，小的放到前面*/t = *(x+j);*(x+j) = *(x+j+1);*(x+j+1) = t; /*完成交換*/k = j; /*保存最后下沉的位置。這樣k后面的都是排序排

14、好了的。*/*=功能：希爾排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)=*/*=算法思想簡單描述：在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)節(jié)點(diǎn)，并且對插入下一個(gè)數(shù)沒有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。下面的函數(shù)是一個(gè)

15、希爾排序算法的一個(gè)實(shí)現(xiàn)，初次取序列的一半為增量，以后每次減半，直到增量為1。希爾排序是不穩(wěn)定的。=*/void shell_sort(int *x, int n)int h, j, k, t;for (h=n/2; h>0; h=h/2) /*控制增量*/for (j=h; j<n; j+) /*這個(gè)實(shí)際上就是上面的直接插入排序*/t = *(x+j);for (k=j-h; (k>=0 && t<*(x+k); k-=h)*(x+k+h) = *(x+k);*(x+k+h) = t;/*=功能：快速排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中起止元素

16、的下標(biāo)=*/*=算法思想簡單描述：快速排序是對冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過一趟掃描后，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長度可能只減少1。快速排序通過一趟掃描，就能確保某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。它是由C.A.R.Hoare于1962年提出的。顯然快速排序可以用遞歸實(shí)現(xiàn)，當(dāng)然也可以用?；膺f歸實(shí)現(xiàn)。下面的函數(shù)是用遞歸實(shí)現(xiàn)的，有興趣的朋友可以改成非遞歸的。快速排序是不穩(wěn)定的。最理想情況算法時(shí)間復(fù)雜度O(nlo

17、g2n)，最壞O(n2)=*/void quick_sort(int *x, int low, int high)int i, j, t;if (low < high) /*要排序的元素起止下標(biāo)，保證小的放在左邊，大的放在右邊。這里以下標(biāo)為low的元素為基準(zhǔn)點(diǎn)*/i = low;j = high;t = *(x+low); /*暫存基準(zhǔn)點(diǎn)的數(shù)*/while (i<j) /*循環(huán)掃描*/while (i<j && *(x+j)>t) /*在右邊的只要比基準(zhǔn)點(diǎn)大仍放在右邊*/j-; /*前移一個(gè)位置*/if (i<j) *(x+i) = *(x+j);

18、 /*上面的循環(huán)退出：即出現(xiàn)比基準(zhǔn)點(diǎn)小的數(shù)，替換基準(zhǔn)點(diǎn)的數(shù)*/i+; /*后移一個(gè)位置，并以此為基準(zhǔn)點(diǎn)*/while (i<j && *(x+i)<=t) /*在左邊的只要小于等于基準(zhǔn)點(diǎn)仍放在左邊*/i+; /*后移一個(gè)位置*/if (i<j)*(x+j) = *(x+i); /*上面的循環(huán)退出：即出現(xiàn)比基準(zhǔn)點(diǎn)大的數(shù)，放到右邊*/j-; /*前移一個(gè)位置*/*(x+i) = t; /*一遍掃描完后，放到適當(dāng)位置*/quick_sort(x,low,i-1); /*對基準(zhǔn)點(diǎn)左邊的數(shù)再執(zhí)行快速排序*/quick_sort(x,i+1,high); /*對基準(zhǔn)點(diǎn)右邊

19、的數(shù)再執(zhí)行快速排序*/*=功能：堆排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)=*/*=算法思想簡單描述：堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進(jìn)。堆的定義如下：具有n個(gè)元素的序列（h1,h2,.,hn),當(dāng)且僅當(dāng)滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,.,n/2)時(shí)稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)。完全二叉樹可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根，其它為左子樹、右子樹。初始時(shí)把要排序的數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹，調(diào)整它們的存儲(chǔ)順序

20、，使之成為一個(gè)堆，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最大。然后將根節(jié)點(diǎn)與堆的最后一個(gè)節(jié)點(diǎn)交換。然后對前面(n-1)個(gè)數(shù)重新調(diào)整使之成為堆。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對它們作交換，最后得到有n個(gè)節(jié)點(diǎn)的有序序列。從算法描述來看，堆排序需要兩個(gè)過程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。堆排序是不穩(wěn)定的。算法時(shí)間復(fù)雜度O(nlog2n)。*/*功能：滲透建堆輸入：數(shù)組名稱（也就是數(shù)組首地址）、參與建堆元素的個(gè)數(shù)、從第幾個(gè)元素開始*/void sift(int *x, int n, int s)int t, k, j;t = *(x+s); /*暫存開始元素*/k = s; /*開始元素下標(biāo)*/j = 2*k + 1; /*右子樹元素下標(biāo)*/while (j<n)if (j<n-1 && *(x+j) < *(x+j+1)/*判斷是否滿足堆的條件：滿足就繼續(xù)下一輪比較，否則調(diào)整。*/j+;if (t<*(x+j) /*調(diào)整*/*(x+k) = *(x+j);k = j; /*調(diào)整后，開始元素也隨之調(diào)整*/j = 2*k + 1;else /*沒有需要調(diào)整了，已經(jīng)是個(gè)堆了，退出循環(huán)。*/break;*(x+k) = t; /*開始元素放到它正確位置*/*功能