堆排序实现

原创
2014/02/26 17:15
阅读数 859

堆排序实现:

我们利用最大堆来实现排序,先了解下什么是最大堆呢,看图就明白了:

最大堆:所有根节点都必须大于其孩子。

  • 那么对于一个普通的数组,我们要怎么让其变成最大堆呢,比如:

先看看怎么对一颗子树进行最大堆化,其实现代码为:

/**
 * 最大堆化数组arr[index]为根的子树
 * @param arr 对应数组
 * @param index 根索引, 0 ~ arr.length-1
 * @param lastIndex 比较操作的最大索引
 */
private static void maxHeapify(int arr[], int index, int lastIndex){
	int leftChildIndex = left(index);
	int rightChildIndex = right(index);
		
	int biggest = index;
	// 若果左边的孩子更大
	if ((leftChildIndex <= lastIndex)
			&& arr[index] < arr[leftChildIndex]){
		biggest = leftChildIndex;
	}
	// 若右边的孩子还更大
	if ((rightChildIndex <= lastIndex)
			&& arr[biggest] < arr[rightChildIndex]){
		biggest = rightChildIndex;
	}
	// 需要进行调整
	if (biggest != index){ 
		int temp = arr[biggest];
		arr[biggest] = arr[index];
		arr[index] = temp;
		// 递归最大堆化子树
		maxHeapify(arr, biggest, lastIndex); 
	}
}
// 获取左孩子索引
private static int left(int index) {
	return 2*index+1;
}
// 获取右孩子索引
private static int right(int index) {
	return 2*index+2;
}

上面是对以index为根的子树进行最大堆化,那么要怎么对整个数组最大堆化呢,请看:

/**
 * 对整个数组进行最大堆化:
 * 可对每个非叶子节点出发进行最大堆化,
 * 	注意叶子节点索引为: [(arr.length)/2,+1, +2...n],我们没必要对它们进行最大堆化
 * 将数组构建为最大堆的线性复杂度为: O(n)
 * @param arr 对应数组
 */
private static void buildMaxHeap(int arr[]){
	for (int i=(arr.length-1)/2; i>=0; i--){ //必须从大到小
		maxHeapify(arr, i, arr.length-1);
	}
}

这样,我们就对这个数组进行最大堆化了。

接下来就是要对这个最大堆进行排序,思路就是,我们每次都让第一个根节点(arr[0])与最后一个节点交换,再做最大堆化,实现:

/**
* 堆排序算法:
* 不停交换a[0]到最后
* @param arr 待排序数组
*/
private static void heapSort(int[] arr) {
	//将数组最大堆化
	buildMaxHeap(arr); 
	for (int i=arr.length-1; i>0; i--){
		arr[0] = arr[0]^arr[i];
		arr[i] = arr[i]^arr[0];
		arr[0] = arr[0]^arr[i];
		//将第一个(根)继续进行最大堆化, 
		//但经过上面的交换操作, 会依次排除排除倒数第i-1元素
		maxHeapify(arr, 0, i-1); 
	}
}
测试用例:
int arr[] = new int[]{4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
heapSort(arr);
堆排序时间复杂度为nlgn.
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
0 评论
10 收藏
0
分享
返回顶部
顶部