目录
本文主要介绍堆排序的原理、例子以及代码实现。
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);
}
在这段代码中,heapify 函数用于构造大顶堆,heapSort 函数用于进行堆排序,swap 函数用于交换两个元素的值,printArray 函数用于打印数组。
标签:10,arr,int,元素,堆排序,largest From: https://www.cnblogs.com/lanyangsh/p/17872767.html