線性時間排序演算法

1. 下列屬於線性時間的排序演算法是： （ ） A.冒泡排序 B.選擇排序 C.桶排序 D.快速排序

下列屬於線性時間的排序演算法是：C.桶排序

2. 排序演算法總結

排序演算法是什麼?有多少種?排序演算法總結又是怎樣?以下是為您整理的排序演算法總結，供您參考!

【排序演算法總結】

排序演算法：一種能將一串數據依照特定的排序方式進行排列的一種演算法。

排序演算法性能：取決於時間和空間復雜度，其次還得考慮穩定性，及其適應的場景。

穩定性：讓原本有相等鍵值的記錄維持相對次序。也就是若一個排序演算法是穩定的，當有倆個相等鍵值的記錄R和S，且原本的序列中R在S前，那麼排序後的列表中R應該也在S之前。

以下來總結常用的排序演算法，加深對排序的理解。

冒泡排序

原理

倆倆比較相鄰記錄的排序碼，若發生逆序，則交旅派配換;有倆種方式進行冒泡，一種是先把小的冒泡到前邊去，另一種是把大的元素冒泡到後邊。

性能

時間復雜度為O(N^2)，空間復雜度為O(1)。排序是穩定的，排序比較次數與初始序列無關，但交換次數與初始序列有關。

優化

若初始序列就是排序好的，對於冒泡排序仍然還要比較O(N^2)次，但無交換次數。可根據這個進行優化，設置一個flag，當在一趟序列中沒有發生交換，則該序列已排序好，但優化後排序的時間復雜度沒有發生量級的改變。

代碼

插入排序

原理

依次選擇一個待排序的數據，插入到前邊已排好序的序列中。

性能

時間復雜度為O(N^2)，空間復雜度為O(1)。演算法是穩定的，比較次數和交換次數都與初始序列有關。

優化

直接插入排序每次往前插入時，是按順序依次往前找，可在這里進行優化，往前找合適的插入位置時採用二分查找的方式，即折半插入。

折半插入排序相對直接插入排序而言：平均性能更快，時間復雜度降至O(NlogN)，排序是穩定的，但排序的比較次數與初始序列無關，總是需要foor(log(i))+1次排序比較。

使用場景

當數據基本有序時，採用插入排序可以明顯減少數據交換和數據移動次數，進而提升排序效率。

代碼

希爾排拆指序

原理

插入排序的改進版，是基於插入排序的以下倆點性質而提出的改進方法：

插入排序對幾乎已排好序的數據操作時，效率很高，可以達到線性排序的效率。

但插入排序在每次往前插入時只能將數據移動一位，效率比較低。

所以希爾排序的思想是：

先是取一個合適的gap

縮小間隔gap，例如去gap=ceil(gap/2)，重復上述子序列劃分和排序

直到，最後gap=1時，將所有元素放在同一個序列中進行插入排序為止。

性能

開始時，gap取值較大，子序列中的元素較少，排序速度快，克服了直接插入排序的缺點;其次，gap值逐漸變小後，雖然子序列的元素逐漸變多，但大多元素已基本有序，所以繼承了直接插入排序的優點，能以近線性的速度排好序。

代碼

選擇排序

原理

每次從未排序的序列中找到最小值，記錄並最後存放到已排序序羨碰列的末尾

性能

時間復雜度為O(N^2)，空間復雜度為O(1)，排序是不穩定的(把最小值交換到已排序的末尾導致的)，每次都能確定一個元素所在的最終位置，比較次數與初始序列無關。

代碼

快速排序

原理

分而治之思想：

Divide：找到基準元素pivot，將數組A[p..r]劃分為A[p..pivotpos-1]和A[pivotpos+1…q]，左邊的元素都比基準小，右邊的元素都比基準大;

Conquer：對倆個劃分的數組進行遞歸排序;

Combine：因為基準的作用，使得倆個子數組就地有序，無需合並操作。

性能

快排的平均時間復雜度為O(NlogN)，空間復雜度為O(logN)，但最壞情況下，時間復雜度為O(N^2)，空間復雜度為O(N);且排序是不穩定的，但每次都能確定一個元素所在序列中的最終位置，復雜度與初始序列有關。

優化

當初始序列是非遞減序列時，快排性能下降到最壞情況，主要因為基準每次都是從最左邊取得，這時每次只能排好一個元素。

所以快排的優化思路如下：

優化基準，不每次都從左邊取，可以進行三路劃分，分別取最左邊，中間和最右邊的中間值，再交換到最左邊進行排序;或者進行隨機取得待排序數組中的某一個元素，再交換到最左邊，進行排序。

在規模較小情況下，採用直接插入排序

代碼

歸並排序

原理

分而治之思想：

Divide：將n個元素平均劃分為各含n/2個元素的子序列;

Conquer：遞歸的解決倆個規模為n/2的子問題;

Combine：合並倆個已排序的子序列。

性能

時間復雜度總是為O(NlogN)，空間復雜度也總為為O(N)，演算法與初始序列無關，排序是穩定的。

優化

優化思路：

在規模較小時，合並排序可採用直接插入;

在寫法上，可以在生成輔助數組時，倆頭小，中間大，這時不需要再在後邊加倆個while循環進行判斷，只需一次比完。

代碼

堆排序

原理

堆的性質：

是一棵完全二叉樹

每個節點的值都大於或等於其子節點的值，為最大堆;反之為最小堆。

