• 【179】Java实现堆排序

    堆是一种特殊的完全二叉树。堆分为最大堆和最小堆。最大堆的任意父节点都大于子节点。最小堆的任意父节点都小于子节点。堆可以用数组或列表来表示。数组或列表的第0个元素是堆的根节点，第 i 个元素的左子节点是第 （2i + 1）个元素，第 i 个元素的右子节点是第 （2i + 2）个元素。第 i 个元素的父节点是第 【（i - 1 ) / 2 向下取整】个元素。

    以按照从小到大排序为例子。

    创建最大堆：

    • 第 0 个元素是堆的根节点。把第0个元素视为一个已经建好的堆。

    • 第 1 个元素作为新节点加入堆中，第 1 个元素的父节点是 第 0 个元素。计算方法：(1-1) / 2 = 0 。第1个元素和第 0 个元素比较大小，如果第 1 个元素大于第 0 个元素，两者交换位置；反之不做操作。

    • 第 2 个元素作为新节点加入堆中，第 2 个元素的父节点是 第 0 个元素。计算方法：(2-1) / 2 = 0.5 向下取整为0 。第 2 个元素和第 0 个元素比较大小，如果第 2 个元素大于第 0 个元素，两者交换位置；反之不做操作。

    • 第 3 个元素作为新节点加入堆中，第 3 个元素的父节点是 第 1 个元素。计算方法：(3-1) / 2 = 1 。第3个元素和第 1 个元素比较大小，如果第 3 个元素大于第 1 个元素，两者交换位置；然后因为新节点到了新的 1 号位置，需要跟父节点比较大小，此时的父节点是第 0 个元素，新节点如果大于第 0 个元素，就交换位置。

    • 第 i 个元素作为新节点加入堆中，需要计算父节点的位置。计算方法：(i - 1) / 2 向下取整。新节点和父节点比较大小。因为前面的 (i - 1) 个元素已经组成一个堆了，所以新节点没有必要和兄弟节点做比较。如果新节点小于等于父节点，就不做处理。如果新节点大于父节点，二者交换位置。交换位置后，新节点需要继续计算出父节点的位置，并且和父节点做比较，如果大于父节点就交换位置。被交换到下一级的父节点没必要再和子节点做比较，因为已经是一个堆了，父节点虽然小于新节点，但是肯定大于或等于旧的子节点。

    这里你可能已经看出来了，新节点找父节点比较和交换位置的过程是一个循环。要想终止循环，只需要满足下面任意一个条件即可：

    1. 新节点已经到了第 0 个的位置，已经是根节点了。
    2. 新节点小于等于父节点。

    当数组或列表中所有的元素都加入了堆以后，创建堆的步骤就完成。

    在创建完堆后，第 0 个元素就是堆顶，也就是最大值。因为是从小到大排序，所以需要不断从堆顶找出最大元素放到数组或列表的末尾。具体步骤如下：

    • 把最后一个元素和第 0 个元素交换位置。此时堆的大小就是 n - 1。此时堆顶的新节点可能不是最大值，找出最大的子节点，如果新节点大于等于最大子节点，就不做操作；如果新节点小于最大子节点，就交换位置。交换位置后，新节点继续和子节点做比较，直到新节点大于等于子节点，或者新节点成为叶子节点。显然新节点和子节点比较和交换位置的过程是一个循环。

    • 把第倒数2个元素和第 0 个元素交换位置。堆的大小变成了 n - 2，堆顶新节点的调整方法和上一段相同。

    下面是堆排序的源码，文件名 HeapSort.java

    package zhangchao;
import java.util.Comparator;
import java.util.List;

/**
 * 堆排序
 * @author zhangchao 
 */
public class HeapSort {
    /**
     * 创建堆
     * @param list 要进行排序的列表
     * @param comparator 比较用的函数钩子
     * @param  list中的元素类型
     */
    private static<T> void createHeap(List<T> list, Comparator<T> comparator) {
        int size = list.size();
        // 假设第0个元素已经是堆了，从第1个元素开始加入堆。
        for (int i = 1; i < size; i++) {
            int newIndex = i;
            while (newIndex > 0) {
//              int parentIndex = (newIndex - 1) / 2;
                int parentIndex = (newIndex - 1) >> 1;
                T parent = list.get(parentIndex);
                T newNode = list.get(newIndex);
                if (comparator.compare(newNode, parent) > 0) {
                    list.set(parentIndex, newNode);
                    list.set(newIndex, parent);
                    newIndex = parentIndex;
                } else {
                    // 小于等于父亲节点，没有上升的需要，不需要再查找上级节点了。
                    newIndex = -1;
                }
            }
        }
    }

