数据结构与算法：十大排序算法之堆排序

ゝ一纸荒年。 2023-10-02 10:55 28阅读 0赞

## 数据结构与算法：十大排序算法之堆排序 ##

堆排序可以说是选择排序的优化

--------------------

package TopTenSortingAlgorithms;
    
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    //堆排序
    public class HeapSort {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int[] nums = new int[6];
            for (int i = 0; i < nums.length; i++) {
        
                nums[i]=scanner.nextInt();
            }
            int[] headsort = headsort(nums);
            System.out.println(Arrays.toString(headsort));
        }
    
    
        public static int[] headsort(int[] nums){
        
            int heapSize=nums.length;//堆的尾部元素
            //原地建堆
            for (int i = (heapSize>>1)-1; i >=0; i--) {
        
                siftDown(i,nums,heapSize);
            }
    
    
    
            while(heapSize>1){
        
                //交换堆顶元素和尾部元素
                int tmp=nums[0];
                nums[0]=nums[heapSize-1];
                nums[heapSize-1]=tmp;
    
                //交换之后
                heapSize--;
    
                //对索引为0的位置 进行shiftDown(恢复堆的性质)
                siftDown(0,nums,heapSize);
    
            }
            return nums;
        }
    
        private static void siftDown(int position, int[] nums, int heapSize) {
        
            int father=position;
            int child=father*2+1;
    
            int temp=nums[position];    //仍然是挖坑
    
            while(child<heapSize)
            {
        
                if(child<heapSize-1 && nums[child]>nums[child+1])    //两个儿子较小的哪一个
                    child=child+1;
    
                if(temp>nums[child])
                {
        
                    nums[father]=nums[child];    //坑往下沉
    
                    father=child;    //更新下标
                    child=2*father+1;
                }
                else
                    break;
            }
    
            nums[father]=temp;    //填坑
        }
    
    
    
    }

注意：如果还有不懂的，[可以看这篇文章的图][Link 1]

[Link 1]: https://www.sogou.com/link?url=hedJjaC291P3yGwc7N55kLSc2ls_Ks2xM5xHlvvn9KSlDvTRlouvpCoMg6W0X3eXreaVHN88tHY.