算法笔记005:堆排序【变治法】

谁践踏了优雅 2022-07-14 12:00 22阅读 0赞

--------------------

# **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  具体编码** ##

![复制代码][copycode.gif]

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();
            }    
        }
    }

![复制代码][copycode.gif]

## **2.4  运行结果截图** ##

**![927750-20161208194142741-851520793.png][]**

每天一小步，成就一大步

[copycode.gif]: /images/20220714/1dfdccf545e64bb4b81849874d8a3027.png
[927750-20161208194142741-851520793.png]: /images/20220714/59512a66edbf45538890ce6ec8df45b1.png