首页 > 代码库 > 堆排序
堆排序
堆的定义如下：
n个元素的序列{k0,k1,...,ki,…,k(n-1)}当且仅当满足下关系时，称之为堆。
"ki<=k(2i),ki<=k(2i+1);或ki>=k(2i),ki>=k(2i+1).（i=1,2,…,[n/2])"
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，
若完全二叉树中每一个节点的值都大于或等于任意一个子节点的值（如果有的话），称之为大顶堆。
若完全二叉树中每一个节点的值都小于或等于任意一个子节点的值（如果有的话），称之为小顶堆。
由此，若序列{k0,k1,…,k(n-1)}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
倘若给堆中每一个节点都赋予一个整数值标签，根节点被标记为0，对于每一个标记为i的节点，其左子节点（若存在的话）被标记为2*i+1，其右子节点（若存在的话）被标记为2*i+2，对于一个标记为i的非根节点，其父节点被标记为（i-1）/2。使用这个标记，我们能够将堆存储在数组中，节点存储在数据中的位置就使其标签。
堆排序示例：
规则：
1.初始化i=0，先后查看节点i的左子节点2*i+1、右子节点2*i+2，如果发现违反了堆的定义，则交换2个节点的值（编号只跟位置有关，也就是数组中的下标），置i=0
2.如果没有发现违反堆的定义，则置i=i+1，返回步骤1
3.当i==n的时候，将0号位置上的元素放置到n号位置上，置i=0，置n=n-1，返回步骤1，对位置为[0, n]范围内的元素重复上述操作
示意图如下：数组中的值依次是17,8,45,84,2,94，这次排序的最终结果是把最大的94放到了序列末尾
下面是剩下的元素的排序过程：
代码如下：
1 package sorts; 2 3 public class Heap // 小顶堆，也就是说小的数据在堆顶部 4 { 5 6 7 public void heap_sort(int[] a,int n){ 8 if(n>0){ 9 init_sort(a,n);//初始化堆，找出最大的放在堆顶10 swap(a, 0, n);11 heap_sort(a, n-1); // recursively12 }else{13 print(a);14 }15 }16 17 private void swap(int[] a, int index1, int index2) {18 a[index1] = a[index1] + a[index2];19 a[index2] = a[index1] - a[index2];20 a[index1] = a[index1] - a[index2];21 }22 23 private void print(int[] a){24 for(int i=0;i<a.length;i++){25 System.out.print(a[i]+" ");26 }27 System.out.println();28 }29 30 private void init_sort(int[] a,int n){ 31 int m=(n+1)/2; 32 for(int i=0;i<m;i++){33 boolean flag=build_heap(a,n,i);34 //如果孩子之间有交换，就要重新开始35 if(flag){36 i=-1;37 }38 }39 40 41 }42 //返回一个标记，如果有根与孩子交换就要重新从顶根开始查找不满足最大堆树结构43 private boolean build_heap(int a[],int n,int i){44 int l_child=2*i+1;//左孩子45 int r_child=2*i+2;//右孩子46 if(r_child>n){ //判断是否有右孩子，没有的话直接比较，小于右孩子则交换47 if(a[i]<a[l_child]){48 swap(a, i, l_child);49 return true;50 }else{51 return false;52 }53 }54 //在根与两个孩子之间找出最大的那个值进行交换55 if(a[i]<a[l_child]){56 if(a[l_child]>a[r_child]){57 //交换根与左孩子的值58 swap(a, i, l_child);59 return true;60 }else{61 //交换根与右孩子的值62 swap(a, i, r_child);63 return true;64 }65 }else if(a[i]<a[r_child]){66 //交换根与右孩子的值67 swap(a, i, r_child);68 return true;69 }70 return false;71 72 }73 public static void main(String[] args) 74 {75 Heap h=new Heap();76 int [] a={17,8,45,84,2,94};77 h.heap_sort(a,a.length-1);78 }79 }
堆排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。