赞
踩
堆排序是一种利用堆数据结构实现的排序算法。首先,它将待排序的数组构建成一个大顶堆或小顶堆。然后,通过不断将堆顶元素(最大或最小)与末尾元素交换并重新调整堆,使得数组逐渐有序。最后,当堆的大小减至1时,排序完成。堆排序的时间复杂度为O(nlogn),空间复杂度为O(1),具有稳定性和适用性广的优点。
堆排序的基本思想是将待排序的序列构造成一个大顶堆或小顶堆,此时,整个序列的最大值(或最小值)就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值或最小值),然后将剩余的堆重新构造成一个堆,这样就会得到新的最大值(或最小值)。如此反复执行,便能得到一个有序序列了。
具体实现时,首先需要根据给定的待排序数组构建一个初始堆。构建堆的过程通常是从最后一个非叶子节点开始,向上遍历每个节点,对每个节点进行下沉操作,以确保每个节点都满足堆的性质。下沉操作是堆排序中的关键步骤,它通过比较节点与其子节点的值,确保父节点的值大于(对于大顶堆)或小于(对于小顶堆)其子节点的值。
在堆构建完成后,堆的根节点就是序列中的最大(或最小)元素。将其与堆数组的最后一个元素交换,然后移除最后一个元素(或将其视为已排序部分),此时堆的大小减一。接着,对剩余部分重新进行下沉操作,以恢复堆的性质。这个过程重复进行,直到堆的大小减至1,此时序列已经完全排序。
堆排序的时间复杂度为O(nlogn)
,其中n
是待排序序列的长度。这是因为构建初始堆的时间复杂度为O(n)
,而每次移除堆顶元素并重新构建堆的时间复杂度为O(logn)
。由于这个过程需要重复n
次,所以总的时间复杂度为O(nlogn)
。堆排序是一种原地排序算法,因为它只涉及到元素之间的交换和移动,不需要额外的存储空间。
值得注意的是,堆排序是一种不稳定的排序算法。这是因为在构建堆和下沉的过程中,相同值的元素可能会改变它们的相对顺序。因此,如果稳定性是一个重要的考量因素,那么可能需要选择其他的排序算法,如归并排序或冒泡排序。
堆排序是一种基于二叉堆数据结构所设计的排序算法,它兼具选择排序和插入排序的优点,并在许多情况下展现出其独特的性能特点。
综上所述,堆排序是一种高效、稳定、易于实现且适用性广的排序算法。尽管它在某些方面可能不如其他排序算法(如快速排序或归并排序)出色,但在许多实际应用中,它仍然是一种非常有用的排序工具。
堆排序
堆排序是一种基于二叉堆的排序算法,它通过构建最大堆或最小堆,然后不断删除堆顶元素并调整堆结构来实现排序。动图展示通常能够直观地展示堆排序的整个过程,包括初始堆的构建、堆顶元素的删除和堆的调整等步骤。通过动图展示,可以清晰地看到堆排序算法的执行过程,从而更好地理解和掌握该算法的实现原理。
详细可看这篇——堆
ps:上面是建堆的时间复杂度不是堆排序的时间复杂度
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。
#include<stdio.h> #include<stdlib.h> #include<time.h> void HeapSort(int* a, int n); void PrintArray(int* a, int n); void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) { child++; } if (a[child] > a[parent]) { Swap(&a[parent], &a[child]); parent = child; child = child * 2 + 1; } else { break; } } } void TestHeapSort() { int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 }; //int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 }; PrintArray(a, sizeof(a) / sizeof(int)); HeapSort(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); } void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void TestOP() { srand(time(0)); const int N = 10000; int* a1 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); } int begin1 = clock(); HeapSort(a1, N); int end1 = clock(); printf("HeapSort:%d\n", end1 - begin1); free(a1); } void HeapSort(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } } int main() { TestHeapSort(); TestOP(); return 0; }
这段代码实现了堆排序算法。
首先,AdjustDown
函数用来调整以parent
为根节点的子树,使之符合大顶堆的性质。在每一次调整中,函数会找到parent
节点的左右孩子中较大的那个,并与parent
节点进行比较。如果孩子节点较大,则交换它们的值,并将parent
更新为较大孩子的位置,继续向下调整。如果孩子节点不大于parent
节点,则停止调整。这个过程保证了每一次调整都能将较大的元素移动到较下面的位置。
HeapSort
函数首先通过调用AdjustDown
函数将待排序数组调整为一个大顶堆。然后,它通过不断交换堆顶元素与最后一个元素,并缩小堆的范围来对堆进行排序。在每一次交换后,需要调用AdjustDown
函数将交换后的堆顶元素移动到合适的位置。
最终,经过多次交换与调整,待排序数组就会按照从小到大的顺序排列好。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。