堆排序-Java实现

2018-07-22 05:48:19来源：博客园阅读 ()

复习排序算法时，自己写了一个堆排序的Java实现，重点是容易理解。

Talk is cheap，直接上代码；

 1 /**
 2  * Created by hardaway on 2018/7/20.
 3  * 堆排序(heap)
 4  * 本代码用大顶堆实现
 5  * 1.构建大顶堆. 2.取走堆顶元素，更新大顶堆，直到堆空;
 6  * 时间复杂度O(NlgN)，最好，最坏，平均时间复杂度都是O(NlgN)
 7  * 不稳定排序
 8  */
 9 public class HeapSort {
10     public void sort(int[] arr){
11         construct(arr);   //构建大顶堆
12         for(int i = 0; i<arr.length-1; i++){
13             swap(arr, 0, arr.length-1-i);  //取走堆顶元素，即将最大的元素与当前未排序序列中的末尾元素交换位置；
14             restructure(arr,0, arr.length-1-i); //重构大顶堆
15         }
16     }
17     public void construct(int[] arr){  //构建大顶堆，很重要的一点是，arr.length/2-1这个位置的元素是最后一个有子节点的元素；
18         for(int i = arr.length/2-1; i>=0; i--){
19             restructure(arr, i, arr.length);
20         }
21     }
22     public void restructure(int[] arr, int index, int arrLength){
23         if(index>arrLength/2-1)
24             return;
25         int temp = 2*index+1;
26         if(((2*index+2)<arrLength)&&(arr[2*index+1]<arr[2*index+2]))
27             temp = 2*index+2;
28         if(arr[index]<arr[temp])
29             swap(arr, index, temp);
30         else
31             return;
32         restructure(arr, temp, arrLength); //递归构建，保证它的子节点也是大顶堆
33     }
34     public void swap(int[] arr, int i, int j){ //交互位置，没什么好说的
35         int temp = arr[i];
36         arr[i] = arr[j];
37         arr[j] =temp;
38     }
39     public static void main(String[] args) { //测试用例
40         int[] arr = {9,3,1,4,2,7,8,6,5};
41         System.out.println(Arrays.toString(arr));
42         HeapSort m = new HeapSort();
43         m.sort(arr);
44         System.out.println(Arrays.toString(arr));
45     }
46 }