首页 > 代码库 > 算法笔记005:堆排序【变治法】
算法笔记005:堆排序【变治法】
目录
1 问题描述
2 解决方案
2.1 堆排序原理简介
2.2 变治法原理简介
2.3 具体编码
2.4 运行结果截图
1 问题描述
(1)实验题目
用基于变治法的堆排序算法对任意一组给定的数据进行排序
(2)实验目的
1)深刻理解并掌握变治法的设计思想;
2)掌握堆的概念以及如何用变治法把任意给定的一组数据改变成堆;
3)提高应用变治法设计算法的技能。
(3)实验要求
1)设计与实现堆排序算法;
2)待排序的数据可以手工输入(通常规模比较小,10个数据左右),用以检测程序的正确性;也可以计算机随机生成(通常规模比较大,1500-3000个数据左右),用以检验(用计数法)堆排序算法的时间效率。
2 解决方案
2.1 堆排序原理简介
堆可以定义为一颗二叉树,树的节点中包含键(每个节点是一个键),并且满足下面两个条件:
(1)树的形状要求——这颗二叉树是基本完备的(或者简称为完成二叉树),这意味着,树的每一层都是满的,除了最后一层最右边的元素有可能缺位。
(2)父母优势要求,又称为堆特性——每一个节点的键都要大于或等于它子女的键(对于任何孩子节点也要自动满足父母优势要求)。
2.2 变治法原理简介
变治法:首先,在“变”的阶段,出于这一或者那样的原因,把问题的实例变得更容易求解(PS:类似本文求解问题,在排序前先把数组中数进行成堆处理);然后,在第二阶段或者说“治”的阶段,对实例进行求解。
根据我们对问题实例的变换方式,变治思想有3种主要的类型:
(1)变换为同样问题的一个更简单或者更方便的实例——我们称之为实例化简;
(2)变换为同样实例的不同表现——我们称之为改变表现;
(3)变换为另一个问题的实例,这种问题的算法是已知的——我们称之为问题的化简。
2.3 具体编码
package com.liuzhen.heapsort; public class HeapSort { /*将array[a]和array[b]、array[c]中最大值进行比较,如果较小则将array[a]与array[b]、array[c]中最大值 进行交换,否则直接返回数组array*/ public static int[] getMaxA(int[] array,int a,int b ,int c){ int temp = 0; if(array[b] >= array[c]){ if(array[a] < array[b]){ temp = array[a]; array[a] = array[b]; array[b] = temp; } } else{ if(array[a] < array[c]){ temp = array[a]; array[a] = array[c]; array[c] = temp; } } return array; } //根据堆排序父母优势规则,返回一个给定长度的数组的成堆结果 public static int[] getHeapSort(int[] array , int len){ boolean judge = true; while(judge){ //根据堆排序父母优先规则,对数组array进行排序 for(int i = 1;i <= len/2;i++){ if((2*i+1) < len) array = getMaxA(array,i,(2*i),(2*i+1)); if((2*i) == len-1){ //当2*i == len-1时,说明array[i]只有一个左孩子节点a[2*i] int temp = 0; if(array[i] < array[2*i]){ temp = array[i]; array[i] = array[2*i]; array[2*i] = temp; } } } //遍历数组array,一旦出现根节点小于其叶子节点时,跳出for循环 int j; for(j = 1;j < len/2;j++){ if((2*j+1) < len){ if(array[j] < array[2*j]) break; if(array[j] < array[2*j+1]) break; } if((2*j) == len-1){ if(array[j] < array[2*j]) break; } } if(j == len/2) //如果j==len/2,说明遍历结果符合堆排序规则,直接结束while循环 judge = false; } return array; } //使用数组成堆,对一个数组元素进行从小到大排序,并返回排序后的结果 public static int[] getResultSort(int[] array , int len){ array = getHeapSort(array , len); //首先对数组进行堆排序处理 int temp = 0; //数组值交换中间变量 int sortLen = len; //排序过程中,需要重新进行堆排序的数组长度,并初始化为array的总长度 while(sortLen > 2){ // for(int i = 1;i < len;i++) // System.out.print(array[i]+"\t"); // System.out.println(); temp = array[1]; //交换array[0]和array[sortLen-1]的值,即把最大的值放在未排序的数组最后一位 array[1] = array[sortLen-1]; array[sortLen-1] = temp; sortLen = sortLen - 1; //交换成功后,未排序的数组长度自动减1 array = getHeapSort(array,sortLen); //对未排序的数组,重新进行堆排序 } return array; } //初始化一个长度为n的随机数组 public static int[] initArray(int n){ int[] result = new int[n]; result[0] = 0; for(int i = 1;i < n;i++) result[i] = (int)(Math.random()*1000); //采用随机函数随机生成0~1000之间的数 return result; } public static void main(String args[]){ int[] array = {0,1,4,5,3,5,23,45,12,23,34,56,78,23,24,25}; //此处定义数组,对array[1]到array[len-1]进行排序 int len = array.length; int[] result = getResultSort(array,len); System.out.println("手动输入数组,使用堆排序,最终排序结果:"); for(int i = 1;i < len;i++){ System.out.print(result[i]+"\t"); } System.out.println(); System.out.println(); int[] oneArray = initArray(1000); int len1 = 1000; int[] result1 = getResultSort(oneArray,len1); System.out.println("系统随机生成的长度为1000的数组(其值均在0~1000之间),使用堆排序,最终排序结果:"); for(int j = 1;j < len1;j++){ System.out.print(result1[j]+"\t"); if(j%15 == 0) System.out.println(); } } }
2.4 运行结果截图
算法笔记005:堆排序【变治法】