Swift實現(xiàn)堆排序算法的代碼示例
算法思想
堆排序利用了最大堆（或小根堆）堆頂記錄的關(guān)鍵字最大（或最?。┻@一特征，使得在當前無序區(qū)中選取最大（或最小）關(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ì)，故應將當前無序區(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)整堆的過程，相當于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)整堆的過程時間復雜度與堆的深度有關(guān)系，是lgn的操作，因為是沿著深度方向進行調(diào)整的。
（3）堆排序：堆排序是利用上面的兩個過程來進行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點取出(一般是與最后一個節(jié)點進行交換)，將前面len-1個節(jié)點繼續(xù)進行堆調(diào)整的過程，然后再將根節(jié)點取出，這樣一直到所有節(jié)點都取出。堆排序過程的時間復雜度是O(nlgn)。因為建堆的時間復雜度是O(n)（調(diào)用一次）；調(diào)整堆的時間復雜度是lgn，調(diào)用了n-1次，所以堆排序的時間復雜度是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)文章
swift中利用runtime交換方法的實現(xiàn)示例
這篇文章主要給大家介紹了關(guān)于swift中利用runtime交換方法的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。2018-05-05
這篇文章主要介紹了Swift教程之閉包詳解,閉包可以在上下文的范圍內(nèi)捕獲、存儲任何被定義的常量和變量引用,因這些常量和變量的封閉性,而命名為“閉包（Closures）”,需要的朋友可以參考下2015-01-01
這篇文章主要給大家介紹了關(guān)于RxSwift學習教程之類型對象Subject的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起看看吧。2017-09-09
這篇文章主要給大家介紹了關(guān)于Swift中命名空間的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-12-12
Swift中自帶數(shù)組、set、字典三大集合類型,這里將學習過程中的基礎(chǔ)的Swift中內(nèi)置的集合類型學習筆記進行整理,需要的朋友可以參考下2016-06-06
Swift的函數(shù)在創(chuàng)建和調(diào)用時非常簡潔,在編寫具有閉包特性的函數(shù)時同樣也相當方便,以下我們就來詳解Swift中的函數(shù)及函數(shù)閉包使用:2016-06-06
既然面向?qū)ο竽蔷鸵欢〞衜ethod,方法和面向過程語言中的function函數(shù)并沒什么區(qū)別,只不過方法在面向?qū)ο笳Z言中可以被類來約束作用域,這里我們就來詳解Swift面向?qū)ο缶幊讨械姆椒?method)2016-07-07
這篇文章主要給大家介紹了關(guān)于swift中自定義正則表達式運算符=~的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。2017-12-12
本篇文章主要介紹了Swift中如何避免循環(huán)引用的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-12-12
Swift之UITabBarController 導航控制器的自定義
本文給大家介紹swift導航控制器之UITabBarController，本文通過代碼實例給大家講解swift導航控制器，導航控制器類繼承UITabBarController，代碼簡單易懂，需要的朋友可以參考下2015-10-10