堆排序实现+分析

素颜马尾好姑娘i 2024-04-17 14:30 61阅读 0赞

堆排序

> package pratice826;  
> //堆排序-最小顶堆  
> public class Main \{
> 
>     public static void main(String\[\] args) \{  
>         int nums\[\] = \{16,7,3,20,17,8\};  
>         headsort(nums);  
>         for(int i=0;i<nums.length;i++)\{  
>             System.out.print(nums\[i\] + " ");  
>         \}  
>         System.out.println(" ");  
>         for(int num : nums)\{  
>             System.out.print(num + " ");  
>         \}  
>     \}  
>     public static void headsort(int nums\[\])  
>     \{  
>         //构造堆  
>         for(int i = (nums.length)/2-1; i>=0; i--)\{  
>             headAdjust(nums ,nums.length,i);  
>         \}  
>         //swap最大的结点放到堆尾，然后从根结点重新调整  
>         //将最大的结点放在堆尾，然后从根节点重新调整  
>         for(int i = nums.length-1 ; i>=1; i--)\{  
>             int temp = nums\[0\];  
>             nums\[0\] = nums\[i\];  
>             nums\[i\] = temp;  
>             headAdjust(nums, i, 0);  
>         \}  
>     \}  
>     public static void headAdjust(int nums\[\], int len, int i)\{  
>         int k = i, temp = nums\[i\], index = 2\*k + 1;  
>         while(index < len)\{  
>             if(index + 1 < len)\{  
>                 if(nums\[index\] < nums\[index+1\])\{  
>                     index = index + 1;  
>                 \}  
>             \}  
>             if(nums\[index\] > temp)\{  
>                 nums\[k\] = nums\[index\];  
>                 k = index;  
>                 index = 2\*k + 1;  
>             \}else\{  
>                 break;  
>             \}  
>         \}  
>         nums\[k\] = temp;  
>     \}  
> \}

![2019082714132340.png][]

[2019082714132340.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/84677b38726c42a09b9290d9e65653f4.png