一、堆排序概述
堆排序是一种基于堆的排序算法,它的时间复杂度为O(nlogn)。它是选择排序的一种改进,在原选择排序的基础上,将未排序元素中最大值与末尾位置交换,可获得从小到大排列的有序数组。
二、堆排序实现原理
堆是一种特殊的树型数据结构,满足任意节点都大于等于(小于等于)左右子节点。堆排序的实现基于堆的特性,在构建堆时,它必须满足两个原则:结构性(完全二叉树)和堆序性(节点都大于等于(小于等于)左右子节点)。在这个堆的基础上,我们可以将堆顶元素(最大值或最小值)与末尾元素交换,然后将剩余未排序的元素重新构建堆。如此反复执行,直到所有元素都排好序。
三、堆排序实现步骤
1.建立堆
通常使用二叉堆来实现,分为最大堆和最小堆。首先,从最后一个非叶子节点开始,依次将每个节点调整为根节点向下的最大(最小)节点。这一过程叫做“堆的调整”。
void heapify(int arr[], int n, int i) { int largest = i; // 父节点(根节点) int l = 2*i + 1; // 左子节点 int r = 2*i + 2; // 右子节点 // 如果左子节点比父节点大 if (l < n && arr[l] > arr[largest]) largest = l; // 如果右子节点比父节点大 if (r < n && arr[r] > arr[largest]) largest = r; // 如果最大的节点不是父节点 if (largest != i) { swap(arr[i], arr[largest]); // 递归调用堆的构建 heapify(arr, n, largest); } }
2.交换堆顶元素和末尾元素
我们将堆顶元素和末尾元素交换,并重新调整剩余元素的堆,以维持堆的特性。
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); } }
四、堆的时间复杂度
堆排序的时间复杂度是O(nlogn),其中建堆的时间复杂度为O(n)。
五、堆排序应用场景
堆排序的应用较广泛,例如Top K问题、求中位数、优先级队列等。
六、堆排序的优缺点
优点:
1.时间复杂度较低,不会因数据数量增加而增加太多的时间。
2.堆排序是一种原地排序算法,不需要额外的存储空间。
3.堆排序是一种稳定的排序算法。
缺点:
1.对于小规模数据排序,堆排序的时间复杂度并不比快速排序、归并排序好。
2.堆排序算法常数较大,不适合于数据量较小的情况。
七、代码实现
#includeusing namespace std; // 调整堆 void heapify(int arr[], int n, int i) { int largest = i; // 父节点(根节点) int l = 2*i + 1; // 左子节点 int r = 2*i + 2; // 右子节点 // 如果左子节点比父节点大 if (l < n && arr[l] > arr[largest]) largest = l; // 如果右子节点比父节点大 if (r < n && arr[r] > arr[largest]) largest = r; // 如果最大的节点不是父节点 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); } } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]); heapSort(arr, n); cout << "排序后的数组:\n"; for (int i=0; i