【Java】堆排序代码实现

￡神魔★判官ぃ 2021-12-20 11:27 266阅读 0赞

堆排序是简单选择排序的改进，我们先来简单介绍一个概念：堆。

堆的定义：n个元素的序列\{k1 , k2 , … , kn\}，当且仅当满足下列关系时，称之为堆。

![20190706155342618.png][]

满足条件1，则称之为小顶堆；满足条件2，则称之为大顶堆。

堆排序要解决两个问题：

（1）将n个元素的序列按关键字建成堆；

（2）输出堆顶元素后，堆的调整。

堆排序代码实现如下：

import java.util.Arrays;
    
    public class HeapSortTest {
        public static void main(String[] args){
            HeapSortTest heap = new HeapSortTest();
            int[] arr = {5,2,7,3,9,10,8,6,1,4};
            heap.heapSort(arr,arr.length);
            System.out.println(Arrays.toString(arr));
        }
    
        //将一个整型数组中的元素调整成大根堆
        private void headAdjust(int[] arr,int s,int m){
            //在arr[s..m]所构成的一个元素序列中，除了第一个元素之外，其余元素均满足堆的定义
            //调整元素arr[s]的位置，使arr[s..m]成为一个大根堆
    
            //保存元素arr[s]，为其找到适当位置后再插入
            int temp = arr[s];
            //沿值较大的孩子结点向下筛选
            for (int j = 2*s+1; j <= m; j=j*2+1) {
                //比较两个孩子结点的值，j是值较大的元素的下标
                //j<m保证了j+1不会超出数组界限
                if(j<m && arr[j]<arr[j+1]){
                    ++j;
                }
                if(temp >= arr[j]){
                    //若待插入元素的值不小于其两个孩子结点的值，则本次筛选结束
                    break;
                }
                arr[s]=arr[j];
                //使用s记录待插入元素的位置（下标）
                s=j;
            }
            //将备份元素插入由s所指出的插入位置
            arr[s]=temp;
        }
        //假设从小到大排序
        public void heapSort(int[] arr,int n){
            int temp;
            //将arr[0..n-1]调整为大根堆
            for (int i = n/2-1; i >= 0; --i) {
                headAdjust(arr,i,n-1);
            }
            for (int i = n-1; i > 0 ; --i) {
                //堆顶元素arr[0]与序列的最后元素arr[i]交换----交换三部曲
                temp=arr[0];
                arr[0]=arr[i];
                arr[i]=temp;
                //待排元素个数减1，将arr[0..i-1]重新调整为大根堆
                headAdjust(arr,0,i-1);
            }
        }
    
    }

时空复杂度与稳定性：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70][]

[20190706155342618.png]: /images/20211220/2d563344cec94e27b680c0924a72907f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]: /images/20211220/b3ee70f5c4634e289f90518522aac64d.png