欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Swift實(shí)現(xiàn)堆排序算法的代碼示例

 更新時(shí)間:2016年06月08日 11:38:54   作者:黃儀標(biāo)  
堆排序(HeapSort)是一樹(shù)形選擇排序,堆排序的時(shí)間復(fù)雜度O(nlogn),這里我們來(lái)看一下Swift實(shí)現(xiàn)基堆排序算法的代碼示例,首先對(duì)堆排序算法的基本概念作一個(gè)了解:

算法思想
堆排序利用了最大堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征,使得在當(dāng)前無(wú)序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡(jiǎn)單。
1.用最大堆排序的基本思想
(1)先將初始文件R[1..n]建成一個(gè)最大堆,此堆為初始的無(wú)序區(qū)
(2)再將關(guān)鍵字最大的記錄R[1](即堆頂)和無(wú)序區(qū)的最后一個(gè)記錄R[n]交換,由此得到新的無(wú)序區(qū)R[1..n-1]和有序區(qū)R[n],且滿足R[1..n-1].keys≤R[n].key
(3)由于交換后新的根R[1]可能違反堆性質(zhì),故應(yīng)將當(dāng)前無(wú)序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換,由此得到新的無(wú)序區(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)整為堆。
……
直到無(wú)序區(qū)只有一個(gè)元素為止。
2.最大堆排序算法的基本操作:
(1)建堆,建堆是不斷調(diào)整堆的過(guò)程,從len/2處開(kāi)始調(diào)整,一直到第一個(gè)節(jié)點(diǎn),此處len是堆中元素的個(gè)數(shù)。建堆的過(guò)程是線性的過(guò)程,從len/2到0處一直調(diào)用調(diào)整堆的過(guò)程,相當(dāng)于o(h1)+o(h2)…+o(hlen/2) 其中h表示節(jié)點(diǎn)的深度,len/2表示節(jié)點(diǎn)的個(gè)數(shù),這是一個(gè)求和的過(guò)程,結(jié)果是線性的O(n)。
(2)調(diào)整堆:調(diào)整堆在構(gòu)建堆的過(guò)程中會(huì)用到,而且在堆排序過(guò)程中也會(huì)用到。利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i),right(i),選出三者最大(或者最小)者,如果最大(?。┲挡皇枪?jié)點(diǎn)i而是它的一個(gè)孩子節(jié)點(diǎn),那邊交互節(jié)點(diǎn)i和該節(jié)點(diǎn),然后再調(diào)用調(diào)整堆過(guò)程,這是一個(gè)遞歸的過(guò)程。調(diào)整堆的過(guò)程時(shí)間復(fù)雜度與堆的深度有關(guān)系,是lgn的操作,因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的。
(3)堆排序:堆排序是利用上面的兩個(gè)過(guò)程來(lái)進(jìn)行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點(diǎn)取出(一般是與最后一個(gè)節(jié)點(diǎn)進(jìn)行交換),將前面len-1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過(guò)程,然后再將根節(jié)點(diǎn)取出,這樣一直到所有節(jié)點(diǎn)都取出。堆排序過(guò)程的時(shí)間復(fù)雜度是O(nlgn)。因?yàn)榻ǘ训臅r(shí)間復(fù)雜度是O(n)(調(diào)用一次);調(diào)整堆的時(shí)間復(fù)雜度是lgn,調(diào)用了n-1次,所以堆排序的時(shí)間復(fù)雜度是O(nlgn)[2]
注意
(1)只需做n-1趟排序,選出較大的n-1個(gè)關(guān)鍵字即可以使得文件遞增有序。
(2)用小根堆排序與利用最大堆類(lèi)似,只不過(guò)其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反:在任何時(shí)刻堆排序中無(wú)序區(qū)總是在有序區(qū)之前,且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個(gè)向量為止

