java实现堆排序链表法和数组法

数组法（需要详解请留言）：

package heap;
import java.util.*;
public class heap {
    public void heap_sort(int arr[]){
        heap s=new heap();
        int n=arr.length;
        for(int i=(n-2)/2;i>-1;i--){//不得不说这个根节点位置为（n-2）/2真的太妙了
            s.heap_sift(arr,i,n-1);
        }
        for(int k=n-1;k>-1;k--){
            int jk=arr[k];
            arr[k]=arr[0];
            arr[0]=jk;
            s.heap_sift(arr,0,k-1);
        }
        for(int j=0;j<n;j++){
            System.out.print(arr[j]+" ");
        }
    }
    public void heap_sift(int arr[],int root,int end){
        int ans=root;
        int lift=2*ans+1;//很奇怪的点明明根据性质左孩子为2*i结果却变成了2*i+1.。。原来是起点为0导致的
        int tmp=arr[ans];
        while(lift<=end){
            if(lift+1<=end&&arr[lift+1]>arr[lift]){
                lift=lift+1;
            }
            if(arr[lift]>tmp){
                arr[ans]=arr[lift];
                ans=lift;
                lift=ans*2+1;
            }
            else {
                arr[ans]=tmp;
                break;
            }

        }
        if(lift>end){
            arr[ans]=tmp;
        }
    }
    public static void main(String []args){
        heap s=new heap();
        Scanner sc=new Scanner(System.in);
        System.out.print("请输入要排序的个数：");
        int num=sc.nextInt();
        int arr[]=new int[num];
        System.out.print("请输入各个数字：");
        for(int i=0;i<num;i++){
            arr[i]=sc.nextInt();
        }
        s.heap_sort(arr);

    }
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
 

链表法：

未完待续。。。

  

 

  
1
 

文章来源: blog.csdn.net，作者：肥学，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jiahuiandxuehui/article/details/116065638