堆排序及Java实现

逃离我推掉我的手 2021-09-28 13:04 261阅读 0赞

# 一、堆 #

**在学习堆排序之前需要了解什么是堆？**  
堆是一颗完全二叉树，什么是完全二叉树？  
若二叉树的深度为h，除了第h层外，其他各层的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。  
**堆分为两种：** 大根堆和小根堆  
大根堆：在完全二叉树的基础上，根节点是最大的值，每个父节点都比自己的两个子结点大，  
小根堆：和大根堆相反，根节点是最小的值，并且每个子节点都比父节点大

# 二、堆排的思想 #

### 1、思想 ###

根据堆的特点进行编写，先将一组拥有n个元素的数据构建成大根堆或者小根堆（我按照大根堆进行介绍，小根堆是一样的思想），再将根节点上的数和堆最后一位数据进行互换，此时，第n位的数就是整个序列中最大的数。然后再将前n-1为元素进行构建形成大根堆，再将根节点与第n-1位数据进行互换，得到第二大数据，此时倒数两个数据无疑是有序的；然后将前n-2个数据构建成大根堆，依次循环直到剩下一位元素，则说明第一位后面的数字都是有序的，并且比第一位数大，此时排序完成。

### 2、步骤 ###

1.  构建大根堆或小根堆
2.  循环：根节点和末尾节点进行互换，再构成大根堆或小根堆
3.  排序完成

### 3、复杂度、稳定性 ###

*  **时间复杂度**： 最好情况：O(nlog2n)  
    最坏情况：O(nlog2n)
 *  **空间复杂度**：O（1）
 *  **稳定性**：不稳定

### 4、图示 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20190504165957141.png]

构建大根堆的过程：↓↓↓  
![在这里插入图片描述][20190504170019129.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 1]

# 三、代码 #

public static void adjust(int[] array,int start,int end){  //调整堆为大根堆的函数
            int tmp = array[start];  
            for (int i = 2*start+1; i <= end ; i = 2*i+1) { 
     //若进入for循环说明有左孩子
                //判断是否有孩子，如果有，找到左右孩子的最大值。
                if((i < end) && array[i] < array[i+1]) { 
                    i++;
                }//肯定i是最大值的下标
                if(array[i] > tmp) { //如果tmp比左右孩子的最大值小的话，将最大值放入start的位置
                    array[start] = array[i];
                    start = i;//更新start的值，继续下一次遍历
                }else { 
                    break;
                }
            }
            array[start] = tmp;
        }
        public static void heapSort(int[] array) { 
    //依次遍历父节点，进行调整，建立大根堆
            for (int i = (array.length-1-1)/2; i >= 0 ; i--) { 
    // (array.length-1-1)/2是已知最后一个，
                adjust(array,i,array.length-1);
            }//for循环结束表示第一个大根堆已经建立 
    //时间复杂度：O(n*log2n)
    
            int tmp = 0;  //为交换位置所设定的临时变量
            for (int i = 0; i <= array.length-1; i++) {  
    //先交换第一个值和已经有序的数的前一个值，然后调整成为大根堆
                tmp = array[0];
                array[0] = array[array.length-1-i];
                array[array.length-1-i] = tmp;
       adjust(array,0,array.length-1-i-1);//调整已经交换的数的前一个数字
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]: /images/20210923/54c35e8cb3ea4ee3b8dbcdc5077d8b03.png
[20190504165957141.png]: /images/20210923/d0da91f394644ffa840077f4645714b8.png
[20190504170019129.png]: /images/20210923/f0978852a4dd463081c5193b723d0d20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 1]: /images/20210923/e7849a80929d4f22ba1b9ca5d5bac9c3.png