算法|堆排序

大佬教程收集整理的这篇文章主要介绍了算法|堆排序，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

完成阅读您将会了解堆排序的：

1. 算法思想
2. 实现步骤
3. 实践范例（C++/Rust）

1. 算法思想

堆排序（Heap Sort）是数据结构堆的一个具体应用，由 J. W. J. Williams 在1964年发表的堆排序^[1]提出。关于堆的介绍请前往数据结构堆查看。

在堆的基础上，每次取出堆顶，再维护剩余堆的性质即可完成堆排序，如图1^[2]。堆排序时间复杂度为(Theta(nlg n))，空间复杂度(Theta(1))。堆排序是原址排序（In-place Sort），但它是不稳定的排序算法。关于排序的稳定性，请前往快速排序查看。

2. 实现步骤

1. 待排序序列构建为堆；
2. 交换堆顶与堆尾；
3. 更新堆大小；
4. 从堆顶开始堆化；
5. 重复以上过程直至堆大小为1。

3. 实践范例（C++/Rust）

问题描述： 为无序数组A做单调不减排序。 输入：无序数组A 输出：有序数组A 解答思路： 运用对堆排序算法对A进行原址排序。

伪代码1：堆化 变量说明：H(rightarrow)堆数组；i(rightarrow)堆化始发下标；left(rightarrow)左子节点下标；right(rightarrow) 右子节点下标

伪代码2：堆排序 变量说明：A(rightarrow)待排序序列

C++解答：

void _heapfy(auto H, auto i, auto heap_sizE) noexcept {
  auto right = i + 1 << 1, left = right - 1;
  while (left < heap_sizE) {
    auto largest = H[i] < H[left] ? left : i;
    largest = right < heap_size && H[largest] < H[right] ? right : largest;
    if (largest == i)
      break;
    std::swap(H[i], H[largest]);
    i = largest;
    right = i + 1 << 1;
    left = right - 1;
  }
}

void heap_sort(auto A, auto s) noexcept {
  auto i = s >> 1;
  while (i)
    _heapfy(A, --i, s);
  while (s > 1) {
    std::swap(*A, A[--s]);
    _heapfy(A, 0, s);
  }
}

Rust解答：

fn _heapfy<T: std::cmp::PartialOrd>(H: &mut [T], mut i: usize, mut size: usizE) {
    let mut right = i + 1 << 1;
    let mut left = right - 1;
    while left < size {
        let mut largest = if H[i] < H[left] { left } else { i };
        largest = if right < size && H[largest] < H[right] { right } else { largest };
        if largest == i { break; }
        H.swap(i, largest);
        i = largest;
        right = i + 1 << 1;
        left = right - 1;
    }
}

pub fn heap_sort<T:std::cmp::PartialOrd>(A:&mut [T]){
    let mut s=A.len();
    let mut i=s>>1;
    while i>0 {
        i-=1;
        _heapfy(A, i, s);
    }
    while s>1{
        s-=1;
        A.swap(0,s);
        _heapfy(A,0,s);
    }
}

4. 自我测试

伪代码实践： N/A LeetCode选荐： N/A

让每一天足够精致，期待与您的再次相遇! ^_^

大佬总结

以上是大佬教程为你收集整理的算法|堆排序全部内容，希望文章能够帮你解决算法|堆排序所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。