十大排序算法

1、十大排序算法自己根據(jù)算法思想，自己編程實(shí)現(xiàn)十大排序算法，當(dāng)然其中也有借鑒別人的地方，所有的程序都是自己經(jīng)過(guò)檢驗(yàn)測(cè)試沒(méi)有問(wèn)題才放出來(lái)的。一 算法介紹1 選擇排序選擇排序的思想就是：從當(dāng)前數(shù)中選出一個(gè)最大或者最小的值排在最前面，然后從剩下的數(shù)中選出剩下數(shù)的最值排在已經(jīng)排序的數(shù)的后面，算法時(shí)間復(fù)雜度O(n2)，在實(shí)際工作中這種排序算法不可取。2 冒泡排序冒泡排序的思想就是：比如說(shuō)要升序排列，那么就依次相鄰兩個(gè)數(shù)比較大小，然后把大的數(shù)放在后面，依次類推。冒泡排序時(shí)間復(fù)雜度O(n2)，在實(shí)際工作中這種排序算法不可取。3 插入排序插入排序思想就是：依次遍歷數(shù)組，假設(shè)前面已經(jīng)有一部分排過(guò)序的，當(dāng)前待排數(shù)字跟

2、前面的數(shù)字依次比較大小，將其插在對(duì)應(yīng)順序位置，算法時(shí)間復(fù)雜度O(n2)，在實(shí)際工作中這種排序算法不可取。4 希爾排序希爾排序的思想就是：希爾排序是對(duì)插入排序的改進(jìn)，可以把當(dāng)前數(shù)據(jù)分組，每個(gè)分組都有一定間隔，比如說(shuō)原來(lái)數(shù)組的小標(biāo)范圍是0,1,2,3,4,5,6,7,8,9.我們把它們分成兩組，0-4一組，5-9一組，這樣的話，間隔就是5，我們令0,5,；1,6；2,7；3,8；4,9,它們兩兩比較大小。然后再減小間隔范圍，或者說(shuō)增多分組個(gè)數(shù)，比如此時(shí)，間隔為2，那么比較下標(biāo)為0,2,4,6,8的大小，然后比較下標(biāo)為1,3,5,7,9的大小。到最后間隔變?yōu)?，就變成了完全的插入排序了。希爾排序的算

3、法時(shí)間復(fù)雜度O(n2)。5 快速排序快速排序利用分治的思想，在數(shù)組中設(shè)置一個(gè)游標(biāo)，從數(shù)組的兩端來(lái)遍歷數(shù)組，將元素和游標(biāo)相比，意圖達(dá)到兩組數(shù)據(jù)一邊游標(biāo)小，一邊比游標(biāo)大。那么此時(shí)的游標(biāo)就處于兩組數(shù)組的中間。然后依次對(duì)前后兩組數(shù)據(jù)排序，此時(shí)當(dāng)然可以利用遞歸了。時(shí)間平均復(fù)雜度是O(n*logn)，排序算法貌似是公認(rèn)最實(shí)用最好的排序算法，在大多數(shù)情況下都能解決問(wèn)題，提高效率，當(dāng)然也有糟糕的時(shí)候，此時(shí)的算法時(shí)間復(fù)雜度達(dá)到O(n2)。6 歸并排序歸并排序的思想就是把數(shù)組分成兩組，前后兩組分別排序，兩組排完序后再把兩組合并起來(lái)，當(dāng)然可以利用遞歸的思想來(lái)實(shí)現(xiàn)歸并排序，算法時(shí)間復(fù)雜度是O(n*logn)。7 堆排

