堆排序

Posted by 石玉军 on 2018-07-26

堆排序主要是运用了二叉树的性质来进行的排序。

在进行堆排序之前我们先了解一下二叉树的几个性质:

1.在排序使用二叉树的时候我们要排序的数组的第0个位置其实是不可以用的,这个时候如果我们要排序的数组为[3,1,0,2,8,4,2]时,我们首先要把它变为[0,3,1,0,2,8,4,2],我们把他转换为二叉树的时候是这样的图片

2.观察此二叉树我们可以发现几个公式:

父节点个数:(数组长度-1)/2
父节点索引为1到父节点个数
子节点的索引:左儿子为父节点索引*2,右儿子为左儿子索引+1
3.我们进行堆排序的时候一般先从最后的节点开始,先比较最后的子节点,找出较大的子节点与父节点比较,如果子节点大于父节点则子节点与父节点交换。此流程大概是这样的
图片
明白了上方的概念以后我们可以就可以进行简单的操作了:

由公式所知,我们父节点的索引个数等于父节点个数(等于(数组长度8-1)/2)3个,那么最后一个父节点的索引就是3.
有了父节点索引我们就可以得到他的左孩子和右孩子的索引分别为6和7
我们先假设左孩子是子节点最大的,然后判断一下右孩子是否存在,如果存在再比较左右孩子得出最小的孩子。
比较最小孩子和父节点。如果孩子节点大于父节点则交换。
索引为3的父节点比较完了接着比较索引为2的父节点。。然后是为1的。
现在整个树上最大的元素已经在跟节点了,那么我们就把跟节点与最后一个节点交换一下位置。
再次回到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
public static void sort(int []arr,int length){
if(length==1){
return;
}
for (int i=(length-1)/2;i>=1;i--){
int max=i*2;//先假设最大的子节点为左儿子
if(max+1<length&&arr[max+1]>arr[max]){//如果右儿子不超出数组下标且比左儿子大
max++;//最大的子节点为右儿子
}
if(arr[i]<arr[max]){ //如果子节点大于父节点
swap(arr,i,max);//交换方法
}
}
swap(arr,1,length-1);//将跟节点与数组最后一个节点交换
sort(arr,length-1);//递归调用此方法,不过排序好的就不需要再次比较了,所以忽略它
}


public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String []args){
int []arr = {0,3,1,0,2,8,4,2};
sort(arr,arr.length);
System.out.println(Arrays.toString(arr));
}

堆排序讲完了。在这里温馨提示大家,学习算法时,我们没必要拘泥于代码的实现,那没有意义。我的建议就是深入理解步骤,当你理解步骤以后代码是随你怎么玩都可以的。