堆排序详细解说

比眉伴天荒 2022-10-28 00:49 165阅读 0赞

## 思路分析 ##

堆排序的过程如下：  
由于利用小堆会占用额外空间，因此先将一个堆按照大堆的方式进行创建，然后取堆顶元素与堆中的最后一个元素进行交换，接着将最后一个元素出堆，将剩余的元素进行向下调整，重新调整成一个大堆，接着再重复以上操作，知道排序完成。

**注意：排升序要建大堆；排降序要建小堆**

## 图解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]

## 代码实现 ##

public static void heapSort(int[] array){
        
            creatHeap(array);
            for (int i = 0; i < array.length-1; i++){
        
                exchange(array,0,array.length - 1 -i);
    
                shiftDown(array, array.length -1 -i, 0);
    
            }
        }
        public static void shiftDown(int[] array, int size, int index){
        
            //向下调整  大堆!!!!!
            int parent = index;
            int child = 2*parent + 1;
            while (child < size){
        
                if (child + 1 < size && array[child+1] > array[child]){
        
                    child = child+1;
                }
                if (array[child] > array[parent]){
        
                    exchange(array,child,parent);
                }else {
        
                    break;
                }
                parent = child;
                child = 2 * parent + 1;
            }
        }
    
        private static void creatHeap(int[] array) {
        
            for (int i = (array.length - 1 - 1)/2; i >= 0; i--){
        
                shiftDown(array,array.length,i);
            }
        }
    
    
        private static void exchange(int[] array, int bound, int cur) {
        
            int tmp = array[bound];
            array[bound] = array[cur];
            array[cur] = tmp;
        }

## 性能分析 ##

**时间复杂度：**  
O(N\*log(N))

**空间复杂度：**  
O(1)

**稳定性：**  
不稳定排序

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]: /images/20221024/0fc07f7db59843908d3839f8e5971130.png