4、序首先說(shuō)明什么是堆，堆其實(shí)就一個(gè)二叉樹(shù)，其中要滿足父節(jié)點(diǎn)大于或者小于子節(jié)點(diǎn)。把數(shù)組中元素按照堆來(lái)遍歷，修正堆后，那么最大或者最小的元素就在根節(jié)點(diǎn)上了。我們把根節(jié)點(diǎn)移除，按照相同的方法再次得到最值，依次類推，直到剩下一個(gè)元素位置。算法時(shí)間復(fù)雜度是O(n*logn)。8 基數(shù)排序基數(shù)排序和后面要說(shuō)的計(jì)數(shù)排序，桶排序都是非比較排序，因此他們能夠突破比較排序的時(shí)間上限O(n*logn)，達(dá)到時(shí)間復(fù)雜度為)O(n)的程度，但是這幾種排序都有限制性條件，不能看到他們的時(shí)間復(fù)雜付貌似比別的低一個(gè)等級(jí)就覺(jué)得他們是最好的排序算法了。三者的思想類似，都是用到了桶的概念?；鶖?shù)排序針對(duì)的是非負(fù)整數(shù)，將所有的數(shù)字依次比

5、較個(gè)位，十位，百位，直到最高位，每一次比較都能得到一個(gè)排序，由于越往高位，這個(gè)位上數(shù)字影響權(quán)重越大，所以能夠起到對(duì)前面順序的修正。9 計(jì)數(shù)排序計(jì)數(shù)排序的思想也很簡(jiǎn)單，就是針對(duì)所有的整數(shù)。取一個(gè)從最小值到最大值的間隔，然后遍歷數(shù)組，把當(dāng)前元素放在下標(biāo)為（當(dāng)前元素值 - 最小值）的位置。是不是很簡(jiǎn)單啊，編程玩的就是思想，沒(méi)有思想的程序員就不是真正的程序員。10 桶排序說(shuō)到最后最后終于說(shuō)到桶排序了。桶排序的思想就是先把數(shù)據(jù)分成一個(gè)個(gè)分組，這一個(gè)個(gè)分組就是一個(gè)個(gè)桶，當(dāng)然這些桶是有順序的，要不然桶排序作為非比較排序算法，連唯一的順序都沒(méi)有并且也不比較還排什么序啊。對(duì)于首次分桶后的數(shù)據(jù)可以采用遞歸或者其他

6、的排序算法實(shí)現(xiàn)對(duì)每個(gè)桶內(nèi)數(shù)據(jù)排序。最后按照桶號(hào)將所有數(shù)據(jù)依次連接就是拍完順序的數(shù)據(jù)了。二 算法實(shí)現(xiàn)常言道光說(shuō)不練假把式，這里肯定要把實(shí)現(xiàn)代碼貼出來(lái)了。1 選擇排序void selectsort(int *pData,int left,int right)int i,j,temp;int tb;for(i=left;i<right-1;i+)temp = i;for(j=i+1;j<right;j+)if(pDataj<pDatatemp)temp = j;if(i != temp )tb = pDatatemp;pDatatemp = pDatai;pDatai = tb;2

7、 冒泡排序void bubblesort(int *pData,int left,int right)int i,j;int temp;for(i=left;i<right-1;i+)for(j=left;j<right-i-1;j+)if(pDataj+1<pDataj)temp = pDataj+1;pDataj+1 = pDataj;pDataj = temp;3 插入排序void insertsort(int *pData,int left,int right)int i,j;int temp;for(i=left+1;i<right;i+)temp = pDa

8、tai;j = i;while(-j>=left && pDataj>temp)pDataj+1 = pDataj;pDataj+1 =temp;4 希爾排序void shellsort(int *pData,int left,int right)int i,j,gap;int temp;for(gap=right/2;gap>0;gap/=2)for(i=gap;i<right;i+)temp = pDatai;for(j=i-gap;(j>=0)&&pDataj>temp;j-=gap)pDataj+gap = pData

9、j;pDataj+gap = temp;5 快速排序三種實(shí)現(xiàn)方式（1）游標(biāo)為最左邊元素void quicksort(int *pData,int left,int right) int i,j,middle,temp; middle = pDataleft; i = left + 1; j = right - 1; do  while( i<right && pDatai<middle)   i+;  while( j>left &&

10、amp; pDataj>middle)   j-;  if(i >= j)   break;  temp = pDatai;  pDatai = pDataj;  pDataj = temp;  i+;  j-; while(i<=j); pDataleft = pDataj; pDataj = middle; if(left<j-1) 

