Java实现堆排序算法

淡淡的烟草味﹌ 2022-07-21 00:16 171阅读 0赞

### 这里列出自己写的两个堆排序算法，第一个是之前写的，当时不知道堆调整的思想，第二个是优化堆调整后的方法。 ###

#### 这是第一个： ####

之前只知道如何建堆，不知道算法导论上还有如此巧妙的堆调整算法。所以一开始自己写的堆排序算法非常低效，事件复杂度为O(N^2),因为每次排序都是重建堆。但是，自己写的程序还是有自己独特的思想的， 依然要分享出来给大家看看，尤其是确定数组表示的树的首个叶子节点的位置的方法。  
以下为代码：

package test;
    class HeapSort{
        public static void main(String args[]){
            int []a={
       1,5,7,4,58,96,51,5};
            heapSort(a,0);
            for(int i:a){
                System.out.print(i+",");
            }
        }
        public static void heapSort(int[]a,int L){
            if(L<a.length-1){
                /*============================================================= * 首先，把要进行堆调整的片段复制到临时数组temp[]中 */
                int[]temp=new int[a.length-L];
                for(int i=0;i<temp.length;i++){
                    temp[i]=a[L+i];
                }
                //=============================================================
                /* * 这里需要确定堆最下面一行，也就是二叉树最下面一行的最左边的元素的位置 * 假设要做对调整的数组有10个元素，二进制表示10d=1010b,那么在这1010b * 个元素中有111b个元素不是最下面一行，也就是说，最下面一行最左边的元素的 * 标号为[7],10的二进制有4位，最高位为2的3次方，所以111就是2的三次方减1. */
                String binaryLen=Integer.toBinaryString(temp.length);
    
                int start=(int)(Math.pow(2, binaryLen.length()-1)-1);
                int end=temp.length;
    
                while(end>1){
                    for(int i=start;i<end;i=i+2){
                        int root=temp[i/2];
                        int left=temp[i];
    
                        //if left--root--right
                        if(i+1<end){
                            int right=temp[i+1];
    
                            //if left<root<right then root<=right
                            if(left<=right&&root<right){
                                int t=temp[i/2]; 
                                temp[i/2]=temp[i+1];
                                temp[i+1]=t;     
                            }
                            //else if right<root<left then root<=left
                            else if(right<=left&&root<left){
                                int t=temp[i/2];
                                temp[i/2]=temp[i];
                                temp[i]=t;
                            }
                        }
                        //if left--root--NLL
                        else{
                            if(root<left){
                                int t=temp[i/2];
                                temp[i/2]=temp[i];
                                temp[i]=t;                          
                            }
                        }
                    }//for
    
                    end=start;
                    start=start/2;
                }//while
    
                for(int i=0;i<temp.length;i++){
                    a[L+i]=temp[i];
                }           
    
                heapSort(a,++L);
            }
        } 
    }

### 这是第二个： ###

package test;
    public class HeapSort{ 
        public static void main(String args[]){
            int []a={
       5,7,56,4,65,21,85,7,25,4,78};
            heapSort(a);
            for(int i:a){
                System.out.print(i+",");
            }
        }
        private static void heapSort(int[]a){
            //应该top-down to build
            for(int i=a.length/2;i>=0;i--){
                heapify(a,i,a.length);
            }
            for(int heapSize=a.length;heapSize>0;heapSize--){
                int temp=a[0];
                a[0]=a[heapSize-1];
                a[heapSize-1]=temp;
                heapify(a,0,heapSize-1);
            }
        }
        private static void heapify(int []a,int largest,int heapSize){
            int root=largest;
            int left=root*2+1;
            int right=left+1;
            if(left<heapSize && a[root]<a[left]){
                largest=left;
            }
            if(right<heapSize && a[largest]<a[right]){
                largest=right;
            }
            if(largest != root){
                int temp=a[largest];
                a[largest]=a[root];
                a[root]=temp;
                heapify(a,largest,heapSize);
            }
        }
    }