java 堆排序 初始化堆

hjf_java 发布于 2014/04/08 15:47
阅读 969
收藏 0
在初始化堆的时候从最后一个节点开始向上比较节点的大小
int len = arr.length;
while(true){
    for(int i = len; i > 1; i--){
	int val = i/2;
	if(val >= 1){
	    if(arr[i - 1] > arr[val - 1]){
		arr[val - 1] = arr[val - 1] + arr[i - 1];
		arr[i - 1] = arr[val - 1] - arr[i - 1];
		arr[val - 1] = arr[val - 1] - arr[i - 1];
	    }
	}
    }
    arr[0] = arr[0] + arr[len - 1];
    arr[len - 1] = arr[0] - arr[len - 1];
    arr[0] = arr[0] - arr[len - 1];
    len -= 1;
    if(len == 1){
	break;
    }
}

这样写有什么问题吗?我发现网上的堆排序基本上都是通过从上往下初始化的,所以就很纳闷,这样写明明就简单了很多为什么不这样写呢!


加载中
0
公孙二狗
公孙二狗

1. 初始化堆时,可以从最后一个非叶节点开始调整堆。

2. 把堆顶交换到最后一个位置。

3. 然后在自顶向下调整堆。

4. 重复2到4,直到堆中只有一个元素。

公孙二狗
公孙二狗
回复 @hjf_java : 你的做法效率差一些,多做了一些不必要的调整。
h
hjf_java
我的思路是每次从最后一个节点开始调整堆,然后把堆顶交换到最后一个位置,知道堆中只有一个元素。这样写代码明显减少了不少,但是我看到的都是自顶向下调整,这两种写法效率会不一样么
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部