Swift实现堆排序算法的代码示例

heavyelephant 发布于2年前
0 条问题

算法思想
堆排序利用了最大堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
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]

需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。