将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地

[单选题]

将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在整个排序过程中，元素3的数组下标发生过____次改变。

```
0
```
```
1
```
```
2
```
```
3
```
```
4
```
```
5
```

查看正确选项

Mageric0412

大根堆来排序，则只需要2次移动3的下标，第一次在将3升到堆顶的时候，第二次则是将3与末尾元素交换的时候，

不知道答案的3从何而来。

考虑小根堆来排序，则需要4次：将原数组转化为一个小根堆，进而进行堆排序操作：

1.首先对原排序进行小根堆转换，则由（7,6,3,5,4,1,2）【大根堆】建立小根堆：

（7,6,3,5,4,1,2）->（7,6,1,5,4,3,2）->（7,4,1,5,6,3,2）->（1,4,7,5,6,3,2）->【下沉】（1,4,2,5,6,3,7），可见3的下标移动1次；

2.堆排序开始，先将堆顶元素与末尾调换，去除末尾元素后，对剩下的堆进行调整：

（1,4,2,5,6,3,7）->（7,4,2,5,6,3,1）->【去除末元素，用x占位之前的移除元素，不参与调整】（7,4,2,5,6,3,x）->

【调整开始】（2,4,7,5,6,3,x）->（2,4,3,5,6,7,x）,可见3的下标又移动1次；

3.对堆顶与末尾元素调换，继续采用2的策略进行调整：

（2,4,3,5,6,7,x）->（7,4,3,5,6,2,x）->【去除末元素，用x占位之前的移除元素，不参与调整】（7,4,3,5,6,x,x）->

【调整开始】（3,4,7,5,6,x,x），可见3的下标再次移动1次；

4.如果采用标准的堆排序策略，还需要将3与末尾元素交换，即（3,4,7,5,6,x,x）->（6,4,7,5,3,x,x）->...3的下标再移动一次。

编辑于 2015-08-25 15:30:48 回复(5)

bboyzqh

排序是对一个数组而言，并不需要输出，也就是说，给一个乱序的数组，经过排序后，这个数组是升序的（一个数组就可以实现堆排序），如果要输出的话，直接把这个数组输出来就可以了。

即：如果需要升序排列，则要逐步大顶堆。因为根节点被一个个放在后面去了。降序排列则要建立小顶堆。

public class HeapOperate2 {
	/*
	 * 建立堆时只需要保证根结点小于两个子结点或者大于两个子结点，对两个子结点大小没有要求
	 */

	public static void main(String[] args) {
		int[] a = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };  
		//在堆排序之前，打印初始数组
        print(a);  
        //进行堆排序
        heapSort(a);  
        //进行堆排序之后
        print(a);  
	}
	

	public static void heapSort(int[] a){
		//建立大根堆
        buildMaxHeap(a);  
        for (int i = a.length - 1; i >= 1; i--) {  
            swap(a[0], a[i]);  
            maxHeap(a, i, 0);  
        }  
    }  

    private static void buildMaxHeap(int[] a) {  
        int half = a.length/2;  
        for (int i = half; i >= 0; i--) {  
            maxHeap(a, a.length, i);  
        }  
    }  

    private static void maxHeap(int[] a, int heapSize, int index) {  
    	//找出index位置处左右孩子的位置left和right
        int left = index * 2 + 1;  
        int right = index * 2 + 2;  

        int largest = index;  
        if (left < heapSize && a[left] > a[index]) {  
            largest = left;  
        }  

        if (right < heapSize && a[right] > a[largest]) {  
            largest = right;  
        }  

        if (index != largest){
        	//交换两个数据
            swap(a[index], a[largest]);  
            maxHeap(a, heapSize, largest);  
        }  
}
}

参见： http://blog.csdn.net/zhuqiuhui/article/details/51214052

谢谢大家支持！

编辑于 2016-06-13 16:06:36 回复(0)