堆排序

向上调整(Java) #

/**
 * 向上调整
 * 若当前节点大于父节点 交换节点位置
 *
 * @param arr
 * @param index
 */
private void heapInsert(int[] arr, int index) {
  while (arr[index] > arr[(index - 1) / 2]) {
    swap(arr, index, (index - 1) / 2);
    index = (index - 1) / 2;
  }
}

向下调整(Java) #

 /**
 * 向下调整
 *
 * @param arr
 * @param index
 * @param heapSize
 */
private void heapify(int[] arr, int index, int heapSize) {
  int left = index * 2 + 1;
  while (left < heapSize) {
    int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; // 比较左右孩子的下标，赋值给largest
    largest = arr[largest] > arr[index] ? largest : index;
    if (largest == index)
      break;

    swap(arr, largest, index);
    index = largest;
    left = index * 2 + 1;
  }
}

堆排序(Java) #

 /**
 * 堆排序 时间复杂度O(N)
 *
 * @param arr
 */
public void heapSort(int[] arr) {
  if (arr == null || arr.length < 2)
    return;

  for (int i = arr.length - 1; i >= 0; i--)
    heapify(arr, i, arr.length);

  int heapSize = arr.length;
  swap(arr, 0, --heapSize);
  while (heapSize > 0) {
    heapify(arr, 0, heapSize);
    swap(arr, 0, --heapSize);
  }
}