HeapSort -- 堆排序
博客专区 > gAKey 的博客 > 博客详情
HeapSort -- 堆排序
gAKey 发表于3个月前
HeapSort -- 堆排序
  • 发表于 3个月前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

/*
 * 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征, 使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
 * (1)用大根堆排序的基本思想 ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区 ②
 * 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个 记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],
 * 且满足R[1..n-1].keys≤R[n].key ③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。
 * 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,
 * 由此得到新的无序区R[1..n-2]和有序区R[n-1..n],
 * 且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。 直到无序区只有一个元素为止。
 * (2)大根堆排序算法的基本操作: ① 初始化操作:将R[1..n]构造为初始堆; ②
 * 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换, 然后将新的无序区调整为堆(亦称重建堆)。
 */

public class HeapSort {
	public static void sort(int[] data) {
		MaxHeap h = new MaxHeap();
		h.init(data);
		for (int i = 0; i < data.length; i++)
			h.remove();
		System.arraycopy(h.queue, 1, data, 0, data.length);
	}

	private static class MaxHeap {

		void init(int[] data) {
			this.queue = new int[data.length + 1];
			for (int i = 0; i < data.length; i++) {
				queue[++size] = data[i];
				fixUp(size);
			}
		}

		private int size = 0;

		private int[] queue;

		public int get() {
			return queue[1];

		}

		public void remove() {
			MaxHeap.swap(queue, 1, size--);
			fixDown(1);
		}

		// fixdown
		private void fixDown(int k) {
			int j;
			while ((j = k << 1) <= size) {
				if (j < size && queue[j] < queue[j + 1])
					j++;
				if (queue[k] > queue[j]) // 不用交换

					break;
				MaxHeap.swap(queue, j, k);
				k = j;
			}
		}

		private void fixUp(int k) {
			while (k > 1) {
				int j = k >> 1;
				if (queue[j] > queue[k])
					break;
				MaxHeap.swap(queue, j, k);

				k = j;
			}
		}

		public static void swap(int[] data, int i, int j) {
			int temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
}

 

共有 人打赏支持
粉丝 3
博文 38
码字总数 2477
×
gAKey
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: