堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
- 大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于升序排列；
- 小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列；
堆排序的平均時(shí)間復(fù)雜度為 Ο(nlogn)。不穩(wěn)定
首先理解一個(gè)東西 heapify
給定一個(gè)堆（完全二叉樹）
dui
- 把給定節(jié)點(diǎn)作為父節(jié)點(diǎn)，與其兩個(gè)子節(jié)點(diǎn)比較，讓最大的成為父節(jié)點(diǎn)。
- 產(chǎn)生交換之后，自然下一層就會(huì)受影響，那么需要用遞歸的方法對(duì)下一層的各種子樹再進(jìn)行heapify操作。
- 當(dāng)遞歸到最后的子節(jié)點(diǎn)是，遞歸結(jié)束。
這時(shí)就完成了把最大的數(shù)放在對(duì)頂?shù)牟僮?/strong>
image.png
算法步驟
-
將待排序序列構(gòu)建成一個(gè)堆 H[0……n-1]，根據(jù)（升序降序需求）選擇大頂堆或小頂堆；
比如第一次換好的是：
image.png -
把堆首（最大值）和堆尾互換（意思就是最大的沉下去，或者砍掉最后一個(gè)子節(jié)點(diǎn)）；
image.png 去掉最后一個(gè)元素（已找到的最大的），即把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；
重復(fù)步驟 2，直到堆的尺寸為 1。就是再heapify再砍 最后砍光就成功了。
Python
注：這個(gè)代碼里是第一次建立堆時(shí)先heapify，后面就方便直接砍再heapify，也可以先按照原始數(shù)組建堆，再執(zhí)行排序。
class Solution:
def MySort(self , arr ):
# write code here
global arrLen
arrLen = len(arr)
# 先建大頂堆，把最大的元素放在對(duì)頂，并且父>子
def buildMaxHeap(arr):
import math
# floor:向下取整，range（父節(jié)點(diǎn)，到-1，步長(zhǎng)-1）
for i in range(math.floor(len(arr)/2), -1, -1):
heapify(arr, i)
def heapify(arr, i):
leaf = 2*i + 1 #左孩子
right = 2*i + 2 #右孩子
largest = i
# 比較三個(gè)最大，最大的當(dāng)爸, 防止越界：leaf < arrLen
if leaf < arrLen and arr[leaf] > arr[largest]:
largest = leaf
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i :
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
buildMaxHeap(arr)
for i in range(len(arr)-1, 0, -1):
#堆頂和最后一個(gè)元素交換
swap(arr, 0, i)
#再砍去最后一個(gè)元素
arrLen -= 1
heapify(arr, 0)
return arr
Java
public class HeapSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對(duì) arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int len = arr.length;
buildMaxHeap(arr, len);
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}
private void buildMaxHeap(int[] arr, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i, len);
}
}
private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