    /**
     * 排序
     * @param list 要进行排序的列表
     * @param comparator 比较用的函数钩子
     * @param  list中的元素类型
     */
    public static<T> void sort(List<T> list, Comparator<T> comparator) {
        if (null == list || list.size() < 2) {
            return;
        }
        createHeap(list, comparator);

        int size = list.size();
        for (int i = size - 1; i >= 0; i--) {
            // 当前节点和堆顶交换位置。
            T current = list.get(i);
            list.set(i, list.get(0));
            list.set(0, current);

            // 当前节点放到堆顶后，不断和子节点做比较，以便调整当前节点在堆中的位置。
            int currentIndex = 0;
            int heapSize = i;
            boolean whileFlag = true;
            while(whileFlag) {
//              int leftIndex = currentIndex * 2 + 1;
//              int rightIndex = currentIndex * 2 + 2;
                int leftIndex = (currentIndex << 1) + 1;
                int rightIndex = (currentIndex << 1) + 2;
                if (rightIndex < heapSize) {
                    T right = list.get(rightIndex);
                    T left = list.get(leftIndex);
                    // 找出最大子节点
                    int maxIndex = rightIndex;
                    T max = right;
                    if (comparator.compare(left, right) > 0) {
                        maxIndex = leftIndex;
                        max = left;
                    }
                    if (comparator.compare(max, current) > 0) {
                        list.set(maxIndex, current);
                        list.set(currentIndex, max);
                        currentIndex = maxIndex;
                    } else {
                        whileFlag = false;
                    }
                    /*
                    这段代码被注释掉，是因为这种比较方式会比上一种方式多一到两次比较。
                    // 右子节点最大
                    if (comparator.compare(right, left) > 0 && comparator.compare(right, current) > 0) {
                        list.set(rightIndex, current);
                        list.set(currentIndex, right);
                        currentIndex = rightIndex;
                    }
                    // 左子节点最大
                    else if (comparator.compare(left, right) > 0 && comparator.compare(left, current) > 0) {
                        list.set(leftIndex, current);
                        list.set(currentIndex, left);
                        currentIndex = leftIndex;
                    } else {
                        whileFlag = false;
                    }
                     */
                } else if (leftIndex < heapSize) {
                    T left = list.get(leftIndex);
                    if (comparator.compare(left, current) > 0) {
                        list.set(leftIndex, current);
                        list.set(currentIndex, left);
                        currentIndex = leftIndex;
                    } else {
                        whileFlag = false;
                    }
                } else {
                    whileFlag = false;
                }
            }

        } // end for
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117

    为了直观感受堆排序的效率，我还写了冒泡排序来做比较，下面是冒泡排序代码，文件是 BubbleSort.java

    package zhangchao;

import java.util.Comparator;
import java.util.List;

/**
 * 冒泡排序
 * @author zhangchao
 */
public class BubbleSort {

    /**
     * 排序
     * @param list 要进行排序的列表
     * @param comparator 比较用的函数钩子
     * @param  list中的元素类型
     */
    public static<T> void sort(List<T> list, Comparator<T> comparator) {
        int size = list.size();
        for (int i = 1; i < size; i++) {
            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag = true;

            for (int j = 0; j < size - i; j++) {
                T first = list.get(j);
                T second = list.get(j + 1);

                if (comparator.compare(first, second) > 0) {
                    list.set(j, second);
                    list.set(j + 1, first);
                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    下面是测试代码 Main.java

    package zhangchao;

import java.util.*;

/**
 * 测试
 * @author zhangchao
 */
public class Main {

    /**
     * 检查列表是不是从小到大排序的。
     * @param list 要检查的列表
     * @return 如果是从小到大就返回true，其中相邻元素相等不影响返回结果。
     *         只要其中相邻元素是从大到小的，就返回false。
     */
    private static boolean check(List<Integer> list, List<Integer> originList){
        if (null == list || list.isEmpty() || originList == null || originList.isEmpty()) {
            return false;
        }

        Map<Integer, Integer> listMap = new HashMap<>();
        for (Integer item : list) {
            if (listMap.containsKey(item)) {
                int tmp = listMap.get(item);
                tmp++;
                listMap.put(item, tmp);
            } else {
                listMap.put(item, 1);
            }
        }

        Map<Integer, Integer> originMap = new HashMap<>();
        for (Integer item : originList) {
            if (originMap.containsKey(item)) {
                int tmp = originMap.get(item);
                tmp++;
                originMap.put(item, tmp);
            } else {
                originMap.put(item, 1);
            }
        }

        if (listMap.size() != originMap.size()) {
            return false;
        }
        for (Integer key : originMap.keySet()) {
            int originVal = originMap.get(key);
            int listVal = listMap.get(key);
            if (originVal != listVal) {
                return false;
            }
        }

        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) > list.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        List<Integer> originList = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        List<Integer> list3 = new ArrayList<>();
        final int MAX = 70000;
        for (int i = 0; i < MAX; i++) {
            Random r = new Random();
            int num = r.nextInt(MAX * 8);
            originList.add(num);
            list1.add(num);
            list2.add(num);
            list3.add(num);
        }

        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        };
        long t1 = System.currentTimeMillis();
        HeapSort.sort(list1, comparator);
        long t2 = System.currentTimeMillis();
        System.out.println("heap     check="+ check(list1, originList) +" time=" + (t2-t1) );

        t1 = System.currentTimeMillis();
        list2.sort(comparator);
        t2 = System.currentTimeMillis();
        System.out.println("listSort check="+ check(list2, originList) +" time=" + (t2-t1));

        t1 = System.currentTimeMillis();
        BubbleSort.sort(list3, comparator);
        t2 = System.currentTimeMillis();
        System.out.println("bubble   check="+ check(list3, originList) +" time=" + (t2-t1));



//        System.out.println("origin=" + originList);
//        System.out.println("list1 =" + list1);
    }
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106

    输出结果：

    heap     check=true time=59
listSort check=true time=33
bubble   check=true time=22821

    • 1
    • 2
    • 3
  • 相关阅读:
    dll文件反编译源代码 C#反编译 dotpeek反编译dll文件后export
    C语言——联合与枚举
    MySQL——多表查询
    前端下载文件
    我们再来谈一谈HashMap呗（负载因子，遍历角度）
    Win10下安装CARLA
    EasyExcel实现复杂导入 适用于导入1对N类型数据如组合商品,订单和订单明细等等
    常见面试题-MySQL的Explain执行计划
    AI搜索，围攻百度
    ADE Explorer和Assembler的仿真技巧
  • 原文地址：https://blog.csdn.net/zhangchao19890805/article/details/127580913