Java：数组30多行代码实现堆排序

た入场券 2023-02-11 07:22 15阅读 0赞

> 在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：  
> 1、最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点  
> 2、创建最大堆（Build Max Heap）：将堆中的所有数据重新排序  
> 3、堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

动图演示：  
![在这里插入图片描述][20200522115350344.gif_pic_center]  
代码实现：

public class DuiPai { 
        public static int[] sort(int[] arr ){ 
            int len = arr.length;
            //建立大根堆
            for(int i = (int)Math.floor(len / 2);i >= 0 ;i--){ 
                heapify(arr,i,len);
            }
    
            for(int i = len - 1; i > 0;i--){ 
                int temp = arr[i];
                arr[i] = arr[0];
                arr[0] = temp;
                len--;
                heapify(arr,0,len);
            }
            return arr;
        }
        private static void heapify(int[] arr,int i,int len){ 
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = i;
            if(left < len && arr[left] > arr[largest]){ 
                largest = left;
            }
            if(right < len && arr[right] > arr[largest]){ 
                largest = right;
            }
            if(largest != i){ 
                int temp = arr[i];
                arr[i] = arr[largest];
                arr[largest] = temp;
                heapify(arr,largest,len);
            }
        }
    }

测试：![在这里插入图片描述][20200522115615897.png]  
![在这里插入图片描述][20200522115632283.png]  
堆排序使用数组方式实现代码量很少，当然，使用树节点的方式也可以实现，节点中包含一个值三个指向（左右孩子和父节点）。

[20200522115350344.gif_pic_center]: https://img-blog.csdnimg.cn/20200522115350344.gif#pic_center
[20200522115615897.png]: https://img-blog.csdnimg.cn/20200522115615897.png
[20200522115632283.png]: https://img-blog.csdnimg.cn/20200522115632283.png