算法问题:堆排序-n个数里找最大的m个

1.方法

package io.fredia;

/**
 * 堆排序
 */
public class HeapSortTest {

	public static void main(String[] args) {
		HeapSortTest heapSort = new HeapSortTest();
		int[] ran = new int[100];
		int[] out = heapSort.getRandomIndexArray(ran, ran.length, 5);
		print(ran);
		print(out);

	}

	public int[] getRandomIndexArray(int[] random, int mapSize,
			int numberOfIndex) {
		int[] indexes = getInitialArray(numberOfIndex);
		for (int i = 0; i < mapSize; i++) {
			int randomNum = (int) (Math.random() * 1000);
			random[i] = randomNum;
			if (i > numberOfIndex) {
				insertNumIntoHeap(indexes, randomNum);
			} else if (i == numberOfIndex) {
				heapSort(indexes);
			} else {
				indexes[i] = randomNum;
			}

		}

		return indexes;
	}

	public int[] getInitialArray(int numOfIndex) {
		int[] indexes = new int[numOfIndex];
		for (int i = 0; i < numOfIndex; i++) {
			indexes[i] = -1;
		}
		return indexes;
	}

	public int[] insertNumIntoHeap(int[] numbers, int numToInsert) {
		if (numToInsert > numbers[0]) {
			numbers[0] = numToInsert;

			compareAndExchange(numbers, 0);
		}
		return numbers;
	}

	private void compareAndExchange(int[] numbers, int index) {
		int leftChildIndex = (index + 1) * 2 - 1;
		int rightChildIndex = leftChildIndex + 1;
		if (rightChildIndex > numbers.length) {
			return;
		} else if (rightChildIndex == numbers.length) {
			if (numbers[index] > numbers[leftChildIndex]) {
				swap(numbers, index, leftChildIndex);
			}
		} else {
			int changeIndex = index;
			if (numbers[index] > numbers[leftChildIndex]) {
				changeIndex = leftChildIndex;
			}
			if (numbers[rightChildIndex] < numbers[changeIndex]) {
				changeIndex = rightChildIndex;
			}
			if (changeIndex != index) {
				swap(numbers, index, changeIndex);
				compareAndExchange(numbers, changeIndex);
			}

		}

	}

	public static void swap(int[] data, int i, int j) {
		if (i == j) {
			return;
		}
		data[i] = data[i] + data[j];
		data[j] = data[i] - data[j];
		data[i] = data[i] - data[j];
	}

	public static void heapSort(int[] data) {
		for (int i = 0; i < data.length; i++) {
			createMaxdHeap(data, data.length - 1 - i);
			swap(data, 0, data.length - 1 - i);
			print(data);
		}
	}

	public static void createMaxdHeap(int[] data, int lastIndex) {
		for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
			// 保存当前正在判断的节点
			int k = i;
			// 若当前节点的子节点存在
			while (2 * k + 1 <= lastIndex) {
				// biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
				int biggerIndex = 2 * k + 1;
				if (biggerIndex < lastIndex) {
					// 若右子节点存在,否则此时biggerIndex应该等于 lastIndex
					if (data[biggerIndex] < data[biggerIndex + 1]) {
						// 若右子节点值比左子节点值大,则biggerIndex记录的是右子节点的值
						biggerIndex++;
					}
				}
				if (data[k] < data[biggerIndex]) {
					// 若当前节点值比子节点最大值小,则交换2者得值,交换后将biggerIndex值赋值给k
					swap(data, k, biggerIndex);
					k = biggerIndex;
				} else {
					break;
				}
			}
		}
	}

	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}

}

2. 结果

排序过程,跑出的结果如下

20	748	141	645	830	
20	645	141	748	830	
141	20	645	748	830	
20	141	645	748	830	
20	141	645	748	830	
141	20	830	645	748	28	792	388	502	137	285	531	329	210	519	883	111	961	827	512	408	369	14	705	207	934	765	509	108	262	530	257	547	247	887	337	804	263	444	62	824	156	984	939	109	497	689	796	223	528	963	214	797	442	598	447	260	175	748	558	897	681	473	811	272	739	404	440	481	693	434	810	187	187	178	634	893	858	388	344	460	177	398	942	422	82	160	655	296	855	421	499	669	698	113	421	548	839	73	31	
939	942	984	961	963	

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://blog.wyatt.plus/?p=57

Buy me a cup of coffee ☕.