溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
排序的穩定性
因為待排序的記錄序列中可能存在兩個或兩個以上的關鍵字相等的記錄， 排序結果可能會存在不唯一的情況。所以就有穩定與不穩定的定義。
假設ki=kj( 1 =< i <= n,1 =< j <= n, i != j)，且在排序前的序列中ri領先于rj。如果排序后ri仍領先于rj，則稱所用的排序方法是穩定的;反之，若可能使得排序后的序列中rj領先于ri，則稱所用的排序方法是不穩定的。
只要有一組關鍵字發生類似情況，就可認為此排序方法是不穩定的。
內排序和外排序
根據在排序過程中待排序記錄是否全部放在內存中，排序分為內排序和外排序。
內排序是在排序整個過程中，待排序的所有記錄全部被放置在內存中。
外排序是由于排序的記錄個數太多，不能同時放置在內存中，整個排序過程需要在內外存之間多次交換數據才能進行。
對內排序來說，排序算法的性能主要有3個影響因素：
1、時間性能
排序算法的時間開銷是衡量其好壞的最重要的標志。
在內排序中，主要進行兩種操作：比較和移動。
高效率的內排序算法應該具有盡可能少的關鍵字比較次數和盡可能少的記錄移動次數。
2、輔助空間
評估算法的另一個主要標準是執行算法所需要的輔助存儲空間。
輔助存儲空間是除了存放待排序所占用的存儲空間外，執行算法所需要的其他存儲空間。
3、算法的復雜性
指算法本身的復雜性，過于復雜的算法也會影響排序的性能。
接下來本文介紹各種排序算法。
冒泡排序是一種交換排序，它的基本思想是：
兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。
算法復雜度分析：
使用優化后的冒泡排序，最好的情況下，僅需要n - 1次比較，時間復雜度為O(n);最壞情況下，需要n(n - 1)/2次比較和交換;
所以平均時間復雜度為O(n2)。
選擇排序的基本思想：
每一次遍歷時選取關鍵字最小的記錄作為有序序列的第i個記錄。
算法復雜度分析
簡單選擇排序最大的特點就是交換移動數據次數少，但它的比較次數是和數組本身是否有序是無關的，即無論最好最差的情況，都要進行n(n-1)/2次比較;在最好的情況下，不需要進行交換，在最壞的情況下，進行n-1次交換。
所以平均時間復雜度為O(n2)。
直接插入排序的基本操作：
將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄遞增1的有序表。
插入排序是進行值移動，而是不值交換。所以在量較小的情況下插入排序性能要優于冒泡和簡單選擇排序。
算法復雜度分析：
在最好的情況下，只需進行比較n - 1次，無需進行移動;
在最壞的情況下，比較(n + 2)(n - 1)/2次，交換(n + 4)(n - 1)/2次。
所以平均時間復雜度O(n2)
二分(折半)插入排序是一種在直接插入排序算法上進行小改動的排序算法。其與直接排序算法最大的區別在于查找插入位置時使用的是二分查找的方式，在速度上有一定提升。
算法復雜度分析：
插入每個記錄需要O(log i)比較，最多移動i+1次，最少2次。最佳情況O(n log n)，最差和平均情況O(n^2)。
總排序碼比較次數比直接插入排序的最差情況好得多，但比最好情況要差，所元素初始序列已經按排序碼接近有序時，直接插入排序比二分插入排序比較次數少
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。
希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了。
更好的理解方式
將數組列在一個表中并對行排序(用插入排序)。重復這過程，不過每次用更小的列來進行。最后整個表就只有一列了。
將數組轉換至表是為了更好地理解這算法，算法本身僅僅對原數組進行排序(通過增加索引的步長，例如是用i += step_size而不是i++)。
比如第一次放在5列中對每行使用快速排序排序，第二次放在3列中，最后放在1列中。類比于步長從5到3再到1。
算法復雜度分析
希爾排序的算法復雜度和增量序列有關，只要最終步長為1任何步長序列都可以工作。可以參加希爾排序。
堆
堆是具有下列性質的完全二叉樹：
每個節點的值都大于或等于其左右孩子節點的值，成為大頂堆;
每個節點的值都小于或等于其左右孩子節點的值，成為小頂堆;
完全二叉樹性質
按完全二叉樹的性質，該樹可以被順序存儲在數組中，按不同的角標進行表示。
即：
Parent(i) = (i-1)/2，i 的父節點下標
Left(i) = 2i + 1，i 的左子節點下標
Right(i) = 2(i + 1)，i 的右子節點下標
基本思想
將待排序的序列構造成一個大頂堆。此時，整個序列的最大值就是堆定的根節點，將它移走(與堆數組末尾元素交換)，再將剩余n-1個序列重新構造成一個堆，這樣就會得到第二大值，以此類推，就能得到一個有序序列了。
算法復雜度分析
在構建堆時，對每個非葉子節點來說，最多進行2次比較和互換操作，復雜度為O(n);
在進行排序時，第i次取堆頂記錄重新建堆需要用O(log i )時間，并需要取n-1次，所以重建堆的時間為O(nlogn)。
所以堆排序的時間復雜度為O(nlogn)。
實現步驟：
最大堆調整(Max_Heapify)：從堆的倒數第一個非葉子節點作調整，使得子節點永遠小于父節點。沒有必要從葉子節點開始，葉子節點可以看作是已符合堆特點的節點。
創建最大堆(Build_Max_Heap)：將堆所有數據重新排序
堆排序(HeapSort)：移除位在第一個數據的根節點，并做最大堆調整。
概念：
歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的典型應用。
它指的是將兩個已經排序的序列合并成一個序列的操作。歸并排序算法依賴歸并操作。歸并排序有多路歸并排序、兩路歸并排序 , 可用于內排序，也可以用于外排序。這里僅對內排序的兩路歸并方法進行討論。
算法思路
把 n 個記錄看成 n 個長度為 l 的有序子表
進行兩兩歸并使記錄關鍵字有序，得到 n/2 個長度為 2 的有序子表
重復第 2 步直到所有記錄歸并成一個長度為 n 的有序表為止。
算法復雜度分析：
在最后一步，需要依次遍歷兩個已排序的好的數組，此時的時間復雜度為O(n)。
同時又進行著二路歸并，形成一顆完全二叉樹，此時整個排序需要進行log2n次。
所以歸并排序的時間復雜度為O(nlogn)。這是它的最好、最壞、平均的時間性能。
基本思想
通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分小，則可分別對這兩部分記錄繼續進行排序，直到整個序列有序。
復雜度分析
最好情況：partition每次劃分的都很均勻，如果排序n個關鍵字，其遞歸樹的深度就為floor(log2n)+ 1次，此時的復雜度為O(nlogn)。
如果是最壞情況，每次partition都只操作一個數字，該遞歸樹即為一顆斜樹，比較次數為n(n - 1)/2，時間復雜度為O(n2)。
平均復雜度為O(nlogn)。
基本思想
工作的原理是將數組分到有限數量的桶里。每個桶再個別排序(有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序)。
步驟
設置一個定量的數組當作空桶子。
尋訪序列，并且把項目一個一個放到對應的桶子去。
對每個不是空的桶子進行排序。
從不是空的桶子里把項目再放回原來的序列中。
算法復雜度
對于N個待排數據，M個桶，平均每個桶[N/M]個數據的桶排序平均時間復雜度為：
O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-N*logM)
可以看出，最好情況即當N=M時，每個桶只有一個數據時，能夠達到O(N)。
基本思想
計數排序是一種穩定的線性時間排序算法。
計數排序使用一個額外的數組C，其中C數組的第i個元素是待排序數組A中值等于i的元素的個數。然后根據數組C來將A中的元素排到正確的位置。
步驟：
找出待排序的數組中最大和最小的元素
統計數組中每個值為i的元素出現的次數，存入數組 C 的第 i 項
對所有的計數累加(從C中的第一個元素開始，每一項和前一項相加)
反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1
算法復雜度分析
當輸入的元素是n個0到k之間的整數時，它的運行時間是Θ(n + k)。計數排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來計數的數組C的長度取決于待排序數組中數據的范圍(等于待排序數組的最大值與最小值的差加上1)，這使得計數排序對于數據范圍很大的數組，需要大量時間和內存。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
