堆排序及java实现

Myth丶恋晨 2023-07-16 13:58 2阅读 0赞

堆排序是一种时间复杂度为O(nlgn)的一种排序算法，该排序算法用到的就是[https://blog.csdn.net/john1337/article/details/104908523][https_blog.csdn.net_john1337_article_details_104908523]所说的大顶堆，大体思路就是将大顶堆的顶跟数组最后一个有效位置交换，然后对新构成的二叉堆进行大顶堆的重构，依次类推，最后数组就是一个从小往大递增的数组。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70][]

（a）

如上图所示的大顶堆，第一步就是把3与16交换位置，这样就会形成下面的数据  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70 1][]

（b）

然后就会将16排除新的大顶堆的构造过程，新的大顶堆（不包括刚排除的16节点）如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70 2][]

（c）

好了，有了上面的基础，接下来看下用java来实现堆排序算法：

/**
     * 堆排序
     * 有效数据从0开始，
     * 所以一个节点i，其对应二叉树左右子节点下标分别为2*i+1以及2*i+2
     */
    public class MaxHeapSort {
    
        @Test
        public void test(){
            int[] array= {2,8,14,4,16,7,1,10,9,3};
            heapSort(array);
            //输出堆排序结果
            for(int i:array){
                println(i);
            }
        }
    
        /**
         * 堆排序
         * @param array
         */
        public void heapSort(int[] array){
            //初始化大顶堆
            buildMaxHeap(array);
            //堆排序
            int heapSize = array.length;
            //最外层是循环次数，循环到最后大顶堆只有一个元素时停止，所以循环次数为array.length-1
            for(int i=0;i<array.length-1;i++){
                //交换a[0]与大顶堆最后一个元素(不包括已排好序的节点)
                swap(array,0,heapSize-1);
                //大顶堆数据减少一个
                heapSize--;
                //我这里array[0]也是有效数据，所以maxHeepify的第二个参数一致是0
                maxHeepify(array,0,heapSize);
            }
        }
    
        /**
         * 初始化大顶堆
         */
        private void buildMaxHeap(int[] array){
            int len = array.length;
            for(int i= (array.length-2)/2;i>=0;i--){
                maxHeepify(array,i,len);
            }
        }
        /**
         *
         * @param arr
         * @param i
         */
        private void maxHeepify(int[] arr,int i,int len){
            //println("i="+i);
            //有效数据下标从0开始
            //左子节点
            int left = 2*i+1;
            //右子节点
            int right = 2*i+2;
            //初始化最大值节点为当前节点
            int largest = i;
            //左节点不超出数组范围且比较大节点值大，则更新较大值下标
            if(left <len && arr[left] > arr[largest]){
                //左节点比该节点大
                largest = left;
            }
            //右节点不超出数组范围且比较大节点值大，则更新较大值下标
            if(right <len && arr[right] > arr[largest]){
                //左节点比该节点大
                largest = right;
            }
            //如果子节点有一个比当前节点大，则进行数据呼唤，同时向下递归
            if(largest != i){
                //交换节点i与较大子节点数据
                swap(arr,i,largest);
                //经过上面的调整后节点i与其两个子节点满足大顶堆条件
                //但是需要判断调整后的节点largest位置以及其子节点是否还满足大顶堆特性
                maxHeepify(arr,largest,len);
            }
        }
    
        private void swap(int[] arr,int i,int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

[https_blog.csdn.net_john1337_article_details_104908523]: https://blog.csdn.net/john1337/article/details/104908523
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70]: /images/20230528/eaea31ec413b441ea4ef588d6bf4b077.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70 1]: /images/20230528/a7db50bf4e9c40849284f6f8fce66d04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70 2]: /images/20230528/4ba78c3a0ee442b4a35da36c315973eb.png