大家好,又见面了,我是全栈君。
堆排序(Heapsort)是指利用堆这样的数据结构所设计的一种排序算法。
堆积是一个近似全然二叉树的结构。并同一时候满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
一、堆的结构
一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。
如第0个结点左右子结点下标分别为1和2。
这是从0開始的结构。
二、堆的分类
堆分为最大堆(大顶堆)和最小堆(小顶堆),顾名思义就是父节点和左右孩子节点的关系,假设父节点大于全部的子节点的堆就是大顶堆,父节点小于全部子节点的堆就是小顶堆,选择大顶堆和小顶堆决定了排序的顺序,是从大到小还是从小到大排序。
三、堆的操作
1、创建及堆的插入
//k是插入元素的位置 void swim(int a[], int k) { int j; while(k > 0) { j = (k - 1) / 2; //是k的父节点 if(a[j] > a[k]) { swap(&a[j], &a[k]); k = j; } else { break; } } }
2、删除
//n是节点总数。删除总是从根节点開始 void sink(int a[], int n, int i) { int j; while((2 * i + 1) < n) { j = 2 * i + 1; if(j + 1 < n && a[j] > a[j+1]) j++; if(a[j] < a[i]) { swap(&a[i], &a[j]); i = j; } else { break; } } }
3、建堆
void build_heap(int a[], int n) { int i; for(i = (n/2 -1); i >= 0; i--) { sink(a, n, i); } }
四、堆排序
void heap_sort(int a[], int n) { int i; for(i = n - 1; i > 0; i--) { swap(&a[i], &a[0]); sink(a, i, 0); } }
最后将总体做了一个測试,代码例如以下:
#include <stdio.h>void swap(int *a, int *b){ int tmp = *a; *a = *b; *b = tmp;}//k是插入元素的位置void swim(int a[], int k){ int j; while(k > 0) { j = (k - 1) / 2; //是k的父节点 if(a[j] > a[k]) { swap(&a[j], &a[k]); k = j; } else { break; } }}//n是节点总数。删除总是从根节点開始void sink(int a[], int n, int i){ int j; while((2 * i + 1) < n) { j = 2 * i + 1; if(j + 1 < n && a[j] > a[j+1]) j++; if(a[j] < a[i]) { swap(&a[i], &a[j]); i = j; } else { break; } }}void build_heap(int a[], int n){ int i; for(i = (n/2 -1); i >= 0; i--) { sink(a, n, i); }}void heap_sort(int a[], int n){ int i; for(i = n - 1; i > 0; i--) { swap(&a[i], &a[0]); sink(a, i, 0); }}int main(){ int a[4] = {10, 40, 30, 5}; swim(a, 3); int i; for(i = 0; i < 4; i++){ printf("%d\t", a[i]); } printf("\n"); int b[4] = {50, 10, 20, 40}; sink(b, 4, 0); for(i = 0; i < 4; i++){ printf("%d\t", b[i]); } printf("\n"); int c[10] = {9, 12, 17, 30, 50, 20, 60 , 65, 4, 19}; build_heap(c, 10); for(i = 0; i < 10; i++){ printf("%d\t", c[i]); } printf("\n"); heap_sort(c, 10); for(i = 0; i < 10; i++){ printf("%d\t", c[i]); } printf("\n");}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115277.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...