—堆排序—
堆排序可以说是一种利用堆的概念来排序的选择排序。
算法描述
具体算法描述如下：
- <1>.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- <2>.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- <3>.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后 再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元 素个数为n-1，则整个排序过程完成。
代码实现
//维护堆
void Heap(int a[], int n, int i) //（数组，数组长度，下标）
{
int largest = i;
int lson = i * 2 + 1;
int rson = i * 2 + 2;
if (lson < n && a[largest] < a[lson]) //lson是下标 要小于数组的长度 不能等于
largest = lson;
if (rson < n && a[largest] < a[rson]) //同上
largest = rson;
if (largest != i)
{
int temp = a[largest];
a[largest] = a[i];
a[i] = temp;
Heap(a, n , largest); //递归维护
}
}
//堆排序接口
void Heap_Sort(int a[],int n)
{
//建堆
for (int i = n / 2 - 1; i >= 0; --i) // n为数组长度，建堆是从建堆要从第一个非叶节点进行循环,
{ // 对每一个非叶节点下滤
Heap(a, n, i);
}
//排序
for (int i = n - 1; i > 0; --i)
{
int temp = a[i];
a[i] = a[0];
a[0] = temp;
//调整堆 对根节点下滤
Heap(a, i, 0);
}
}
算法分析
平均情况：T(n) = O(nlogn)
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
稳定性
- 不稳定
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
