美文网首页
堆排序算法(Java实现)

堆排序算法(Java实现)

作者: d3f59bfc7013 | 来源:发表于2018-06-28 16:38 被阅读0次

    原始堆如下

    image

    堆排序算法

    1. 构造初始堆,从最后一个非叶节点开始调整

      1. 选出叶子节点中比自己大的一个交换,如果交换后的叶子节点不满足堆,则继续调整。


        image

        20和16交换后导致16不满足堆的性质,因此需重新调整


        image
    2. 构造好初始堆之后,将堆头元素交换到堆尾,堆尾的元素就已经是有序的了,然后一直重复,直到所有都有序。

      20已经是最大的了,把交换到堆尾


      image

      然后再从根节点3开始调整,然后每次挑出最大的放到堆尾,直至所有元素有序


      image

    Java代码如下:

    /**
     * @author: gethin
     * @create: 2018-05-23 16:21
     * @description: 常用排序算法
     **/
    public class Sort {
        public static void main(String[] args) {
            int[] nums = {16,7,3,20,17,8};
            headSort(nums);
            for (int num : nums) {
                System.out.print(num + " ");
            }
        }
    
        /**
         * 堆排序
         */
        public static void headSort(int[] list) {
            //构造初始堆,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
            for (int i = (list.length) / 2 - 1; i >= 0; i--) {
                headAdjust(list, list.length, i);
            }
            //排序,将最大的节点放在堆尾,然后从根节点重新调整
            for (int i = list.length - 1; i >= 1; i--) {
                int temp = list[0];
                list[0] = list[i];
                list[i] = temp;
                headAdjust(list, i, 0);
            }
        }
        
        private static void headAdjust(int[] list, int len, int i) {
            int k = i, temp = list[i], index = 2 * k + 1;
            while (index < len) {
                if (index + 1 < len) {
                    if (list[index] < list[index + 1]) {
                        index = index + 1;
                    }
                }
                if (list[index] > temp) {
                    list[k] = list[index];
                    k = index;
                    index = 2 * k + 1;
                } else {
                    break;
                }
            }
            list[k] = temp;
        }
    }
    

    堆排序结果图:

    image

    相关文章

      网友评论

          本文标题:堆排序算法(Java实现)

          本文链接:https://www.haomeiwen.com/subject/fdxnyftx.html