Swift示例
(1)基于最大堆實(shí)現(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,說(shuō)明已經(jīng)無(wú)序區(qū)已經(jīng)縮小到0
 guard len > 1 else {
  return
 }
 
 // 父結(jié)點(diǎn)的左、右孩子的索引
 let leftChildIndex = 2 * parentNodeIndex + 1
 
 // 如果連左孩子都沒(méi)有, 一定沒(méi)有右孩子,說(shuō)明已經(jīng)不用再往下了
 guard leftChildIndex < len else {
  return
 }
 
 let rightChildIndex = 2 * parentNodeIndex + 2
 
 // 用于記錄需要與父結(jié)點(diǎn)交換的孩子的索引
 var targetIndex = -1
 
 // 若沒(méi)有右孩子,但有左孩子,只能選擇左孩子
 if rightChildIndex > len {
  targetIndex = leftChildIndex
 } else {
  // 左、右孩子都有,則需要找出最大的一個(gè)
  targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex
 }
 
 // 只有孩子比父結(jié)點(diǎn)還要大,再需要交換
 if a[targetIndex] > a[parentNodeIndex] {
  let temp = a[targetIndex]
  
  a[targetIndex] = a[parentNodeIndex]
  a[parentNodeIndex] = temp
  
  // 由于交換后,可能會(huì)破壞掉新的子樹(shù)堆的性質(zhì),因此需要調(diào)整以a[targetIndex]為父結(jié)點(diǎn)的子樹(shù),使之滿足堆的性質(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)的最后一個(gè)位置
  if a[0] > a[i] {
   let temp = a[0]
   
   a[0] = a[i]
   a[i] = temp
  }
  print(a)
  print(i - 1)
  // 有序區(qū)長(zhǎng)度+1,而無(wú)序區(qū)長(zhǎng)度-1,繼續(xù)縮小無(wú)序區(qū),所以i-1
  // 堆頂永遠(yuǎn)是在0號(hào)位置,所以父結(jié)點(diǎn)調(diào)整從堆頂開(kāi)始就可以了
  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,說(shuō)明已經(jīng)無(wú)序區(qū)已經(jīng)縮小到0
 guard len > 1 else {
  return
 }
 
 // 父結(jié)點(diǎn)的左、右孩子的索引
 let leftChildIndex = 2 * parentNodeIndex + 1
 
 // 如果連左孩子都沒(méi)有, 一定沒(méi)有右孩子,說(shuō)明已經(jīng)不用再往下了
 guard leftChildIndex < len else {
  return
 }
 
 let rightChildIndex = 2 * parentNodeIndex + 2
 
 // 用于記錄需要與父結(jié)點(diǎn)交換的孩子的索引
 var targetIndex = -1
 
 // 若沒(méi)有右孩子,但有左孩子,只能選擇左孩子
 if rightChildIndex > len {
  targetIndex = leftChildIndex
 } else {
  // 左、右孩子都有,則需要找出最大的一個(gè)
  targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex
 }
 
 // 只有孩子比父結(jié)點(diǎn)還要大,再需要交換
 if a[targetIndex] < a[parentNodeIndex] {
  let temp = a[targetIndex]
  
  a[targetIndex] = a[parentNodeIndex]
  a[parentNodeIndex] = temp
  
  // 由于交換后,可能會(huì)破壞掉新的子樹(shù)堆的性質(zhì),因此需要調(diào)整以a[targetIndex]為父結(jié)點(diǎn)的子樹(shù),使之滿足堆的性質(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)的最后一個(gè)位置
  if a[0] < a[i] {
   let temp = a[0]
   
   a[0] = a[i]
   a[i] = temp
  } else {
    return // 可以直接退出了,因?yàn)橐呀?jīng)全部有序了
  }
  
  // 有序區(qū)長(zhǎng)度+1,而無(wú)序區(qū)長(zhǎng)度-1,繼續(xù)縮小無(wú)序區(qū),所以i-1
  // 堆頂永遠(yuǎn)是在0號(hào)位置,所以父結(jié)點(diǎn)調(diào)整從堆頂開(kāi)始就可以了
  adjustMinHeap(&a, len: i - 1, parentNodeIndex: 0)
 }
}

測(cè)試:

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代碼示例

    這篇文章主要介紹了RxSwift發(fā)送及訂閱 Subjects、Variables代碼示例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-12-12
  • Swift教程之函數(shù)詳解

    Swift教程之函數(shù)詳解

    這篇文章主要介紹了Swift教程之函數(shù)詳解,本文講解了函數(shù)的聲明與調(diào)用、函數(shù)的參數(shù)和返回值、函數(shù)參數(shù)名、函數(shù)類(lèi)型等內(nèi)容,需要的朋友可以參考下
    2015-01-01
  • Swift UILable 設(shè)置內(nèi)邊距實(shí)例代碼

    Swift UILable 設(shè)置內(nèi)邊距實(shí)例代碼

    本文主要介紹Swift UILable 設(shè)置內(nèi)邊距,這里提供示例代碼供大家參考,有需要的小伙伴可以看下
    2016-07-07
  • Swift?Error重構(gòu)的基礎(chǔ)示例詳解

    Swift?Error重構(gòu)的基礎(chǔ)示例詳解

    這篇文章主要為大家介紹了Swift?Error基礎(chǔ)錯(cuò)誤處理的方法詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-11-11
  • Swift 4.2使用self做為變量名淺析

    Swift 4.2使用self做為變量名淺析

    這篇文章主要給大家介紹了關(guān)于Swift 4.2使用self做為變量名的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2018-09-09
  • swift自定義表格控件(UITableView)

    swift自定義表格控件(UITableView)

    這篇文章主要為大家詳細(xì)介紹了swift自定義表格控件,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-01-01
  • Swift仿選擇電影票的效果并實(shí)現(xiàn)無(wú)限/自動(dòng)輪播的方法

    Swift仿選擇電影票的效果并實(shí)現(xiàn)無(wú)限/自動(dòng)輪播的方法

    這篇文章主要給大家介紹了關(guān)于Swift仿選擇電影票的效果并實(shí)現(xiàn)無(wú)限/自動(dòng)輪播的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2018-08-08
  • swift3.0鍵盤(pán)彈起遮擋輸入框問(wèn)題的解決方案

    swift3.0鍵盤(pán)彈起遮擋輸入框問(wèn)題的解決方案

    這篇文章主要介紹了swift3.0鍵盤(pán)彈起遮擋輸入框問(wèn)題的解決方案,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下
    2016-11-11
  • 通過(guò)示例分析Swift單例模式

    通過(guò)示例分析Swift單例模式

    這篇文章主要介紹了通過(guò)示例分析Swift單例模式的三種方法,分別是全局變量,內(nèi)部變量,dispatch_once方式,有需要的小伙伴可以參考下。
    2015-06-06
  • Swift協(xié)議Protocol介紹

    Swift協(xié)議Protocol介紹

    協(xié)議規(guī)定了用來(lái)實(shí)現(xiàn)某一特定功能所必需的方法和屬性。任意能夠滿足協(xié)議要求的類(lèi)型被稱(chēng)為遵循(conform)這個(gè)協(xié)議。類(lèi),結(jié)構(gòu)體或枚舉類(lèi)型都可以遵循協(xié)議,并提供具體實(shí)現(xiàn)來(lái)完成協(xié)議定義的方法和功能
    2022-08-08

最新評(píng)論