最常用的排序算法總結(jié)實際應(yīng)用中最常用的排序是快速排序和堆排序。所謂堆排序，就是將最小的一個值放到堆棧的頂部，這樣就可以使最后出來的數(shù)完成排序?？焖倥判蚴遣环€(wěn)定的，堆排序是穩(wěn)定的。所謂穩(wěn)定，就是當(dāng)兩個值相等時，排序后兩個值的順序和排序前相同。以上兩種排序使用的范圍和情況是不同的，一般對于自然生成序列排序使用快速排序效率比較高，而對于已經(jīng)有一定順序的序列，使用堆排序比較合適，而且穩(wěn)定的。這里主要總結(jié)常用的5種排序，分別是快速排序，冒泡排序(也叫交換排序)，選擇排序，shell排序,插入排序。下邊分別介紹：1快速排序，就是從一個序列中隨意取一個數(shù)，然后對剩下的數(shù)進行分類，小的放到左邊，大的放到右邊。如此進行下去知道最后。N(n-l)/2.空間復(fù)雜度是o(n).2冒泡排序，就是從第一個數(shù)開始和后一個數(shù)比較，然后依情況交換,然后再用第二個和第三個比較交換，如此反復(fù)，直到最后一個。一直進行n輪就可以完成排序。3選擇排序，就是將一個序列中的最小的放到第一個，然后再將剩下的數(shù)據(jù)用相同的方式分別放到后一位。它的空間復(fù)雜度是0(1).4shell排序，就是將有一定間隔的數(shù)進行排序，并且間隔變小,也就是開始是n/2,然后繼續(xù)變小，一般都是以一半為標準，直到最后間隔只有2,也就完成了排序。需要的空間復(fù)雜度是0(1).5插入排序，就比如平時玩的撲克排，一般整理排的時候需要將排排序，當(dāng)你拿到一張新排的時候，就要比較左邊和右邊，只有在左右中間的那個值的時候才說明排序成功。它需要的空間復(fù)雜度也是0(1).Ps:空間復(fù)雜度就是需要另外占用的空間。以上排序中，只有快速排序是O(n),其他都是0(2),因為只有快速排序需要另外再起存儲空間，而其他都是在原來空間中增加一個空間就可以。1,快速排序這個有點難解釋，感覺上就是紐來紐去,先從首記錄開始也行，從未記錄開始也行，以后補上.TonyHoare在1962年首次提出了快速排序算法。對快速排序方法的研究表明，至今快速排序算法仍然是流傳久遠的最實用的排序算法。只在輸入數(shù)據(jù)項有更詳細的信息時，其它排序算法才可能勝過快速排序算法?？焖倥判蛩惴ㄊ抢梅种渭夹g(shù)的典型例子，隨機分治策略是設(shè)計組合優(yōu)化與計算幾何一類問題有效算法的基礎(chǔ)。分治策略分為三步：將問題分成若干大小基本相等的子問題；獨立地解決這些子問題；將子問題歸并成原問題的解?？焖倥判虻幕舅悸肥牵菏紫任覀冞x擇一個中間值middle(程序中我們可使用數(shù)組中間值)，把比中間值小的放在其左邊，比中間值大的放在其右邊。由于這個排序算法較復(fù)雜，我們先給出其進行一次排序的程序框架(從各類數(shù)據(jù)結(jié)構(gòu)教材中可得)：voidQuickSort(int*pData,intleft,intright){inti,j;intmiddle,iTemp;i二left;j二right;middle二pData[(left十right)/2];〃求中間值do{while((pData[i]middle)(iright))〃從左掃描大于中值的數(shù)i十十；while((pDataDJmiddle)(jleft))〃從右掃描小于中值的數(shù)j-■if(i二j)〃找到了一對值{〃交換iTemp二pData[i];pData[i]二pData[j];pDatafj]二iTemp;i十十;j_-;}}while(i二j);〃如果兩邊掃描的下標交錯，就停止(完成一次)〃當(dāng)左邊部分有值(left<j),遞歸左半邊></j),遞歸左半邊〉if(left<j)></j)>Quicksort(pDataJeftj);〃當(dāng)右邊部分有值(righti),遞歸右半邊if(righti)Quicksort(pData.i,right);}由此可見，上述排序算法中采用了遞歸策略。在我設(shè)定的一個杯林個無序記錄集中快速排序比冒炮節(jié)省了差不多一半時間，估計記錄越多,這個數(shù)量級會更高.2,選擇排序，選擇排序和冒泡如果不仔細看，光從字面解釋,很多人都弄混，解釋這個很簡單，舉個例子就行.如:2,6丄4首先將2和所有記錄遍歷，找出比他小的交換位置，于是(第一個記錄)1.6.2.4第二次將6遍歷,找出小的交換(第二個記錄)1.2.6.4第三次......1,2,4,6完成！3冒泡這個就更加簡單理解兩兩相互之間比較，大(或者小的)放到前面，但必須遍歷N-1次.感覺上如果是無序的記錄讓他遍歷效率會高.女11,2,6,1,42,1,4,6(小的交換后繼續(xù)和后面的記錄交換)1.2,4.6完成(N-1次???好象是說選擇排序了，忘記了.)數(shù)據(jù)量少的時候可以用冒泡，某些人說過冒泡效率最低當(dāng)然還有改良的冒泡雙璉算法.voidCTestDlg::BubbleSort(int*pData,intiNum)//冒泡{inti,j;inttemp;for(i=iNum-l;ii--)//iNum-1次for(j=0;j<i;j++){<px/i；j++)>if(pData[j]pDataO+l]){temp=pData|j];pData[j]=pData[j+l];pData[j+l]二temp;}}}4插入排序?qū)⒌谝粋€記錄看成己經(jīng)排好的序列，其次數(shù)據(jù)一個一個與之前最大的記錄比較，子成序列,聽說是如果有序的記錄集合排序效果好.voidCTestDlg::insert_sort(int*list,intlength){inti,j,temp;for(i二1;ilength;i十十){temp=list[i];j=i-1;while((list[j]temp)(j二0)){listD+l]=list[j]；j-；}list0+1]二temp;//show」ist(list,length);}}各種排序算法的比較(轉(zhuǎn))2008-07-3009:121.穩(wěn)定性比較插入排序、冒泡排序、二叉樹排序、二路歸并排序及其他線形排序是穩(wěn)定的選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的2.時間復(fù)雜性比較插入排序、冒泡排序、選擇排序的時間復(fù)雜性為O(n2)其它非線形排序的時間復(fù)雜性為O(nlog2n)線形排序的時間復(fù)雜性為O(n);3?輔助空間的比較線形排序、二路歸并排序的輔助空間為0("其它排序的輔助空間為0(2);4?其它比較插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。反而在這種情況下，快速排序反而慢了。當(dāng)n較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序。若待排序的記錄的關(guān)鍵字在一個明顯有限范圍內(nèi)時，且空間允許是用桶排序。當(dāng)n較大時，關(guān)鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序。當(dāng)n較大時，關(guān)鍵字元素可能出現(xiàn)本身是有序的，對穩(wěn)定性