【Day27】[演算法]-堆积排序法 Heap Sort

堆积排序法(Heap Sort)原理是利用「堆积」的资料结构为基础来完成排序。

堆积的介绍可以参考此篇。

操作流程(最大堆积为例):

1. 将阵列转换最大堆积(Max Heap)
2. 将Root与最後一个节点交换
3. 将最後一个节点移除
4. 将剩余为排序完的节点重复1~3步骤，直到所有节点被移除，即完成排序。

下面利用30 20 15 1 10 5由小到大排序

时间复杂度 = 建立堆积 + 移除堆积

建立堆积: Ο(n)
移除堆积: n-1次，(n-1) X Ο(log n) = Ο(n log n)

Ο(n) + Ο(n log n) = Ο(n log n)

平均时间复杂度为: O(n log n)

JavaScript

let data = [30,20,15,1,10,5];

function maxHeapify(arr, n, i){
  let largest = i;
  let l = 2 * i + 1;
  let r = 2 * i + 2;
  
  // 若左子树大於根结点时
  if (l < n && arr[l] > arr[largest]) {
        largest = l; 
  }
  
  // 若右子树大於根结点时
  if (r < n && arr[r] > arr[largest]) {
      largest = r; 
  }
  
  // 根节点不是最大值时
  if (largest != i) { 
    [arr[i],arr[largest]] = [arr[largest],arr[i]]
    // 子树堆积化递回 
    maxHeapify(arr, n, largest); 
  } 
}

 function heapSort(arr) { 
    let n = arr.length
    // 建立最大堆积化
    for (let i = parseInt(n / 2 - 1); i >= 0; i--) {
        maxHeapify(arr, n, i); 
    }
  
    //逐一从最後节点拿出
     for (let i = n - 1; i >= 0; i--) { 
        // 根节点与最後节点交换位置
        [arr[0],arr[i]] = [arr[i],arr[0]]
        maxHeapify(arr, i, 0); 
     } 
 }
 
 heapSort(data);
 console.log(data);//[1, 5, 10, 15, 20, 30]

Python

#Heap Sort

def maxHeapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
  
    if l < n and arr[i] < arr[l]:
        largest = l
  
    if r < n and arr[largest] < arr[r]:
        largest = r
  
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i]
        maxHeapify(arr, n, largest)
  
def heapSort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        maxHeapify(arr, n, i)
  
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        maxHeapify(arr, i, 0)

data = [30,20,15,1,10,5]
heapSort(data)
print(data)
#1,5,10,15,20,30