堆排序

概述：根据二叉树，每次将成员最大值放在堆顶，然后与堆底交换，堆底不参与下次筛选，重复以上步骤。直到从小到大。

场景分析：

4，2，5，1，3

4，3，5，1，2

根据二叉树，每次将成员最大值放在堆顶，

↓   

5，3，4，1，2

然后与堆底交换，

↓                    ↓

2，3，4，1，5

堆底不参与下次筛选

重复以上步骤

2，3，4，1

4，3，2，1

1，3，2，4

1，3，2，

3，1，2

2，1，3

1，2

直到从小到大。

1，2，3，4，5

JAVA实现:

package Sorts;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {

            int[] array = {5,4,3,2,1};

            int length = array.length;

            for (int i = 0; i < length - 1; i++) {

            //每次将成员最大值放在堆顶，堆底不参与下次筛选，

            buildMaxHeap(array,length -1 -i);

           //然后与堆底交换，

           swap(array, 0, length-1-i);

        System.out.println(Arrays.toString(array));

}

}

public static void buildMaxHeap(int[] array, int lastIndex) {

   //根据二叉树

   for (int i = (lastIndex - 1) / 2; i >= 0; i--) {

        int k = i;

        int maxIndex = k * 2 + 1;

        while(maxIndex <= lastIndex) {

        if(maxIndex < lastIndex) {

            if(array[maxIndex] < array[maxIndex + 1]) {

                maxIndex++;

            }

        }

        if(array[k] < array[maxIndex]) {

            swap(array, k, maxIndex);

            k = maxIndex;

        }else {

            break;

        }

    }

    }

}

        public static void swap(int[] array, int low, int high) {

                int temp = array[high];

                array[high] = array[low];

                array[low] = temp;

        }

}