Heap sort

Heap sort

• Heaps are divided into big top heaps and small top heaps, where the value of the parent node is greater than the value of the child node (and vice versa). The big top heap is in ascending order and the small top heap is in descending order.

• Heap sort is to build a top heap, swap the top element with the last one, and then run to the end of the heap, and then clean up the heap for the next swap, until there is one more element left in the heap

• Stable sort, space complexity is O(1), time complexity is O(nlogn) (like quicksort, merge sort time complexity is Nlogn, how to choose?)

  • Quicksort is nlogn, but worst case n^2, and merge sort and heapsort are both stable nlogn

  

• Code implementation

  import java.util.Arrays;
  
  / * * *@Description: heap sort *@Author: LinZeLiang
   * @Date: the 2020-10-08 * /
  public class HeapSort {
  
      public static void main(String[] args) {
          int[] a = {9.8.7.5.6.4.3.2.1.0};
  
          heapSort(a);
  
          System.out.println(Arrays.toString(a));
      }
  
      /** * heap sort **@paramA Array to be sorted */
      private static void heapSort(int[] a) {
          // Get the array length
          int length = a.length;
          // Create a big top heap and complete the heap
          for (int i = (length - 2) / 2; i >= 0; i--) {
              downAdjust(a, i, length);
          }
          // Heap sort
          for (int i = length - 1; i >= 1; i--) {
              // Swap, place the larger number at the end
              int temp = a[i];
              a[i]  = a[0];
              a[0] = temp;
  
              downAdjust(a, 0, i); }}/** * Sink adjustment **@paramA Array to be sorted *@paramParent Parent node *@paramLength Range of array length */
      private static void downAdjust(int[] a, int parent, int length) {
          int temp = a[parent];
          // Get the left child index
          int child = parent * 2 + 1;
          // When the child index is within the array length (i.e. the child exists)
          while (child < length) {
              // If the right child is older than the left child, point to the right child
              if (child + 1 < length && a[child] < a[child + 1]) {
                  child++;
              }
              // If the parent node is less than or equal to the child node, then the sink ends
              if (temp >= a[child]) {
                  break;
              }
              // Assign one way, move the child up one bit
              a[parent] = a[child];
              // The parent index points to the node where the child is moved up, and the child index is updated
              parent = child;
              child = parent * 2 + 1; } a[parent] = temp; }}Copy the code