当前位置：首页 > article >正文

堆排序算法

article 2024/11/16 9:01:32

1.基本原理

堆排序（Heap Sort）是一种基于比较的排序算法，它的工作原理是首先将待排序的序列构造成一个大顶堆或小顶堆，然后交换堆顶元素和最后一个元素，然后将剩余元素重新调整为大顶堆或小顶堆，再交换堆顶元素和最后一个元素，如此反复，直到所有元素都排好序。

堆排序的步骤如下：

构造大顶堆（或小顶堆），对于每一个非叶子节点，保证其值大于（或小于）其子节点的值。
将堆顶元素与最后一个元素交换，然后将剩余元素重新调整为大顶堆（或小顶堆）。
重复步骤2，直到所有元素都排好序。

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。

2.例子

假设我们有一个待排序的数组 [4, 10, 3, 5, 1]，我们想要对其进行升序排序，可以使用堆排序，具体步骤如下：

首先，我们将数组构造成一个大顶堆。大顶堆是一种满足父节点的值大于或等于其子节点值的二叉树。构造大顶堆后，数组变为 [10, 5, 3, 4, 1]。
然后，我们将堆顶元素（即当前最大的元素10）与最后一个元素1交换位置，然后将剩余的元素（即除去最后一个元素的其他元素）重新调整为大顶堆。交换并调整后，数组变为 [5, 4, 3, 1] 和 [10]。
我们再次将堆顶元素5与最后一个元素1交换位置，然后将剩余的元素重新调整为大顶堆。交换并调整后，数组变为 [4, 1, 3]、[5, 10]。
重复上述步骤，直到所有元素都排好序，最终得到的数组为 [1, 3, 4, 5, 10]。

以上就是一个堆排序的具体例子。

3.代码实现

以下是堆排序的C语言实现：

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i=n-1; i>=0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

void printArray(int arr[], int n) {
    for (int i=0; i<n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array is \n");
    printArray(arr, n);
}