今天，我們要來講講排序問題，這次講的排序算法主要是歸并排序，堆排序和桶排序。
歸并一詞在中文的含義就是“合并，并入”的意思，在數據結構里面就是將兩個或者兩個以上的有序數組列表合并成一個的意思。
排序算法時間復雜度總結。歸并排序就是利用歸并思想實現排序的方法。它的原理就是假設有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) / 2MSort(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-1while i>-1:if nums1[i]>x:nums1[i+1] = nums1[i]i-=1else:nums1[i+1] = xbreakif i == -1:nums1[0] = xm+=1快速排序算法時間復雜度。說到堆排序，讓我們先想一個問題，如果在待排序的n個子序列中尋找一個最小的子序列，需要n-1次比較沒錯吧，但是我們本沒有將這次排序的結果過程保存下來，那么在下次排序中，比如說找到第二小的子序列，是不是又需要走一遍？這樣很浪費資源和時間。
那么我們做到每次選擇到最小記錄的同時，比較結果并對其他記錄做出相應的調整，這樣我們的效率就大大提高了。
而我們的堆排序，就是對相對簡單的堆排序的一種改進，而且效果非常明顯。
首先我們要明白，堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右節點的值，稱之為大頂堆；每個結點的值都小于或等于其左右節點的值，稱之為小頂堆。
堆排序時間復雜度、堆排序就是利用堆進行排序的方法(假設使用大頂堆)：將待排序的序列組成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點了，我們將它移走(其實就是將他和數組的末尾元素交換)，然后將剩余的n-1個元素繼續構成一個大頂堆，這樣就會得到n個元素中的第二大的值，如此反復執行，我們就能得到一個有序序列了。
相信大家對堆排序的基本思想有一定的理解了，不過實現它還需要解決兩個問題：
1.如何由一個無序序列構成一個堆？
2.在輸出頂堆元素后，剩下的元素如何形成一個新的堆？
leetcode 刷題app、解決這兩個問題嘛，老規矩，上代碼！！
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}
代碼不長吧，相信大家都能看得懂，我這邊就講幾個我認為的難點吧。
leetcode刷多少題，首先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 = 0for j in reversed(range(0,length)):count += 1if count == k:return nums[0]self.swap(nums,0,j)length -= 1self.adjustHeap(nums,0,length)def adjustHeap(self,nums,i,length):while True:k = i*2+1if k >= length:returnif k + 1 < length and nums[k+1] > nums[k]:k += 1if nums[k] > nums[i]:self.swap(nums,i,k)i = kelse:returndef 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] += 1else:a[i] = 1b = sorted(a.items(),key=lambda x:x[1],reverse = True)result = []for i in range(k):result.append(b[i][0])return result不多就這樣了，希望本文能夠幫到你！~！
最后打個小廣告，我的公眾號，喜歡寫點學習中的小心得，不介意可以關注下!~!
版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间：8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态
