堆排序

迷南。 2021-10-29 07:20 360阅读 0赞

什么是堆排序，堆排序能解决什么问题？

在排序的过程中，不能把进行排序的过程中，得一些信息保留下来吗？来加快排序的速度吗？答案是可以的。通过利用完全二叉堆的结构来保留信息。

堆的性质：每个节点都大于等于其左右孩子节点的值，称为大顶堆，或者每个节点的值都小于等于其左右孩子节点的值，称为小顶堆。

ki>=k2i ki<=k2i 1<=i<=n/2  
ki>=k2i+1 ki<=k2i+1;  
为什么i<=n/2呢?因为二叉树的一个性质，如果i = 1,则节点i是二叉树的根，无双亲，如果i>1,其双亲节点是i/2;那么对于有n个节点的二叉树而言，它的i值自然就是小于等于n/2.  
如果当前i = 0,开始的，那么它的左孩子节点为i = 2i+1.右孩子节点位置为i = 2i+2.

堆排序过程：  
1.构建堆（你可以构建大根堆或者小根堆）。  
2.每次交换堆顶元素和最后一个元素，再维持从首元素最长度减1的位置的堆。  
注：构建大根堆和构建小根堆一样的，把符号稍微改变就好了。

算法：

//堆排序,1.先构建堆 2.再将堆顶与末尾交换，3.再重新调整堆，时间复杂度不论好坏都为 O(nlogn)
        public static void Heapsort(int[] arr){
    
            //1.构建堆
            for(int i = arr.length/2-1;i>=0;i--)   //i起始从/2-1开始，是有原因的，这个元素位置都有左右子孩子													            存在
            {
                adjustHeap(arr,i,arr.length);     //  调整从 i位置，到length长度的情况
            }
    
            //for 交换堆顶元素，再调整
            for(int j = arr.length-1;j>0;j--)    // j-- 后变相让数组缩小了
            {
                swap(arr,0,j);                      //  交换堆顶和最后一个位置的元素
                adjustHeap(arr,0,j);           //   把堆顶和j之间调整一下
            }
    
            print(arr);
        }
    
        public static void print(int[] s){
            for(int a:s){
                System.out.print(a);
            }
        }
    
    
        /**
         * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
         * @param arr
         * @param i        // 需要调整位置的根节点
         * @param length       // 调整数组的长度
         */
        public static void adjustHeap(int []arr,int i,int length){          //主要是调整堆函数
    
           
            //temp当前传入根节点
            int temp = arr[i];
    
    
            for(int j = i*2+1;j<length;j = j*2+1) {   //  从根节点的左右子节点开始调整
    
                if(j+1<length && arr[j]<arr[j+1])           // 先比较左右子节点大小，因为是大根堆，找到大元素位置
                    j++;
                if(arr[j] > temp) {   //  找到左右子节点较大元素，与根节点交换，并且，根节点的位置改变
                    arr[i] = arr[j];
                    i = j;                  // 去交换位置为根节点，再往下走，找到temp放下的合适位置
                }else{
                    break;
                }
            }
            arr[i] = temp;             // 插入
    
        }
    
        /*
        小顶堆排序尝试
    
         */
        public static void Heapsorts(int[] arr){
    
            //1.构建堆
            for(int i = arr.length/2-1;i>=0;i--)
            {
                adjustHeaps(arr,i,arr.length);
            }
    
            //for 交换堆顶元素，再调整
            for(int j = arr.length-1;j>0;j--)
            {
                swap(arr,0,j);
                adjustHeaps(arr,0,j);
            }
            print(arr);
        }
    
    
        //小顶堆，堆排序
        public static void adjustHeaps(int []arr,int i,int length){
    
            //怎么调整呢?
            //把当前元素存下来
            int temp = arr[i];
    
            //
            for(int j = i*2+1;j<length;j = j*2+1) {
    
                if(j+1<length && arr[j]>arr[j+1])
                    j++;
                if(arr[j] < temp) {
                    arr[i] = arr[j];
                    i = j;
                }else{
                    break;
                }
            }
            arr[i] = temp;
    
        }
    
    
    
    
    
    
         /* 交换元素
         * @param arr
         * @param a
         * @param b
         */
        public static void swap(int []arr,int a ,int b){
            int temp=arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }