[每日一道小算法（七十七）] [排序算法] 堆排序

末蓝、 2023-07-11 06:28 5阅读 0赞

前言：  
今天复习了一下排序算法，堆排序写的不太熟练，所以在这里记录一下，方便以后的学习。

### 题目描述 ###

就是实现堆排序。

### 解题思路 ###

基本思路：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

### 代码样例 ###

package Quicksort;
    
    /** * 堆排序 ： 时间复杂度 最好最坏平均复杂度都为O（nlogn） */
    public class Main { 
        public static void main(String[] args) { 
            Main main = new Main();
            int[] array = { 7,9,4,6,2,3};
            main.HeapSort(array);
            for (int i = 0; i < array.length; i++) { 
                System.out.println(array[i]);
            }
        }
        private void swap(int[] array,int len)
        { 
            int temp = array[0];
            array[0] = array[len-1];
            array[len-1] = temp;
        }
        public void HeapSort(int[] array)
        { 
            for (int i = array.length; i > 0; i--) { 
                Heap(array,i);
                swap(array,i);
            }
        }
        public void Heap(int[] array,int len)
        { 
            int temp;
            int i;
            for (i = len/2-1;i>=0;i--)
            { 
                //先判断左子树
                if((2*i+1)<len && array[i] < array[2*i+1])
                { 
                    temp = array[2*i+1];
                    array[2*i+1] = array[i];
                    array[i] = temp;
                    //左右子树在进行判断
                    if(((2*(2*i+1)+1)<len && array[2*i+1] < array[2*(2*i+1)+1])||((2*(2*i+1)+2)<len && array[2*i+1] < array[2*(2*i+1)+2]))
                    { 
                        Heap(array,len);
                    }
                }
                //先判断右子树
                if((2*i+2)<len && array[i] < array[2*i+2])
                { 
                    temp = array[2*i+2];
                    array[2*i+2] = array[i];
                    array[i] = temp;
                    //左右子树在进行判断
                    if(((2*(2*i+2)+1)<len && array[2*i+2] < array[2*(2*i+2)+1])||((2*(2*i+1)+2)<len && array[2*2+2] < array[2*(2*i+2)+2]))
                    { 
                        Heap(array,len);
                    }
                }
            }
        }
    }