本文旨在介紹排序的基礎知識和相關概念，為後續章節做鋪墊。

排序（sorting）的功能是将一個數據元素的任意序列，重寫排列成一個按關鍵字有序的序列。其确切的定義為：假設有n個數據元素的序列（R1，R2.，。。。，Rn），其相應關鍵字的序列是（K1，K2，。。。，Kn）。通過排序要求找出下标1，2，。。。，n的一種排列p1，p2，。。。，pn，使得相應關鍵字滿足如下的非遞減（或非遞增）關系Kp 1<= Kp 2 <=…<= Kp n這樣，就得到一個按關鍵字有序的記錄序列：（Rp1，Rp2，。。。，Rpn）

整個排序過程在内存儲器中進行，稱為内部排序。以下介紹的都是内部排序。我們常見的排序都是内部排序。

由于待排序元素數量太大，以至于内存儲器無法容納全部數據，排序需要借助外存儲設備才能完成，這類排序稱為外部排序。

如果在待排序的序列中存在多個具有相同關鍵字的元素，假設Ki = Kj（1<=i<=n,1<=j<=n,i != j),若在排序之前的序列中Ri在Rj之前，經過排序後得到的序列中Ri仍然在Rj之前，則稱所用的排序方法是穩定的；否則，當相同關鍵字元素的前後關系在排序中發生變化，則稱所用的排序方法是不穩定的。

簡單地說，如果A=B，排序前A在B之前，排序結束後A還在B之前，排序就穩定，反之不穩定。

例如：有數據

原始數據

若排序後得到結果

穩定排序結果

則稱該排序方法是穩定的

若排序後得到結果

不穩定排序結果

則稱該排序方法是不穩定的。

無論是穩定的還是不穩定的排序方法，均能完成排序的功能。在某些場合可能對排序有穩定性的要求，此時就應當選擇穩定的排序方法。

大部分排序都是需要通過比較來判斷大小，作為排序的依據的。但是也有例外的，比如計數排序、基數排序、不需要進行比較。

插入排序：将無序子序列中的多個記錄"插入"到有序序列中，從而增加記錄的有序子序列的長度。（詳見學習筆記-詳解直接插入排序，學習筆記-詳解希爾排序）

交換排序：通過"交換"無序序列中的記錄從而得到其中關鍵字最小或最大的記錄，并将它加入到有序子序列中，以此方法增加記錄的有序子序列長度。（詳見學習筆記-詳解冒泡排序，學習筆記-詳解快速排序）

選擇排序：從記錄的無序子序列中"選擇"關鍵字最小或最大的記錄，并将它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。（詳見學習筆記-詳解簡單選擇排序，學習筆記-詳解堆排序）

歸并排序：通過"歸并"兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。（詳見學習筆記-詳解歸并排序）

此外還有基數排序，計數排序。（詳見學習筆記-詳解基數排序，學習筆記-詳解計數排序）

分為和。其作用： 是指執行算法所需要的計算工作量；而是指執行這個算法所需要的空間。（算法的複雜性體運行該算法時的計算機所需資源的多少上，資源最重要的是時間和空間（即）資源，因此複雜度分為時間和空間複雜度。）一個算法的優劣主要從算法的執行時間和所需要占用的存儲空間兩個方面。

對于一個算法，其和空間複雜度往往是相互影響的。當追求一個較好的時間複雜度時，可能會使空間複雜度的性能變差，即可能導緻占用較多的存儲空間；反之，當追求一個較好的空間複雜度時，可能會使時間複雜度的性能變差，即可能導緻占用較長的運行時間。另外，算法的所有性能之間都存在着或多或少的相互影響。因此，當設計一個算法(特别是大型算法)時，要綜合考慮算法的各項性能，算法的使用頻率，算法處理的數據量的大小，算法描述語言的特性，算法運行的機器系統環境等各方面因素，才能夠設計出比較好的算法。

在中，時間複雜性，又稱時間複雜度，的時間複雜度是一個，它定性描述該算法的運行時間。這是一個代表算法輸入值的的長度的函數。時間複雜度常用表述，不包括這個函數的低階項和首項系數。使用這種方式時，時間複雜度可被稱為是的，亦即考察輸入值大小趨近無窮時的情況。

常數時間：若對于一個算法，T(n)的上界與輸入大小無關，則稱其具有常數時間，記作 O(1)時間。如果 T(n) =O(c)，其中 c是一個常數，這記法等價于标準記法 T(n) =O(1)

對數時間:若算法的T(n) =O(logn)，則稱其具有對數時間。由于計算機使用的記數系統，常常以2為底（即log2n，有時寫作lgn）。然而，由對數的，logan和logbn隻有一個常數因子不同，這個因子在大O記法中被丢棄。因此記作O（logn），而不論對數的底是多少，是對數時間算法的标準記法。

常見的具有對數時間的算法有的相關操作和二分搜索。

線性時間:如果一個算法的時間複雜度為O(n)，則稱這個算法具有線性時間，或O(n)時間。非正式地說，這意味着對于足夠大的輸入，運行時間增加的大小與輸入成線性關系。

線性對數時間：若一個算法時間複雜度T(n) = O(nlog n)，則稱這個算法具有線性對數時間。因此，從其表達式我們也可以看到，線性對數時間增長得比線性時間要快，但是對于任何含有n，且n的幂指數大于1的多項式時間來說，線性對數時間卻增長得慢。

空間複雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接的空間複雜度是O(1) 。而一般的算法就要有O(n)的空間複雜度了，因為每次遞歸都要存儲返回信息。

此處不過多贅述，後續将為大家一一介紹。

本文的初衷為學習筆記的分享，部分圖文來源于網絡，如侵，聯删。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!