1、所謂排序，就是使一審記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。分類在計算機科學(xué)所使用的排序算法通常被分類為：計算的復(fù)雜度(最差、平均、和最好表現(xiàn))，依據(jù)申列(list)的大小(n)。一般而言，好的表現(xiàn)是Q(nlogn),且壞的行為是Q(n2)。對於一個排序理想的表現(xiàn)是O(n)。僅使用一個抽象關(guān)鍵比較運算的排序算法總平均上總是至少需要Q(nlogn)。記憶體使用量(以及其他電腦資源的使用)穩(wěn)定度：穩(wěn)定排序算法會依照相等的關(guān)鍵(換言之就是值)維持紀(jì)錄的相對次序。、也就是一個排序算法是穩(wěn)定的，就是當(dāng)有兩個有相等關(guān)鍵的紀(jì)錄R和S,且在原本的串列中R出現(xiàn)在S之前，在排序過的串列

2、中R也將會是在S之前。一般的方法：插入、交換、選擇、合并等等。交換排序包含(bubblesort)和(quicksort)。包含shakerNF序和(heapsort)。當(dāng)相等的元素是無法分辨的，比如像是整數(shù)，穩(wěn)定度并不是一個問題。然而，假設(shè)以下的數(shù)對將要以他們的第一個數(shù)字來排序。(4,1)(3,1)(3,7)(5,6)在這個狀況下，有可能產(chǎn)生兩種不同的結(jié)果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：(3,1)(3,7)(4,1)(5,6)(維持次序)(3,7)(3,1)(4,1)(5,6)(次序被改變)/不穩(wěn)定排序算法可能會在相等的鍵值中改變紀(jì)錄的相對次序,但是穩(wěn)定排序算法從來不

3、會如此。不穩(wěn)定排序算法可以被特別地時作為穩(wěn)定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件問之比較，就會被決定使用在原先資料次序中的條目，當(dāng)作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負(fù)擔(dān)。排列算法列表在這個表格中,n是要被排序的紀(jì)錄數(shù)量以及k是不同鍵值的數(shù)量。穩(wěn)定的冒泡排序(bubblesort)/O(n2)排序(Cocktailsort,雙向的冒泡排序)一O(n2)(insertionsort)O(n2)桶排序(bucketsort)O(n);需要O(k)額外記憶體計數(shù)排序(countingsort)O(n+k);需要O(n+k)額外記憶體(mer

4、gesort)O(nlogn);需要O(n)額外記憶體原地歸并排序一O(n2)排序(Binarytreesort)O(nlogn);需要O(n)額外記憶體鴿巢排序(Pigeonholesort)O(n+k);需要O(k)額外記憶體基數(shù)排序(radixsort)O(nk);需要O(n)額外記憶體GnomesortO(n2)LibrarysortO(nlogn)withhighprobability,需要(1+e)n額外記憶體不穩(wěn)定選擇排序(selectionsort)O(n2)/(shellsort)O(nlogn)如果使用最佳的現(xiàn)在版本/CombsortO(nlogn)堆排序(heapsort

5、)O(nlogn)/SmoothsortO(nlogn)快速排序(quicksort)O(nlogn)期望時間，O(n2)最壞情況；對於大的、亂數(shù)串列一般相信是最快的已知排序IntrosortO(nlogn)PatiencesortingO(nlogn+k)最外情況時間，需要額外的O(n+k)空問，也需要找至U最長白遞增子序歹！J(longestincreasingsubsequence)不實用的排序算法 TOC o 1-5 h z Bogo排序一O(nxn!)期望時間，無窮的最壞情況。StupidsortO(n3);遞回版本需要O(n2)額外記憶體BeadsortO(n)orO(Vn),但需

6、要特別的硬體PancakesortingO(n),但需要特別的硬體排序的算法排序的算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序算法。這里面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩(wěn)定；而后面三種排序相對于簡單排序?qū)臻g的要求稍高一點，但時間效率卻能穩(wěn)定在很高的水平?；鶖?shù)排序是針對關(guān)鍵字在一個較小范圍內(nèi)的排序算法。插入排序冒泡排序選擇排序快速排序堆排序歸并排序基數(shù)排序希爾排序插入排序插入排序是這樣實現(xiàn)的：首先新建一個空列表，用于保存已排序的有序數(shù)列(我們稱之為有序列表),從原數(shù)列中取出一個數(shù)，/將其插入“有序列表”中，使其仍舊保持有序

7、狀態(tài)。重復(fù)2號步驟/直至原數(shù)列為空。插入排序的平均為平方級的，效率不高，但是容易實現(xiàn)。它借助了逐步擴大成果”的思想，使有序列表的長度逐漸增加，直至其長度等于原列表的長度。冒泡排序冒泡排序是這樣實現(xiàn)的：首先將所有待排序的數(shù)字放入工作列表中。從列表的第一個數(shù)字到倒數(shù)第二個數(shù)字,逐個檢查：若某一位上的數(shù)字大于他的下一位，則將它與它的下一位交換。重復(fù)2號步驟，直至再也不能交換。冒泡排序的平均時間復(fù)雜度與插入排序相同，也是平方級的，但也是非常容易實現(xiàn)的算法。選擇排序選擇排序是這樣實現(xiàn)的：設(shè)數(shù)組內(nèi)存放了n個待排數(shù)字，數(shù)組下標(biāo)從1開始，到n結(jié)束。i=1從數(shù)組的第i個元素開始到第n個元素，尋找最小的元素。將上

8、一步找到的最小元素和第i位元素交換。/如果i=n1算法結(jié)束，否則回到第3步/選擇排序的平均時間復(fù)雜度也是O(n2)的?？焖倥判颥F(xiàn)在開始，我們要接觸高效排序算法了。實踐證明，快速排序是所有排序算法中最高效的一種。它采用了分治的思想：先保證列表的前半部分都小于后半部分，然后分別對前半部分和后半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序算法中，算法的高效與否與列表中數(shù)字問的比較次數(shù)有直接的關(guān)系，而保證列表的前半部分都小于后半部分就使得前半部分的任何一個數(shù)從此以后都不再跟后半部分的數(shù)進行比較了，大大減少了數(shù)字間不必要的比較。但查找數(shù)據(jù)得另當(dāng)別論了。堆排序堆排序與前面的算法都不同，它是這樣的：首先新建一個空列表，作用與插入排序中的“有序列表相同。找到數(shù)列中最大的數(shù)字，將其加在“有序列表的末尾，并將其從原數(shù)列中刪除。重復(fù)2號步驟，直至原數(shù)列為空。堆排序的平均時間復(fù)雜度為nlogn,效率高(因為有堆這種以及它奇妙的特征，使得找到數(shù)列中最大的數(shù)字”這樣的操作只需要0(1)的時間復(fù)雜度，維護需要logn的時間復(fù)雜度)，但是實現(xiàn)相對復(fù)雜(可以說是這里7種算法中比較難實現(xiàn)的)?？雌饋硭坪醵雅判蚺c插入