shopex网站首页空白,免费网站制作开发公司,WordPress预各式华化,自由贸易区的建设网站目录 1.基本原理2.例子3.代码实现 本文主要介绍堆排序的原理、例子以及代码实现。
1.基本原理
堆排序#xff08;Heap Sort#xff09;是一种基于比较的排序算法#xff0c;它的工作原理是首先将待排序的序列构造成一个大顶堆或小顶堆#xff0c;然后交换堆顶元素和最后一… 目录 1.基本原理2.例子3.代码实现 本文主要介绍堆排序的原理、例子以及代码实现。
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.hvoid 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 in-1; i0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}void printArray(int arr[], int n) {for (int i0; in; 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 函数用于打印数组。
