算法初级——堆排序


堆分为大根堆和小根堆,大根堆就是所有的根节点都比他的子节点都要大,小根堆同理。
我们进行堆排序的时候,其实并不是真的要用到二叉树(完全二叉树),而只是借用这个形式来理解排序的过程,可以将一个数组想象成一棵树。例如i节点的父节点就是(i-1)/2,i节点的左子节点就是i*2+1,右子节点就是i*2+2。
heapInsert:将数组的0到1位置的数变成一个大根堆,然后加入2位置的数,整体是一个大根堆,方法就是刚进来的i位置的数与他的父节点比较,如果大于父节点就交换,然后i位置变成了他的父节点的位置,然后再比较i位置与他的父节点大小,,,,如此类推。这样就形成了一整个大根堆。
heapfy:当大根堆的某一个位置 i 的数变小了,就需要对堆的位置进行从新调整,方法就是i位置的数与他的两个子节点中比较大的值交换,然后i也变成他的大的子节点的位置,然后再与子节点比较,如此类推,堆就调整好了。
堆排序
堆排序的步骤就是:将数组调整成为大根堆,这个时候头节点是最大值,将他与最后一个位置的元素交换,利用heapfy重新调整堆,然后heapSize(堆的有效范围0~heapSize)减一,这个时候,最大值就到了数组的最后一个位置,重复上面的操作,第二大的数就到了数组的倒数第二个位置了,,,,,一直到完成排序,也就是heapSize等于0的时候。
时间复杂度O(N*logN),额外空间复杂度O(1)
代码中包含对数器的验证过程

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import java.util.Arrays;
public class 堆排序 {

    public static void heapSort(int arr[]){  
        if(arr==null || arr.length<2){  
            return ;  
        }  
        //将0~i位置变成大根堆  
        for (int i = 0; i < arr.length; i++) {  
            heapInsert(arr,i);  
        }  
        //开始排序
        int heapSize = arr.length;  
        swap(arr, 0, --heapSize);  
        while(heapSize>0){  
            heapfy(arr, 0, heapSize);  
            swap(arr, 0, --heapSize);  
        }  
    }  
 
    //将0~i位置变成大根堆  
    private static void heapInsert(int[] arr, int i) {  
        while(arr[i]>arr[(i-1)/2]){  
            swap(arr,i,(i-1)/2);  
            i = (i-1)/2;  
        }  
    }  
 
    //当堆中一个值(index)变小的时候,对堆进行调整  
    //数组arr,index位置的值变小,size是堆的范围(0~size)  
    private static void heapfy(int[] arr,int index,int heapSize){  
        int left = index*2+1;//index的左孩子  
        while(left<heapSize){//左孩子不越界  
            //右孩子不越界并且左孩子大于右孩子的时候large是left  
            int large = left+1<heapSize && arr[left+1]>arr[left] ? left+1 : left;  
            large = arr[index]<arr[large]?large:index;  
            if(index==large){  
                break;  
            }  
            swap(arr, large, index);  
            index = large;  
            left = index*2+1;  
        }  
    }  
    //交换  
    private static void swap(int[] arr, int i, int j) {  
        int t = arr[i];  
        arr[i] = arr[j];  
        arr[j] = t;  
    }  
     
    ////////////////////////for test//////////////////////////  
    // for test  
    public static void comparator(int[] arr) {  
        Arrays.sort(arr);  
    }  
 
    // for test  
    public static int[] generateRandomArray(int maxSize, int maxValue) {  
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];  
        for (int i = 0; i < arr.length; i++) {  
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());  
        }  
        return arr;  
    }  
 
    // for test  
    public static int[] copyArray(int[] arr) {  
        if (arr == null) {  
            return null;  
        }  
        int[] res = new int[arr.length];  
        for (int i = 0; i < arr.length; i++) {  
            res[i] = arr[i];  
        }  
        return res;  
    }  
 
    // for test  
    public static boolean isEqual(int[] arr1, int[] arr2) {  
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {  
            return false;  
        }  
        if (arr1 == null && arr2 == null) {  
            return true;  
        }  
        if (arr1.length != arr2.length) {  
            return false;  
        }  
        for (int i = 0; i < arr1.length; i++) {  
            if (arr1[i] != arr2[i]) {  
                return false;  
            }  
        }  
        return true;  
    }  
 
    // for test  
    public static void printArray(int[] arr) {  
        if (arr == null) {  
            return;  
        }  
        for (int i = 0; i < arr.length; i++) {  
            System.out.print(arr[i] + " ");  
        }  
        System.out.println();  
    }  
 
    // for test  
    public static void main(String[] args) {  
        int testTime = 1000000;  
        int maxSize = 100;  
        int maxValue = 100;  
        boolean succeed = true;  
        for (int i = 0; i < testTime; i++) {  
            int[] arr1 = generateRandomArray(maxSize, maxValue);  
            int[] arr2 = copyArray(arr1);  
            heapSort(arr1);  
            comparator(arr2);  
            if (!isEqual(arr1, arr2)) {  
                succeed = false;  
                break;  
            }  
        }  
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");  
 
        int[] arr = generateRandomArray(maxSize, maxValue);  
        printArray(arr);  
        heapSort(arr);  
        printArray(arr);  
    }  

}
0 条评论
发表一条评论