首页 > 编程学习 > 算法6-堆排序算法

算法6-堆排序算法

发布时间:2022/1/17 12:56:51

堆排序算法思想:

假设数组arr中有N个数:
(1)将整个数组大根堆结构,大根堆的heapSize就是整个数组arr的length;
(2)将大根堆结构的头节点的值和最后一个节点的值交换位置,大根堆的size减1,在此时的size约束下,调整头结点位置,将其变成大根堆结构。不断重复步骤(2),直至size变成1,此时size = 1说明,堆中待排序的元素只有一个,自然就不需要再排序了。

堆排序代码:

public class HeapSort {
	public void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		
		// 让整个数组变成大根堆方法一:
		// 下面这个for循环整体复杂度是O(N*log(N))
		for (int i = 0; i < arr.length; i++) { // O(N)
			heapInsert(arr, i);// O(logN)
		}

		// 让整个数组变成大根堆方法二:
		// 下面这个for循环整体复杂度为O(N),但整个算法的时间复杂度仍然是O(N*log(N)),heapify的特性决定了遍历的时候,要倒着遍历,保证之前形成的子树的最大值都在顶部
		// for (int i = arr.length - 1; i >= 0; i--) {// O(N)
		// heapify(arr, i, arr.length);
		// }

		int size = arr.length;
		swap(arr, 0, --size);

		// 这个while循环决定了,这个算法的时间复杂度是O(N*log(N))
		while (size > 1) {// O(N)
			heapify(arr, 0, size);// O(log(N))
			swap(arr, 0, --size);// O(1)
		}
	}

	// 某个数现在处在index位置,往上继续移动
	public void heapInsert(int[] arr, int index) {
		while (arr[index] > arr[(index - 1) / 2]) {//  0 / -1 =0
			swap(arr, index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}

	// heapify 堆化
	// 某个数在index位置,能否往下移动
	// size限制堆的大小
	public void heapify(int[] arr, int index, int size) {
		int left = index * 2 + 1;// 左孩子的下标
		while (left < size) {// 下方还有孩子的时候
			// 两个孩子中,谁的值大,把下标给largest
			int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
			// 父和孩子之间,谁的值大,把下标给largest
			largest = arr[largest] > arr[index] ? largest : index;
			if (largest == index) {
				break;
			}
			swap(arr, largest, index);
			index = largest;
			left = index * 2 + 1;
		}
	}

堆排序的时间复杂度:

O(N*log(N))

堆排序的额外空间复杂度:

O(1)

Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000