Swift完成堆排序算法的代碼示例。本站提示廣大學習愛好者：（Swift完成堆排序算法的代碼示例）文章只能為提供參考，不一定能成為您想要的結果。以下是Swift完成堆排序算法的代碼示例正文
算法思想
堆排序應用了最大堆（或小根堆）堆頂記載的關鍵字最大（或最小）這一特征，使得在以後無序區中選取最大（或最小）關鍵字的記載變得復雜。
1.用最大堆排序的根本思想
（1）先將初始文件R[1..n]建成一個最大堆，此堆為初始的無序區
（2）再將關鍵字最大的記載R[1]（即堆頂）和無序區的最後一個記載R[n]交流，由此失掉新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
（3）由於交流後新的根R[1]能夠違背堆性質，故應將以後無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記載R[1]和該區間的最後一個記載R[n-1]交流，由此失掉新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，異樣要將R[1..n-2]調整為堆。
……
直到無序區只要一個元素為止。
2.最大堆排序算法的根本操作：
（1）建堆，建堆是不時調整堆的進程，從len/2處開端調整，不斷到第一個節點，此處len是堆中元素的個數。建堆的進程是線性的進程，從len/2到0處不斷調用調整堆的進程，相當於o(h1)+o(h2)…+o(hlen/2) 其中h表示節點的深度，len/2表示節點的個數，這是一個求和的進程，後果是線性的O(n)。
（2）調整堆：調整堆在構建堆的進程中會用到，而且在堆排序進程中也會用到。應用的思想是比擬節點i和它的孩子節點left(i),right(i)，選出三者最大(或許最小)者，假如最大（小）值不是節點i而是它的一個孩子節點，那邊交互節點i和該節點，然後再調用調整堆進程，這是一個遞歸的進程。調整堆的進程時間復雜度與堆的深度有關系，是lgn的操作，由於是沿著深度方向停止調整的。
（3）堆排序：堆排序是應用下面的兩個進程來停止的。首先是依據元素構建堆。然後將堆的根節點取出(普通是與最後一個節點停止交流)，將後面len-1個節點持續停止堆調整的進程，然後再將根節點取出，這樣不斷到一切節點都取出。堆排序進程的時間復雜度是O(nlgn)。由於建堆的時間復雜度是O(n)（調用一次）；調整堆的時間復雜度是lgn，調用了n-1次，所以堆排序的時間復雜度是O(nlgn)[2]
留意
（1）只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
（2）用小根堆排序與應用最大堆相似，只不過其排序後果是遞加有序的。堆排序和直接選擇排序相反：在任何時辰堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐漸擴展至整個向量為止
Swift示例
（1）基於最大堆完成升序排序
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，闡明曾經無序區曾經減少到0
guard len > 1 else {
return
}
// 父結點的左、右孩子的索引
let leftChildIndex = 2 * parentNodeIndex + 1
// 假如連左孩子都沒有， 一定沒有右孩子，闡明曾經不必再往下了
guard leftChildIndex < len else {
return
}
let rightChildIndex = 2 * parentNodeIndex + 2
// 用於記載需求與父結點交流的孩子的索引
var targetIndex = -1
// 若沒有右孩子，但有左孩子，只能選擇左孩子
if rightChildIndex > len {
targetIndex = leftChildIndex
} else {
// 左、右孩子都有，則需求找出最大的一個
targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex
}
// 只要孩子比父結點還要大，再需求交流
if a[targetIndex] > a[parentNodeIndex] {
let temp = a[targetIndex]
a[targetIndex] = a[parentNodeIndex]
a[parentNodeIndex] = temp
// 由於交流後，能夠會毀壞掉新的子樹堆的性質，因而需求調整以a[targetIndex]為父結點的子樹，使之滿足堆的性質
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 {
// 每一趟都將堆頂交流到指定范圍內的最後一個地位
if a[0] > a[i] {
let temp = a[0]
a[0] = a[i]
a[i] = temp
}
print(a)
print(i - 1)
// 有序區長度+1，而無序區長度-1，持續減少無序區，所以i-1
// 堆頂永遠是在0號地位，所以父結點調整從堆頂開端就可以了
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，闡明曾經無序區曾經減少到0
guard len > 1 else {
return
}
// 父結點的左、右孩子的索引
let leftChildIndex = 2 * parentNodeIndex + 1
// 假如連左孩子都沒有， 一定沒有右孩子，闡明曾經不必再往下了
guard leftChildIndex < len else {
return
}
let rightChildIndex = 2 * parentNodeIndex + 2
// 用於記載需求與父結點交流的孩子的索引
var targetIndex = -1
// 若沒有右孩子，但有左孩子，只能選擇左孩子
if rightChildIndex > len {
targetIndex = leftChildIndex
} else {
// 左、右孩子都有，則需求找出最大的一個
targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex
}
// 只要孩子比父結點還要大，再需求交流
if a[targetIndex] < a[parentNodeIndex] {
let temp = a[targetIndex]
a[targetIndex] = a[parentNodeIndex]
a[parentNodeIndex] = temp
// 由於交流後，能夠會毀壞掉新的子樹堆的性質，因而需求調整以a[targetIndex]為父結點的子樹，使之滿足堆的性質
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 {
// 每一趟都將堆頂交流到指定范圍內的最後一個地位
if a[0] < a[i] {
let temp = a[0]
a[0] = a[i]
a[i] = temp
} else {
return // 可以直接加入了，由於曾經全部有序了
}
// 有序區長度+1，而無序區長度-1，持續減少無序區，所以i-1
// 堆頂永遠是在0號地位，所以父結點調整從堆頂開端就可以了
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]
