leetcode刷題（二）：排序演算法（歸併排序，堆排序，桶排序）
今天，我們要來講講排序問題，這次講的排序演算法主要是歸併排序，堆排序和桶排序。
歸併排序
歸併一詞在中文的含義就是「合併，併入」的意思，在數據結構裡面就是將兩個或者兩個以上的有序數組列表合併成一個的意思。
歸併排序就是利用歸併思想實現排序的方法。它的原理就是假設有n個初始數據，即n個有序子序列，它們的長度都是1，將它們兩兩合併，得到了n/2個長度為2的有序子序 列。再兩兩合併，如此重複，知道得到一個長度為n的有序子序列為止，這種排序方法稱之為2路歸併排序。
老規矩，上偽代碼吧：
void MergeSort (int SR[ ] , int TR[ ], int s , int t )
{
int m ;
int TR2[MAXSIZE + 1]
if (s == t):
TR1[s] = SR[s]
else:
{
m = (m + s) / 2
MSort(SR , TR2 , s , m)
MSort(SR , TR2 , s + 1 , m)
Merge(TR2 , TR2 ,s ,m , t)
}
}
簡單講一下，這段函數利用到了遞歸，假設初始子序列有10個關鍵字，第一個MSort就是將初始子序列下標0-4的關鍵字歸併到TR2，第二個MSort就是將初始子序列下標5-9的關鍵字歸併到TR2，可以認為將子序列分割成了兩塊，那麼Merge函數就負責把這兩塊分割的子序列歸併成一個完整的子序列。由於是遞歸，所以我們會一直分割分割直到分割成大小為1的子序列為止，然後再遞歸回來歸併成一個完整有序的子序列。
再講下Merge函數是怎麼歸併的，因為在歸併前，因為是遞歸，兩個子函數就已經是有序的了，我們假設到最後一種情況，兩個有序的，長度為5的有序子序列進行歸併，設第一個子序列下標為i，第二個下標為j。
if (SR[i] < SR[j]):
TR[k] = SR[i]
i ++
else:
TR[k] = SR[j]
j ++
差不多就是這樣的。
接下來我們來談談對比排序的複雜度吧。
首先分析時間複雜度，一趟歸併排序需要將SR[1]-SR[n]中長度為h的相鄰元素兩兩歸併，並將結果放在SR[1]-SR[n]中，所以需要將序列全部掃描一遍，時間複雜度為O(n)，再根據完全二叉樹的深度可知，整個歸併排序需要進行O(lgn)次，所以總的時間複雜度為O(nlgn)，這是歸併排序最好最壞的平均性能。
至於空間複雜度，由於再歸併過程中需要和原子序列相同大小的存儲空間存放歸併結果並且需要深度為lgn的棧空間，所以空間複雜度為O(n+lgn)。
那能不能優化呢？當然可以啊，試試能不能將遞歸換成迭代就行了，具體代碼我就不打了（lan不解釋！~！），因為非遞歸函數在空間上不需要(lgn)的棧空間，所以空間複雜度是O(n)，時間複雜度上也有所提升，可以說在歸併演算法中，我們應該盡量避免使用遞歸方法。
下面做一道真題：
Leetcode : 88. Merge Sorted Array (Easy)
給定兩個有序整數數組 nums1 和 nums2，將 nums2 合併到 nums1 中，使得 num1 成為一個有序數組。
說明:
初始化 nums1 和 nums2 的元素數量分別為 m 和 n。
你可以假設 nums1 有足夠的空間（空間大小大於或等於 m + n）來保存 nums2 中的元素。
示例:
輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出: [1,2,2,3,5,6]
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
for x in nums2:
i = m-1
while i>-1:
if nums1[i]>x:
nums1[i+1] = nums1[i]
i-=1
else:
nums1[i+1] = x
break
if i == -1:
nums1[0] = x
m+=1
堆排序
說到堆排序，讓我們先想一個問題，如果在待排序的n個子序列中尋找一個最小的子序列，需要n-1次比較沒錯吧，但是我們本沒有將這次排序的結果過程保存下來，那麼在下次排序中，比如說找到第二小的子序列，是不是又需要走一遍？這樣很浪費資源和時間。
那麼我們做到每次選擇到最小記錄的同時，比較結果並對其他記錄做出相應的調整，這樣我們的效率就大大提高了。
而我們的堆排序，就是對相對簡單的堆排序的一種改進，而且效果非常明顯。
首先我們要明白，堆是具有以下性質的完全二叉樹：每個結點的值都大於或等於其左右節點的值，稱之為大頂堆；每個結點的值都小於或等於其左右節點的值，稱之為小頂堆。
堆排序就是利用堆進行排序的方法(假設使用大頂堆)：將待排序的序列組成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點了，我們將它移走(其實就是將他和數組的末尾元素交換)，然後將剩餘的n-1個元素繼續構成一個大頂堆，這樣就會得到n個元素中的第二大的值，如此反覆執行，我們就能得到一個有序序列了。
相信大家對堆排序的基本思想有一定的理解了，不過實現它還需要解決兩個問題：
1.如何由一個無序序列構成一個堆？
2.在輸出頂堆元素後，剩下的元素如何形成一個新的堆？
解決這兩個問題嘛，老規矩，上代碼！！
void HeapSort(SqList *L)
{
int i ;
for(i = L->length/2;i>0;i--)
HeapAdjust(L,i,L->length);
for(i = L->length;i>0;i--)
swap(L,l,i);
HeapAdjust(L,i,i-1);
}
這裡可以看到有兩個循環，第一個循環是將現有的序列構成一個大頂堆，第二個循環就是將每個最大值的根節點和末尾元素交換，並且將剩餘元素構成大頂堆。
現在我們來看看關鍵元素HeapAdjust(堆調整)是怎樣實現的吧！
void HeapAdjust(SqList *L ,int s , int m)
{
int temp , j;
temp = L->r[s];
for( j = 2*s , j <= m ,j *= 2 )
{
if (j < m && L->r[j] < L->r[j+1])
++j;
if (temp >= L->r[j])
break;
L->r[s] = L->r[j];
s = j;
}
L->r[s] = temp
}
代碼不長吧，相信大家都能看得懂，我這邊就講幾個我認為的難點吧。
首先j變數為什麼從2*s開始呢？因為這是二叉樹的性質，因為我們的二叉樹都是完全二叉樹，所以它的節點為s，那麼它的左孩子一定是2s，右孩子一定是2*s+1。
我用簡潔的話講一下基本思想：先將結點的左右孩子進行比較，如果右孩子大，j++。將比較完後較大的數和雙親進行比較，如L->r[j] > L->r[s]，將他們exchange即可。
接下來我們討論下堆排序的效率吧！~！
它的消耗主要是在初始建堆和重新建堆的反覆篩選上面。在構建堆以後，我們從二叉樹最下層最右邊的非終端節點開始，將它對其孩子進行比較和有必要的互換。所以對每個非終端節點來說，最多進行兩次比較和互換操作，所以整個構建堆的時間複雜度為O(n)。
在正式排序時，第 i 次取頂記錄重建堆需要的時間是O(logi)(根據完全二叉樹某個節點到根節點的距離為[logi]+1)。因此，重建堆的時間複雜度為O(nlogn)。
所以總體來說，堆排序的時間複雜度為O(nlogn)。
下面是真題時間：
Leetocde : 215. Kth Largest Element in an Array (Medium)
在未排序的數組中找到第 k 個最大的元素。請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
length = len(nums)
# 構建大頂堆
for i in reversed(range(0, length / 2)):
self.adjustHeap(nums, i, length)
count = 0
for j in reversed(range(0,length)):
count += 1
if count == k:
return nums[0]
self.swap(nums,0,j)
length -= 1
self.adjustHeap(nums,0,length)
def adjustHeap(self,nums,i,length):
while True:
k = i*2+1
if k >= length:
return
if k + 1 < length and nums[k+1] > nums[k]:
k += 1
if nums[k] > nums[i]:
self.swap(nums,i,k)
i = k
else:
return
def swap(self,nums,i,j):
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
桶排序
到目前為止，我們已經介紹了歸併排序和堆排序這兩種比較排序演算法，我們知道，在最壞情況下任何比較排序演算法都要做O(nlgn)次比較，而歸併排序和堆排序都是漸進最優的比較排序演算法。
接下來我要介紹是是線性時間排序，它是一種非比較排序，它最主要的優點就是穩定。下面我來講幾種典型的線性時間排序：
計數排序：
計數排序的基本思想是對於每個輸入元素，確定小於x的元素的個數，利用這一信息，我們可以直接把x放到它輸出數組的位置上了。
基數排序：
基數排序是一種很古老的排序了，我們舉個栗子就很明白了，比如我們要排序10個三位數，那我們可以先按最低有效位進行排序來解決卡片的排序問題。即先比較個位數，再比較十位數，最後比較百位數就行了！~！
以上兩種線性時間演算法都比較簡單，所以我就不展開講了，接下來我要重點講一下一種運用比較多是演算法--桶排序演算法。
桶排序是假設數據服從均勻分佈，在平均情況下，它們的時間代價為O(n)。
桶排序是將[0，1]區間劃分為n個大小相同的子區間，或者稱之為桶，然後將n個輸入分別輸入到對應的桶中，然後我們對每個桶中的元素進行排序，遍歷每個桶，按照次序，將桶中的元素輸出即可。
再舉一個通俗栗子，我們有100個元素，其中每個元素x都滿足(1 <= x <= 1000) ，求其中個數最多的元素，解決這個問題那我們只需要準備1000個桶，每個桶的編號為1，2，3，4，……1000即可，然後遍曆元素，將每個元素的個數最高者輸出即可！~！
真題時間到了！~！
Leetcode : 347. Top K Frequent Elements (Medium)
給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1
輸出: [1]
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
a = {}
for i in nums:
if i in a.keys():
a[i] += 1
else:
a[i] = 1
b = sorted(a.items(),key=lambda x:x[1],reverse = True)
result = []
for i in range(k):
result.append(b[i][0])
return result
不多就這樣了，希望本文能夠幫到你！~！
最後打個小廣告，我的公眾號，喜歡寫點學習中的小心得，不介意可以關注下!~!
推薦閱讀：
