package io.fredia;

/**
 * 堆排序
 * 
 * @author : Fredia
 * @since : 2018年4月23日
 * @version : v1.0.0
 */
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--) {
            // 保存當(dāng)前正在判斷的節(jié)點(diǎn)
            int k = i;
            // 若當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)存在
            while (2 * k + 1 <= lastIndex) {
                // biggerIndex總是記錄較大節(jié)點(diǎn)的值,先賦值為當(dāng)前判斷節(jié)點(diǎn)的左子節(jié)點(diǎn)
                int biggerIndex = 2 * k + 1;
                if (biggerIndex < lastIndex) {
                    // 若右子節(jié)點(diǎn)存在，否則此時(shí)biggerIndex應(yīng)該等于 lastIndex
                    if (data[biggerIndex] < data[biggerIndex + 1]) {
                        // 若右子節(jié)點(diǎn)值比左子節(jié)點(diǎn)值大，則biggerIndex記錄的是右子節(jié)點(diǎn)的值
                        biggerIndex++;
                    }
                }
                if (data[k] < data[biggerIndex]) {
                    // 若當(dāng)前節(jié)點(diǎn)值比子節(jié)點(diǎn)最大值小，則交換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();
    }

}

排序過程，跑出的結(jié)果如下

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