死磕数据结构与算法（排序java）--堆排序。才疏学浅，如有错误，及时指正

死磕数据结构与算法（排序）--堆排序。才疏学浅，如有错误，及时指正

• • 八大排序算法
• 堆排序
• • 1. 概念以及思路
  • 2. 图解过程
  • 3. 示例代码
• 总结

八大排序算法

1. 冒泡排序算法

2. 选择排序算法

3. 插入排序冒泡算法

4. 希尔排序冒泡算法

5. 快速插入冒泡算法

6. 归并排序冒泡算法

7. 基数排序冒泡算法

8. 堆排序算法

堆排序

1. 概念以及思路

1. 什么是堆？

堆通常是一个可以被看做一棵树的数组对象。堆总是满足以下性值：
堆中某个节点的值总是不大于或不小于其父节点的值。
堆总是一棵完全二叉树。
根节点最大的堆叫做大顶堆。根节点最小的堆叫做小顶堆。
大顶堆示意图：

小顶堆示意图：

2. 什么是堆排序？

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它是不稳定排序。

2. 图解过程

基本思想：

1. 将要排序的数组构造成一个大顶堆
2. 将堆顶的元素与末尾元素进行交换，此时末尾元素就是最大值
3. 将剩余n-1个元素重新构成一个，这样得到n个元素的次小值。反复执行1、2操作，直到要执行的元素长度为1.
   详细操作看代码中的注释。

3. 示例代码

package Tree;

import java.util.Arrays;

public class heapSort {
    public static void main(String[] args) {
        int[] arr = {4,8,5,9,13,6,3,1};
        heapSort( arr );
        System.out.println( Arrays.toString(arr));
    }

    /**
     * 堆排序
     * 1. 将要排序的数组构造成一个大顶堆
     * 2. 将堆顶的元素与末尾元素进行交换，此时末尾元素就是最大值
     * 3. 将剩余n-1个元素重新构成一个，这样得到n个元素的次小值。反复执行1、2操作，直到要执行的元素长度为1.
     * @param arr 要进行排序的数组
     */
    public static void heapSort(int[] arr){
        //1. 第一次构建一个大顶堆
        for (int i = arr.length/2-1; i >= 0; i--) {
            //从第一个非叶子节点从下至上，从右到左调整结构
            adjustHeap( arr, i, arr.length );
        }

        for (int j = arr.length - 1; j > 0 ; j--) {
            //将堆顶元素与末尾元素进行交换
            int temp = arr[0];
            arr[0] = arr[j];
            arr[j] = temp;

            //对堆进行调整，此时从堆顶开始做一次调整就可以得到一个大顶堆
            //因为经过第一次调整之后，父节点的子节点都已经比它的子节点要大了。只有交换之后的根节点不满足要求，所以此时只需要i=0做一次调整即可。
            adjustHeap( arr, 0, j );
        }
    }
    /**
     * 该方法用来
     * @param arr 要调整的数组(树)
     * @param i   开始调整的叶子节点的下标
     * @param length  调整的长度
     */
    public static void adjustHeap (int[] arr, int i, int length){
        int temp = arr[i];  //取出当前元素i
        //对节点下面的元素进行遍历
        //从i的左子节点进行循环，也就是i*2+1处开始
        for (int k = i * 2 + 1; k < length; k++) {
            if(k + 1 < length && arr[k] < arr[k + 1]){
                k++;  //对下一个节点做判断
            }
            //如果子节点大于父节点，把子节点的值给父节点
            if(arr[k] > temp){
                arr[i] = arr[k];  //把较大的值，赋值给当前节点
                i = k;  //把i指向k，继续循环比较
            }else {
                break;
            }
        }
        arr[i] = temp;  //temp放入最终的位置
    }
}

总结

本文使用java完成了一个简单的堆排序算法。以及介绍了堆排序的相关概念。

本文地址：https://blog.csdn.net/qq_41497756/article/details/109254375