堆排序（包括升序和降序，Arraylist 实现）

怼烎@ 2021-09-23 03:18 323阅读 0赞

补充上一篇  
利用Arraylist实现的堆排序(包含升序和降序)

import java.util.ArrayList;
    import java.util.Random;
    
    //采用Arraylist实现堆排序
    public class Main {
        //为了方便 采用索引从 1 开始
        private static int N = 10;// 数组的大小
        static Random rand = new Random();
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            test_HeapSort_DES();
            test_HeapSort_ASC();
        }
    
        private static void test_HeapSort_DES() {
            // TODO Auto-generated method stub
            ArrayList<Integer> arrayList=new ArrayList<>();
            arrayList.add(-1);
            for (int i = 1; i <= N; i++) {
                arrayList.add(rand.nextInt(1000));
            }
            System.out.println("排序前：");
            print(arrayList);       
    
            System.out.println("排序后(降序)：");
            print(HeapSort_DES(arrayList));
    
        }
        private static void test_HeapSort_ASC() {
            // TODO Auto-generated method stub
            ArrayList<Integer> arrayList=new ArrayList<>();
            arrayList.add(-1);
            for (int i = 1; i <= N; i++) {
                arrayList.add(rand.nextInt(1000));
            }
            System.out.println("排序前：");
            print(arrayList);       
    
            System.out.println("排序后(升序)：");
            print(HeapSort_ASC(arrayList));
    
        }
    
        private static ArrayList<Integer> HeapSort_ASC(ArrayList<Integer> arrayList) {
            // TODO Auto-generated method stub
            Build_Max_Heap(arrayList);
            ArrayList<Integer> temp=new ArrayList<>();
            temp.add(-1);//方便打印
            while(arrayList.size()>1){
                temp.add(1,arrayList.get(1));//与逆序的差别 每次插在第一个
                arrayList.remove(1);
                Max_Heapfy(arrayList,1);
            }
            return temp;
        }
    
        private static ArrayList<Integer> HeapSort_DES(ArrayList<Integer> arrayList) {
            // TODO Auto-generated method stub
            Build_Max_Heap(arrayList);
            ArrayList<Integer> temp=new ArrayList<>();
            temp.add(-1);//方便打印
            while(arrayList.size()>1){
                temp.add(arrayList.get(1));
                arrayList.remove(1);
                Max_Heapfy(arrayList,1);
            }
            return temp;
    
        }
    
        private static void Build_Max_Heap(ArrayList<Integer> arrayList) {
            // TODO Auto-generated method stub
            int length=arrayList.size()-1;
            for(int i=length/2;i>0;i--){
                Max_Heapfy(arrayList, i);
            }
        }
    
        private static void Max_Heapfy(ArrayList<Integer> arrayList, int i) {
            // TODO Auto-generated method stub
            if(arrayList.size()<=1)
                return;
            int l=left(i);
            int r=right(i);
            int largest=0;
            if(l<arrayList.size() && arrayList.get(l)>arrayList.get(i)){
                largest=l;
            }else{
                largest=i;
            }
            if(r<arrayList.size() && arrayList.get(r)> arrayList.get(largest)){
                largest=r;
            }
            if(largest!=i){
                int temp =  arrayList.get(i);
                arrayList.set(i, arrayList.get(largest));
                arrayList.set(largest, temp);       
                Max_Heapfy(arrayList,largest);
            }       
        }
    
        private static int right(int i) {
            // TODO Auto-generated method stub
            return 2*i+1;
        }
    
        private static int left(int i) {
            // TODO Auto-generated method stub
            return 2*i;
        }
    
        //打印
        private static void print(ArrayList<Integer> arrayList) {
            // TODO Auto-generated method stub
            for(int i=1;i<arrayList.size();i++){
                System.out.print(arrayList.get(i)+"\t");
            }
            System.out.println();
        }
    }

结果截图  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20210923/de6100d532034e01be7416f34d449d13.png