堆排序（java）

堆排序的基本思想：将一个待排序的序列构成一个大顶堆， 整个序列的最大值就是堆顶的根结点。 将他移走（其实是将其与堆数组的末尾元素交换， 此时末尾元素就是最大值）， 然后将剩余的n-1个序列重新构造成大顶堆，得到n-1个元素中的最大值， 反复执行，得到一个有序序列。

构造大顶堆的方法： 从上往下，从右到左，将每一个非叶子节点当作根结点，将其和其子树调整成大顶堆。

稳定性： 由于记录的比较与交换是跳跃式进行的， 堆排序是一种不稳定的排序方法。

public class Sort {
  public static void heapSort(int[] arr){
    //根据序列构造大顶堆
    int i;
    for(i  =(arr.length - 1) / 2; i >= 0; i--) {
      heapAdjust(arr, i, arr.length);
    }
    //排序：移走大顶堆的根结点（和末尾元素进行交换），对剩余的n-1个元素重新构造大顶堆
    for(i = arr.length - 1; i > 0; i--){
      swap(arr, 0, i);
      heapAdjust(arr, 0, i); //此处的i表示剩余需要构造大顶堆的数组长度
    }
  }
  
  public static void headAdjust(int[] arr, int i, int length){
    int temp, j;
    temp = arr[i]; //temp保存当前需要调整的堆的根结点的值
  
    //找出下标为i的结点应存放的位置
    for(j = 2 * i + 1; j <= length - 1; j = 2 * j + 1){
      if(j < length - 1 && arr[j] < arr[j + 1]){ //条件成立：有右结点，切右结点的值比左结点的值大
        j++;
      }
      if(temp > arr[j]){ //条件成立：arr[i] 是最大值满足大顶堆退出循环
        break; 
      }
      arr[i] = arr[j]; //将下标为i的结点点的值改为子节点中的最大值
      i = j; //因为交换了结点值的位置，可能影响下面子树的大顶堆结构，需要继续构造      
    }
    arr[i] = temp; //
  }

  public static void swap(int[] arr, int index_1, int index_2){
    int temp;
    temp = arr[index_1];
    arr[index_1] = arr[index_2];
    arr[index_2] = temp;    
  }

  //test
  public static void main(String[] args){
    int heapSortArray = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    Sort.heapSort(heapSortArray);
    for(int num : heapSrotArray){
      System.out.print(num + " ");
    }
  }
}

时间复杂度：O(nlogn)
空间复杂度：一个用来暂存arr[i]的单元