堆排序思想：

將待排序的序列構造成一個最大堆，此時序列的最大值為根節點

依次將根節點與待排序序列的最後一個元素交換

再維護從根節點到該元素的前一個節點為最大堆，如此往復，最終得到一個遞增序列

性能

時間復雜度為O(NlogN)，空間復雜度為O(1)，因為利用的排序空間仍然是初始的序列，並未開辟新空間。演算法是不穩定的，與初始序列無關。

使用場景

想知道最大值或最小值時，比如優先順序隊列，作業調度等場景。

代碼

計數排序

原理

先把每個元素的出現次數算出來，然後算出該元素所在最終排好序列中的絕對位置(最終位置)，再依次把初始序列中的元素，根據該元素所在最終的絕對位置移到排序數組中。

性能

時間復雜度為O(N+K)，空間復雜度為O(N+K)，演算法是穩定的，與初始序列無關，不需要進行比較就能排好序的演算法。

使用場景

演算法只能使用在已知序列中的元素在0-k之間，且要求排序的復雜度在線性效率上。

代碼

桶排序

原理

根據待排序列元素的大小范圍，均勻獨立的劃分M個桶

將N個輸入元素分布到各個桶中去

再對各個桶中的元素進行排序

此時再按次序把各桶中的元素列出來即是已排序好的。

性能

時間復雜度為O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空間復雜度為O(N+M)，演算法是穩定的，且與初始序列無關。

使用場景

演算法思想和散列中的開散列法差不多，當沖突時放入同一個桶中;可應用於數據量分布比較均勻，或比較側重於區間數量時。

基數排序

原理

對於有d個關鍵字時，可以分別按關鍵字進行排序。有倆種方法：

MSD：先從高位開始進行排序，在每個關鍵字上，可採用計數排序

LSD：先從低位開始進行排序，在每個關鍵字上，可採用桶排序

性能

時間復雜度為O(d*(N+K))，空間復雜度為O(N+K)。

總結

以上排序演算法的時間、空間與穩定性的總結如下：

3. 幾種常見簡單排序演算法

排序演算法一般分為以下幾種：
（1）非線性時間比較類排序：交換類排序（快速排序和冒泡排序）、插入類排序（簡單插入排序和希爾排序）、選擇類排序（簡單選擇排序和堆排序）、歸並排序（二路歸並排序和多路歸並排序）；
（2）線性時間非比較類排序：計數排序、基數排序和桶排序。

4. 桶排序怎麼實現

桶排序的實驗如下：

桶排序 (Bucket sort)或所謂的箱排序，是一個排序演算法，工作的原理是將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別皮明的排序演算法或是以遞歸方式繼續使用桶排序進行排序）。

桶排序是鴿巢運拿排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序並不是 比較排序，他不受到O(nlogn) 下限的影響。

處理大量重復元素的情況：對於存在大量重復元素的情況，桶排序的效率也會比其他排序演算法高。因為桶排序在統計每個元素出現次數的過程中，相同元素只需計數一次，並存放在同一個桶里，不需要進行額外的比較和交換操作。

作為其他排序演算法的優化：桶排序還可以作為其他排序演算法的優化，提高其排序效率。比如，在快速排序中，每次選取的樞軸元素可能會導致某些分區的長度遠大於另一些分區，這就會影響快排的效率。此時可以使用桶排序對樞軸元素進行預處理，將數據分成若干個區域，再對燃悄告每個區域內的元素進行快排。

5. JAVA中有哪幾種常用的排序方法

1、冒泡排序
冒泡排序是一個比較簡單的排序方法。在待排序的數列基本有序的情況下排序速度較快。若要排序的數有n個，則需要n-1輪排序，第j輪排序中，從第一個數開始，相鄰兩數比較，若不符合所要求的順序，則交換兩者的位置；直到第n+1-j個數為止，第一個數與第二個數比較，第二個數與第三個數比較，......，第n-j個與第n+1-j個比較，共比較n-1次。此時第n+1-j個位置上的數已經按要求排好，所以不參加以後的比較和交換操作。例如：第一輪排序：第一個數與第二個數進行比較，若不符合要求的順序，則交換兩者的位置，否則繼續進行二個數與第三個數比較......。直到完成第n-1個數與第n個數的比較。此時第n個位置上的數已經按要求排好，它不參與以後的比較和交換操作；第二輪排序：第一個數與第二個數進行比較，......直到完成第n-2個數與第n-1個數的比較；......第n-1輪排序：第一個數與第二個數進行比較，若符合所要求的順序，則結束冒泡法排序；若不符合要求的順序，則交換兩者的位置，然後結束冒泡法排序。
共n-1輪排序處理，第j輪進行n-j次比較和至多n-j次交換。
從以上排序過程可以看出，較大的數像氣泡一樣向上冒，而較小的數往下沉，故稱冒泡法。

2、選擇排序
選擇法的原理是先將第一個數與後面的每一個數依次比較,不斷將將小的賦給第一個數,從而找出最小的,然後第二個數與後面的每一個數依次比較,從而找出第二小的,然後第三個數與後面的

3、插入排序
插入排序的原理是對數組中的第i個元素，認為它前面的i-1個已經排序好，然後將它插入到前面的i-1個元素中。插入排序對少量元素的排序較為有效.

4、快速排序
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一次排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此大道整個數據變成有序序列。