package com.kingdz.algorithm.time201702;import java.util.Arrays;/** * 堆排序 *  * @author kingdz *  */public class Algo20 {	public static void main(String[] args) {		int count = 10;		int[] number = new int[count];		number = Algo13.fillArray(count, false);		System.out.PRintln(Arrays.toString(number));		genHeap(number);		heapSort(number);	}	/**	 * 生成堆	 * 	 * @param copy	 */	private static void genHeap(int[] copy) {		// System.out.println(Arrays.toString(copy));		// print(copy);		for (int i = copy.length - 1; i > 1; i--) {			int isChange = 0;			if (i % 2 != 0) {				isChange = sortThree(copy, i / 2, i - 1, i);			} else {				isChange = sortThree(copy, i / 2, i);			}			if (isChange != 0) {				i = copy.length;			}		}		System.out.println(Arrays.toString(copy));		// print(copy);	}	/**	 * 三個數字排序	 * 	 * @param copy	 * @param a	 * @param b	 * @param c	 * @return	 */	private static int sortThree(int[] copy, int a, int b, int c) {		int j = c;		if (copy[b] < copy[c]) {			j = b;		}		return sortThree(copy, a, j);	}	/**	 * 兩個數字排序	 * 	 * @param copy	 * @param a	 * @param b	 * @return	 */	private static int sortThree(int[] copy, int a, int b) {		if (copy[a] < copy[b]) {			Algo13.swap(copy, a, b);			return 1;		}		return 0;	}	/**	 * 復制數組，也就是將數組后移一位	 * 	 * @param number	 * @return	 */	private static int[] moveArray(int[] number) {		int[] copy = new int[number.length + 1];		for (int i = 1; i < number.length + 1; i++) {			copy[i] = number[i - 1];		}		return copy;	}	/**	 * 實際運行的堆排序	 * 	 * @param number	 */	private static void heapSort(int[] number) {		int[] copy = moveArray(number);		for (int i = 0; i < number.length; i++) {			// 生成堆			genHeap(copy);			// 輸出第一個元素，從0開始計數，第0個位置為0代表沒有元素			System.out.println(copy[1]);			// 將最后一個元素復制到第一個位置			int index = number.length;			while (copy[index] == 0) {				index--;			}			if (index > 1) {				copy[1] = copy[index];				// 將最后一個元素賦值為0				copy[index] = 0;			}		}	}}