深圳手机网站建设,西安网站有哪些手续费,c .net网站开发实例,网站 备案 拍照【八大经典排序算法】堆排序 一、概述二、思路解读三、代码实现#xff08;大堆为例#xff09; 一、概述
堆排序是J.W.J. Williams于1964年提出的。他提出了一种利用堆的数据结构进行排序的算法#xff0c;并将其称为堆排序。堆排序是基于选择排序的一种改进#xff0c;通… 【八大经典排序算法】堆排序 一、概述二、思路解读三、代码实现大堆为例 一、概述
堆排序是J.W.J. Williams于1964年提出的。他提出了一种利用堆的数据结构进行排序的算法并将其称为堆排序。堆排序是基于选择排序的一种改进通过维护一个堆来选择最大或最小的元素并将其放置在数组的末尾然后对剩余的元素进行递归调用堆排序。
堆排序在其初期的版本中存在一些性能问题例如在构建堆的过程中需要频繁的调整堆的结构导致性能的下降。为了改进这个问题人们提出了一种称为“堆调整”的操作将调整堆的过程优化为一次遍历从而提高了性能。此外还有一些其他的改进方法如使用二叉堆来代替普通堆使用自底向上的构建堆的方法等。
堆排序作为一种经典的排序算法经过多年的发展与改进已经成为一种高效稳定的排序算法并在实际应用中得到广泛的应用。 二、思路解读
我们知道堆排序是一种基于堆数据结构的排序算法所以堆排序分为以下几步
①构建大堆或小堆。这里我们从数组的最后一个数据的父节点开始采用向下调整算法来建堆。 向下调整算法有一个前提左右子树必须是一个堆才能调整。同时还要注意是调大堆还是小堆。 调小(大)堆堆顶元素和孩子中最小大的节点比较如果父节点大于小于较小的子节点子两者交换。不断向下调整到合适位置。调大堆和较大孩子比较
②将堆中最大或最小的元素即堆顶元素与数组中最后一个元素交换位置然后将堆的大小减1。将交换后的堆顶元素进行向下调整直到堆再次满足堆性质。
③ 重复上述步骤直到堆的大小为1此时整个数组就有序了 三、代码实现大堆为例
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[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{//升序建大堆for (int i (n - 2) / 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--;}
}时间复杂度O(N*logN) 空间复杂度O(1)