11、60;quicksort(pData,left,j); if(right>j+1)  quicksort(pData,j+1,right);（2）游標(biāo)為中間元素void quicksort2(int *pData,int left,int right)int i,j,middle,temp;i = left;j = right - 1;middle = pData(i + j)/2;dowhile(i<right && pDatai<middle)i+;while(j>left && pDataj>mi

12、ddle)j-;if(i>=j)break;temp = pDatai;pDatai = pDataj;pDataj = temp;i+;j-;while(i<j);if(left<i-1)quicksort2(pData,left,i);if(right>i+2)quicksort2(pData,i,right);（3）游標(biāo)為最后元素 void quicksort3(int *pData,int left,int right)int i,j,last;int temp,end;i = left;j = left;last = right - 1;end =

13、pDatalast;/分配初始的i，jif(pDataleft<end)while( pData+j<end );if(j = last)quicksort3(pData,left,right-1);return;elsei = j-1;elsewhile( pData+j>end );temp = pDataj;pDataj = pDataleft;pDataleft = temp;if(j = last)quicksort3(pData,left+1,right);return;/分治排序while(j<last-1)j+;if(pDataj<end)temp

14、 = pDataj;pDataj = pData+i;pDatai = temp;temp = end;pDatalast = pDatai+1;pDatai+1 = temp;if(left<i)quicksort3(pData,left,i+1);if(right>i+3)quicksort3(pData,i+2,right);6 歸并排序（1）遞歸法實(shí)現(xiàn)void mergesort2(int *pData,int *Des,int left,int right)int first = left;int last  = right-1;if(first<last

15、)int mid = (first + last)/2;mergesort2(pData,Des,first,mid+1);mergesort2(pData,Des,mid+1,right);merges(pData,Des,first,mid,last);void merges(int *pData,int *Des,int first,int mid,int last)int i = first;int j = mid + 1;int k = first;while(i<=mid&&j<=last)if(pDatai<pDataj)Desk+ = pDat

16、ai+;elseDesk+ = pDataj+;while(i<=mid)Desk+ = pDatai+;while(j<=last)Desk+ = pDataj+;for(k=first;k<=last;k+)pDatak = Desk; （2）非遞歸法實(shí)現(xiàn)void mergesort3(int *list,int length)int i, left_min, left_max, right_min, right_max, next;    int *tmp = (int*)malloc(sizeof(int) * length); 

17、;   if (tmp = NULL)        fputs("Error: out of memoryn", stderr);        abort();        for (i = 1; i < length; i *= 2)            for (left_min = 0; left_min < length - i; left_min = rig

18、ht_max)                 right_min = left_max = left_min + i;                right_max = left_max + i;                if (right_max > length)        

19、0;               right_max = length;                next = 0;                while (left_min < left_max && right_min < right_max)           

20、            tmpnext+ = listleft_min > listright_min ? listright_min+ : listleft_min+;                while (left_min < left_max)                        list-right_m

21、in = list-left_max;                while (next > 0)                        list-right_min = tmp-next;                free(tmp); 7 堆排序void HeapAdjust(int

22、 array, int i, int nLength)int nchild;int ntemp;while(i>=0)nchild = 2 * i + 1;ntemp = arrayi;if (arraynchild<ntemp)ntemp = arraynchild;arraynchild = arrayi;arrayi = ntemp;if (nchild < nLength - 1)nchild+;if (arraynchild<ntemp)ntemp = arraynchild;arraynchild = arrayi;arrayi = ntemp;i-;/ 堆

23、排序算法void HeapSort(int array,int length)int i,temp;for (int nL = length; nL>0;nL-)i = nL/2 - 1;HeapAdjust(array,i,nL);temp = array0;array0 = arraynL-1;arraynL-1 = temp;8 基數(shù)排序#include <iostream>using namespace std;const int base=10;struct wxint num;wx *next;wx()next=NULL;wx *headn,*curn,*boxb

