java 数据结构之堆排序（HeapSort）详解及实例

java;">public class HeapSort {  public static void main(String[] args) {    int[] arr = {3, 2, 1, 0, -1, -2, -3};    System.out.println("Before heap:");    printArray(arr);    heapSort(arr);    System.out.println("After heap sort:");    printArray(arr);  }  public static void heapSort(int[] arr) {    if (arr == null || arr.length <= 1) {      return;    }    buildMaxHeap(arr); //构建最大堆    for (int i = arr.length - 1; i >= 1; i--) {      exchangeElements(arr, 0, i); //交换堆顶和第0位置元素      maxHeap(arr, i, 0); //因为交换元素后，有可能违反堆的性质，所以沉降元素    }  }  private static void buildMaxHeap(int[] arr) { //构建最大堆    if (arr == null || arr.length <= 1) {      return;    }    int half = arr.length / 2;    for (int i = half; i >= 0; i--) {      maxHeap(arr, arr.length, i);    }  }  private static void maxHeap(int[] arr, int heapSize, int index) {    int left = index * 2 + 1; //左子树上的元素    int right = index * 2 + 2; //右子树上的元素    int largest = index; //初始化最大元素    if (left < heapSize && arr[left] > arr[index]) {      largest = left;    }    if (right < heapSize && arr[right] > arr[largest]) {      largest = right;    }    if (index != largest) { //判断根元素是否为最大元素      exchangeElements(arr, index, largest);      maxHeap(arr, heapSize, largest);    }  }  public static void printArray(int[] arr) { //打印数组    System.out.print("{");    for (int i = 0; i < arr.length; i++) {      System.out.print(arr[i]);      if (i < arr.length - 1) {        System.out.print(", ");      }    }    System.out.println("}");  }  public static void exchangeElements(int[] arr, int index1, int index2) { //交换元素    int temp = arr[index1];    arr[index1] = arr[index2];    arr[index2] = temp;  }}