IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 堆排序算法实现 -> 正文阅读

[数据结构与算法]堆排序算法实现

基本思想:堆排序使用了堆这种完全二叉树数据结构,使得子节点的键值总是小于(或者大于)它的父节点,然后逐个选出根节点,直到剩下最后一个节点,最终完成排序。

堆数据结构的实现利用了一维数组,节点满足如下条件:

第i个父节点的左子节点索引为 2i
第i个父节点的右子节点索引为 2
i+1
算法实现:

#!/usr/bin/awk -f
# heap sort
BEGIN{
        print "排序:"
        print "输入示例:   8 1 6 3 5 2 4 7"
}
{ 
        for( i = 1; i <= NF; i++) 
                A[i] = $i ; 
        hsort(A, NF)
        ## 显示结果
        show(A,1,NF)
        nl()
}
function nl() {
        printf("---------------------------------\n")
}
function show(arr,start ,end , j, i) {
        for( i = start ; i < end ; i++)
                printf("%d%s", arr[i], i == j ? "|":" ")
        printf("%d%s\n", arr[i], i == j ? "|":"")
}

function swap(A,i,j, t){
        t = A[i]; A[i] = A[j]; A[j] = t
}
## heap sort
function hsort(A, n, i){
        # 建堆
        for( i = int(n/2); i >= 1; i--) {
                heapify(A, i, n)
        }
        show(A, 1,n)
        # 挑出父节点后重新建堆 #
        for( i = n; i > 1 ; i--) {
                swap(A, 1, i)
                heapify(A, 1, i-1)
                show(A, 1,n, i-1)
        }
}
# 构建堆
function heapify(A, left, right,  p,c) {
        for( p = left; (c = 2*p) <= right; p = c){
                if( c < right && A[c+1] > A[c])
                        c++
                if( A[p] < A[c])
                        swap(A, c, p)
        }
}

执行结果:

./hsort.awk  
8 1 6 3 5 2 4 7  
8 7 6 3 5 2 4 1  
7 5 6 3 1 2 4|8  
6 5 4 3 1 2|7 8  
5 3 4 2 1|6 7 8  
4 3 1 2|5 6 7 8  
3 2 1|4 5 6 7 8  
2 1|3 4 5 6 7 8  
1|2 3 4 5 6 7 8  
1 2 3 4 5 6 7 8
---------------------------------

下图展示了堆排序的过程示例:
在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-26 10:26:26  更:2021-09-26 10:27:09 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 4:14:08-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码