Swift實現(xiàn)堆排序算法的代碼示例
算法思想
堆排序利用了最大堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最?。┻@一特征,使得在當(dāng)前無序區(qū)中選取最大(或最?。╆P(guān)鍵字的記錄變得簡單。
1.用最大堆排序的基本思想
(1)先將初始文件R[1..n]建成一個最大堆,此堆為初始的無序區(qū)
(2)再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換,由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n],且滿足R[1..n-1].keys≤R[n].key
(3)由于交換后新的根R[1]可能違反堆性質(zhì),故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換,由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n],且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys,同樣要將R[1..n-2]調(diào)整為堆。
……
直到無序區(qū)只有一個元素為止。
2.最大堆排序算法的基本操作:
(1)建堆,建堆是不斷調(diào)整堆的過程,從len/2處開始調(diào)整,一直到第一個節(jié)點,此處len是堆中元素的個數(shù)。建堆的過程是線性的過程,從len/2到0處一直調(diào)用調(diào)整堆的過程,相當(dāng)于o(h1)+o(h2)…+o(hlen/2) 其中h表示節(jié)點的深度,len/2表示節(jié)點的個數(shù),這是一個求和的過程,結(jié)果是線性的O(n)。
(2)調(diào)整堆:調(diào)整堆在構(gòu)建堆的過程中會用到,而且在堆排序過程中也會用到。利用的思想是比較節(jié)點i和它的孩子節(jié)點left(i),right(i),選出三者最大(或者最小)者,如果最大(小)值不是節(jié)點i而是它的一個孩子節(jié)點,那邊交互節(jié)點i和該節(jié)點,然后再調(diào)用調(diào)整堆過程,這是一個遞歸的過程。調(diào)整堆的過程時間復(fù)雜度與堆的深度有關(guān)系,是lgn的操作,因為是沿著深度方向進行調(diào)整的。
(3)堆排序:堆排序是利用上面的兩個過程來進行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點取出(一般是與最后一個節(jié)點進行交換),將前面len-1個節(jié)點繼續(xù)進行堆調(diào)整的過程,然后再將根節(jié)點取出,這樣一直到所有節(jié)點都取出。堆排序過程的時間復(fù)雜度是O(nlgn)。因為建堆的時間復(fù)雜度是O(n)(調(diào)用一次);調(diào)整堆的時間復(fù)雜度是lgn,調(diào)用了n-1次,所以堆排序的時間復(fù)雜度是O(nlgn)[2]
注意
(1)只需做n-1趟排序,選出較大的n-1個關(guān)鍵字即可以使得文件遞增有序。
(2)用小根堆排序與利用最大堆類似,只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反:在任何時刻堆排序中無序區(qū)總是在有序區(qū)之前,且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止
Swift示例
(1)基于最大堆實現(xiàn)升序排序
func initHeap(inout a: [Int]) { for var i = (a.count - 1) / 2; i >= 0; --i { adjustMaxHeap(&a, len: a.count, parentNodeIndex: i) } } func adjustMaxHeap(inout a: [Int], len: Int, parentNodeIndex: Int) { // 如果len <= 0,說明已經(jīng)無序區(qū)已經(jīng)縮小到0 guard len > 1 else { return } // 父結(jié)點的左、右孩子的索引 let leftChildIndex = 2 * parentNodeIndex + 1 // 如果連左孩子都沒有, 一定沒有右孩子,說明已經(jīng)不用再往下了 guard leftChildIndex < len else { return } let rightChildIndex = 2 * parentNodeIndex + 2 // 用于記錄需要與父結(jié)點交換的孩子的索引 var targetIndex = -1 // 若沒有右孩子,但有左孩子,只能選擇左孩子 if rightChildIndex > len { targetIndex = leftChildIndex } else { // 左、右孩子都有,則需要找出最大的一個 targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex } // 只有孩子比父結(jié)點還要大,再需要交換 if a[targetIndex] > a[parentNodeIndex] { let temp = a[targetIndex] a[targetIndex] = a[parentNodeIndex] a[parentNodeIndex] = temp // 由于交換后,可能會破壞掉新的子樹堆的性質(zhì),因此需要調(diào)整以a[targetIndex]為父結(jié)點的子樹,使之滿足堆的性質(zhì) adjustMaxHeap(&a, len: len, parentNodeIndex: targetIndex) } } func maxHeapSort(inout a: [Int]) { guard a.count > 1 else { return } initHeap(&a) for var i = a.count - 1; i > 0; --i { // 每一趟都將堆頂交換到指定范圍內(nèi)的最后一個位置 if a[0] > a[i] { let temp = a[0] a[0] = a[i] a[i] = temp } print(a) print(i - 1) // 有序區(qū)長度+1,而無序區(qū)長度-1,繼續(xù)縮小無序區(qū),所以i-1 // 堆頂永遠是在0號位置,所以父結(jié)點調(diào)整從堆頂開始就可以了 adjustMaxHeap(&a, len: i - 1, parentNodeIndex: 0) print(a) } }
(2)基于最小堆降序排序
func initHeap(inout a: [Int]) { for var i = (a.count - 1) / 2; i >= 0; --i { adjustMinHeap(&a, len: a.count, parentNodeIndex: i) } } func adjustMinHeap(inout a: [Int], len: Int, parentNodeIndex: Int) { // 如果len <= 0,說明已經(jīng)無序區(qū)已經(jīng)縮小到0 guard len > 1 else { return } // 父結(jié)點的左、右孩子的索引 let leftChildIndex = 2 * parentNodeIndex + 1 // 如果連左孩子都沒有, 一定沒有右孩子,說明已經(jīng)不用再往下了 guard leftChildIndex < len else { return } let rightChildIndex = 2 * parentNodeIndex + 2 // 用于記錄需要與父結(jié)點交換的孩子的索引 var targetIndex = -1 // 若沒有右孩子,但有左孩子,只能選擇左孩子 if rightChildIndex > len { targetIndex = leftChildIndex } else { // 左、右孩子都有,則需要找出最大的一個 targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex } // 只有孩子比父結(jié)點還要大,再需要交換 if a[targetIndex] < a[parentNodeIndex] { let temp = a[targetIndex] a[targetIndex] = a[parentNodeIndex] a[parentNodeIndex] = temp // 由于交換后,可能會破壞掉新的子樹堆的性質(zhì),因此需要調(diào)整以a[targetIndex]為父結(jié)點的子樹,使之滿足堆的性質(zhì) adjustMinHeap(&a, len: len, parentNodeIndex: targetIndex) } } func minHeapSort(inout a: [Int]) { guard a.count > 1 else { return } initHeap(&a) for var i = a.count - 1; i > 0; --i { // 每一趟都將堆頂交換到指定范圍內(nèi)的最后一個位置 if a[0] < a[i] { let temp = a[0] a[0] = a[i] a[i] = temp } else { return // 可以直接退出了,因為已經(jīng)全部有序了 } // 有序區(qū)長度+1,而無序區(qū)長度-1,繼續(xù)縮小無序區(qū),所以i-1 // 堆頂永遠是在0號位置,所以父結(jié)點調(diào)整從堆頂開始就可以了 adjustMinHeap(&a, len: i - 1, parentNodeIndex: 0) } }
測試:
var arr = [5, 3, 8, 6, 4] //var arr = [89,-7,999,-89,7,0,-888,7,-7] maxHeapSort(&arr) print(arr) // 打印日志如下: [4, 6, 5, 3, 8] 3 [6, 4, 5, 3, 8] [3, 4, 5, 6, 8] 2 [5, 4, 3, 6, 8] [3, 4, 5, 6, 8] 1 [3, 4, 5, 6, 8] [3, 4, 5, 6, 8] 0 [3, 4, 5, 6, 8] [3, 4, 5, 6, 8]
相關(guān)文章
RxSwift發(fā)送及訂閱 Subjects、Variables代碼示例
這篇文章主要介紹了RxSwift發(fā)送及訂閱 Subjects、Variables代碼示例,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-12-12Swift UILable 設(shè)置內(nèi)邊距實例代碼
本文主要介紹Swift UILable 設(shè)置內(nèi)邊距,這里提供示例代碼供大家參考,有需要的小伙伴可以看下2016-07-07Swift?Error重構(gòu)的基礎(chǔ)示例詳解
這篇文章主要為大家介紹了Swift?Error基礎(chǔ)錯誤處理的方法詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-11-11Swift仿選擇電影票的效果并實現(xiàn)無限/自動輪播的方法
這篇文章主要給大家介紹了關(guān)于Swift仿選擇電影票的效果并實現(xiàn)無限/自動輪播的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-08-08