高级程序员的靠山之：堆排序的使用

╰+哭是因爲堅強的太久メ 2022-01-23 23:55 136阅读 0赞

下面来介绍一下堆排序的具体实例使用，请大家有兴趣一起参考参考！！！

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1.  大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2.  小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

### 1. 算法步骤 ###

1.  创建一个堆 H\[0……n-1\]；
2.  把堆首（最大值）和堆尾互换；
3.  把堆的尺寸缩小 1，并调用 shift\_down(0)，目的是把新的数组顶端数据调整到相应位置；
4.  重复步骤 2，直到堆的尺寸为 1。

## 2.代码实现 ##

### JavaScript实现 ###

var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
    
    function buildMaxHeap(arr) {   // 建立大顶堆
        len = arr.length;
        for (var i = Math.floor(len/2); i >= 0; i--) {
            heapify(arr, i);
        }
    }
    
    function heapify(arr, i) {     // 堆调整
        var left = 2 * i + 1,
            right = 2 * i + 2,
            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);
        }
    }
    
    function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    function heapSort(arr) {
        buildMaxHeap(arr);
    
        for (var i = arr.length-1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0);
        }
        return arr;
    }

### Python实现 ###

def buildMaxHeap(arr):
        import math
        for i in range(math.floor(len(arr)/2),-1,-1):
            heapify(arr,i)
    
    def heapify(arr, i):
        left = 2*i+1
        right = 2*i+2
        largest = i
        if left < arrLen and arr[left] > arr[largest]:
            largest = left
        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]
    
    def heapSort(arr):
        global arrLen
        arrLen = len(arr)
        buildMaxHeap(arr)
        for i in range(len(arr)-1,0,-1):
            swap(arr,0,i)
            arrLen -=1
            heapify(arr, 0)
        return arr

### Go实现 ###

func heapSort(arr []int) []int {
            arrLen := len(arr)
            buildMaxHeap(arr, arrLen)
            for i := arrLen - 1; i >= 0; i-- {
                    swap(arr, 0, i)
                    arrLen -= 1
                    heapify(arr, 0, arrLen)
            }
            return arr
    }
    
    func buildMaxHeap(arr []int, arrLen int) {
            for i := arrLen / 2; i >= 0; i-- {
                    heapify(arr, i, arrLen)
            }
    }
    
    func heapify(arr []int, i, arrLen int) {
            left := 2*i + 1
            right := 2*i + 2
            largest := i
            if left < arrLen && arr[left] > arr[largest] {
                    largest = left
            }
            if right < arrLen && arr[right] > arr[largest] {
                    largest = right
            }
            if largest != i {
                    swap(arr, i, largest)
                    heapify(arr, largest, arrLen)
            }
    }
    
    func swap(arr []int, i, j int) {
            arr[i], arr[j] = arr[j], arr[i]
    }

### Java实例 ###

public class HeapSort implements IArraySort {
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception {
            // 对 arr 进行拷贝，不改变参数内容
            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;
        }
    
    }

### PHP实例 ###

### C实例 ###

#include <stdio.h>
    #include <stdlib.h>
    
    void swap(int *a, int *b) {
        int temp = *b;
        *b = *a;
        *a = temp;
    }
    
    void max_heapify(int arr[], int start, int end) {
        // 建立父節點指標和子節點指標
        int dad = start;
        int son = dad * 2 + 1;
        while (son <= end) { // 若子節點指標在範圍內才做比較
            if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
                son++;
            if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
                return;
            else { // 否則交換父子內容再繼續子節點和孫節點比較
                swap(&arr[dad], &arr[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    }
    
    void heap_sort(int arr[], int len) {
        int i;
        // 初始化，i從最後一個父節點開始調整
        for (i = len / 2 - 1; i >= 0; i--)
            max_heapify(arr, i, len - 1);
        // 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
        for (i = len - 1; i > 0; i--) {
            swap(&arr[0], &arr[i]);
            max_heapify(arr, 0, i - 1);
        }
    }
    
    int main() {
        int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        heap_sort(arr, len);
        int i;
        for (i = 0; i < len; i++)
            printf("%d ", arr[i]);
        printf("\n");
        return 0;
    }

### C++实例 ###

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    void max_heapify(int arr[], int start, int end) {
        // 建立父節點指標和子節點指標
        int dad = start;
        int son = dad * 2 + 1;
        while (son <= end) { // 若子節點指標在範圍內才做比較
            if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
                son++;
            if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
                return;
            else { // 否則交換父子內容再繼續子節點和孫節點比較
                swap(arr[dad], arr[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    }
    
    void heap_sort(int arr[], int len) {
        // 初始化，i從最後一個父節點開始調整
        for (int i = len / 2 - 1; i >= 0; i--)
            max_heapify(arr, i, len - 1);
        // 先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢
        for (int i = len - 1; i > 0; i--) {
            swap(arr[0], arr[i]);
            max_heapify(arr, 0, i - 1);
        }
    }
    
    int main() {
        int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        heap_sort(arr, len);
        for (int i = 0; i < len; i++)
            cout << arr[i] << ' ';
        cout << endl;
        return 0;
    }