24、ase,*curboxbase;void basesort(int t)int i,k=1,r,bn;/ k,r 分別表示10的冪次方，用來(lái)得到相應(yīng)位上的單個(gè)數(shù)字，比如 k=10，r=100，數(shù)字207，則 十位上 0 = /(207/r)%10 for(i=1;i<=t;i+)k*=base;r=k*base;/curbox和box中的指針指向相同的位置，當(dāng)curbox中有新元素時(shí)，curbox指向會(huì)發(fā)生變化，形成box元素為/頭指針，curbox元素相當(dāng)于滑動(dòng)指針，這樣可以通過(guò)比較兩者的不同來(lái)判斷指針的走向。for(i=0;i<base;i+)curboxi

25、=boxi; for(curn=headn->next;curn!=NULL;curn=curn->next)                 bn=(curn->num%r)/k;               / bn表示元素相應(yīng)位上的值，curboxbn->ne

26、xt=curn;             /curboxi的next指向相應(yīng)位為i的元素curboxbn=curboxbn->next;    /此時(shí)curboxi向后移位，以boxi為首的鏈表長(zhǎng)度增加curn=headn;for(i=0;i<base;i+)if(curboxi!=boxi)curn->next=boxi->next;curn=curboxi;    &#

27、160;   /curn此時(shí)指向了在box中具有相同值的鏈表的最后一個(gè)，例如 123，/33，783，67，56，在3開(kāi)頭的 元素鏈表中，此時(shí)cur指向了783。curn->next=NULL;void printwx()for(curn=headn->next;curn!=NULL;curn=curn->next)cout<<curn->num<<' 'cout<<endl;int main()int i,n,z=0,maxn=0;curn=headn=new wx;cin>>n;fo

28、r(i=0;i<base;i+)curboxi=boxi=new wx;for(i=1;i<=n;i+)curn=curn->next=new wx;cin>>curn->num;maxn=max(maxn,curn->num);while(maxn/base>0)maxn/=base;z+;for(i=0;i<=z;i+)basesort(i);printwx();return 0; 9 計(jì)數(shù)排序void CountSort(int array,int nLength)int nMin,nMax;nMin = INT_MAX;n

29、Max = 0;for(int i=0;i<nLength;i+)if (nMax<arrayi)nMax = arrayi;if (nMin>arrayi)nMin = arrayi;int nSize = nMax - nMin + 1;int *Count = NULL;int *Sort  = NULL;Count = (int *)malloc( sizeof(int) * nSize );Sort  = (int *)malloc( sizeof(int) * nLength);int j;for (j=0;j<nSize;j+)Coun

30、tj  = 0;for (j=0;j<nLength;j+)Countarrayj - nMin+;for (j=0;j<nSize-1;j+)Countj+1 += Countj;for (j=nLength-1;j>=0;j-)SortCount arrayj-nMin -1 = arrayj;Countarrayj - nMin-;for (j=0;j<nLength;j+)arrayj = Sortj;free(Count);free(Sort); 10 桶排序 /文件1#ifndef D_BUCKET_H#define D_BUC

31、KET_H#include<cstdlib>#include<climits>using namespace std;void BucketSort(int array,int nLength,int nDivide);struct bucketint key;bucket *next;#endif/文件2#include"bucket.h"void BucketSort(int arr,int nLength,int nDivide)bucket *Box = (bucket*)malloc( sizeof(bucket*) * nDivide )

32、;for(int i =0;i<nDivide;i+)Boxi = (bucket*)malloc( sizeof(bucket) );Boxi->key = 0;Boxi->next = NULL;/ Find the Max and Min in the arrayint nMin = INT_MAX;int nMax = INT_MIN;int nPie,nLeft;for(int i = 0;i<nLength;i+)nMin = (nMin<arri)?nMin:arri;nMax = (nMax>arri)?nMax:arri;nLeft = (

33、nMax - nMin + 1) % nDivide;if(nLeft = 0)nPie = (nMax - nMin + 1) / nDivide;elsenPie = (nMax - nMin + 1) /(nDivide - 1);/Insert the element in bucketfor(int i = 0;i<nLength;i+)bucket *node = (bucket*)malloc(sizeof(bucket);node->key = arri;node->next = NULL;int nId = (arri - nMin) / nPie;if(BoxnId->key = 0)BoxnId->next = node;BoxnId->key+;elsebucket *p = BoxnId->next;bucket *cu