手敲一遍数据结构和排序算法 Java

public void bulbSort(int[] arr) {
  // 当前个与后一个相比，所以外循环只需n-1次
  for (int i = 0; i < arr.length-1; i++) {
    // 内循环比较大小，因为当第i次循环完后，最后的i+1个已排完序，下一次可以不用参与
    // 如：3 1 4 2
    // 第i=0次循环完(4-1-0=3次)：1 3 2 4，最后一个排完序，下一次可以不用参与
    // 第i=1次循环完(4-1-1=2次)：1 2 3 4，最后两个排完序，下一次可以不用参与
    for (int j = 0; j < arr.length - i - 1; j++) {
      // 相邻元素两两对比，如果第一个比第二个大，就交换他们两个
      if (arr[j]>arr[j+1]) {
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

public void selectionSort(int[] arr) {
  // 当前个与后一个相比，所以外循环只需n-1次
  for (int i = 0; i < arr.length - 1; i++) {
    // 每次循环，i前面的都是已经排完序了的
    // 初始将当前i位置的数认为是最小的
    int minIndex = i;
    // 从i后面的所有数中，寻找值最小的数
    for (int j = i+1; j < arr.length; j++) {
      // 判断是否比当前已知的最小的数还要小
      if (arr[j]<arr[minIndex]) {
        // 将最小数的索引保存
        minIndex = j;
      }
    }
    // 如果两者不相等，说明存在比它更小的数，需要交换
    if (i!=minIndex){
      // 将i位置的数与最小值的数交换
      int temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}

public void insertSort(int[] arr) {
  // 第i=0个元素默认已经是有序，因此从i=1开始
  // 每个元素都要参与比较，所以arr[n]也要取到
  for (int i = 1; i < arr.length; i++) {
    // 先记录下待插入的元素的值
    int key = arr[i];
    int j;
    // 在已排序中，从后往前扫描
    // 依次对比大小，大于它的往后移动，直至找到正确位置后停止
    // j=i-1：前i-1个元素已经是排完序了的
    for (j = i-1; j>=0 && arr[j]>key; j--) {
      arr[j+1] = arr[j];
    }
    // 将值插入，注意上面的for循环出来前会执行一次j--，所以这里要j+1
    arr[j+1] = key;
  }
}

public void quickSort(int[] arr, int left, int right) {
  // 当left=right时，说明左右指针指向了同一个元素
  // 即当前分组只有一个元素，递归结束
  if (left>=right) {
    return;
  }else {
    int l = left;
    int r = right;
    // 将左边第一个元素作为基准值
    // 记录基准值，此时arr[l]这个位置可以放其他值了
    int pivot = arr[l];
    // 对于当前递归
    // 循环比较，直至左右指针相遇，即l=r
    while (l<r) {
      // 先将右指针向左移动，直到遇到一个比基准值小的元素
      while (l<r && arr[r]>pivot) {
        r --;
      }
      // 如果指向了同一个元素，就不需要交换
      // 否则，就需要交换
      if (l<r) {
        // 将右指针指向的元素值赋给左指针指向的元素值
        // 此时arr[r]又可以存其他新的内容了
        arr[l] = arr[r];
        // 左指针已经填值，因此需要l++
        l ++;
      }

      // 再将左指针向右移动，直到遇到一个比基准值大的元素
      while (l<r && arr[l]<pivot) {
        l ++;
      }
      // 同上，下同
      if (l<r) {
        arr[r] = arr[l];
        r --;
      }
    }
    // 此时l=r，说明左右指向了同一个位置
    // 而这个位置应该放的是基准值，且一趟排序完成
    arr[l] = pivot;
    // 对基准值左边部分再进行递归排序
    quickSort(arr, left, l-1);
    // 对基准值右边部分再进行递归排序
    // 由于此时l=r，所以r+1=l+1没影响
    quickSort(arr, r+1, right);
  }
}

/**
 * 合并排序部分
 * @param arr 原始数组
 * @param tempArr 临时数组
 * @param left 当前分组的左边位置序号
 * @param right 当前分组的右位置边序号
 */
public void merge(int[] arr, int[] tempArr, int left, int right) {
  // 大于1个元素，还可继续划分
  if (left < right) {
    // 中间位置
    int mid = (left+right)/2;
    // 左半部分递归划分
    merge(arr, tempArr, left, mid);
    // 右半部分递归划分
    merge(arr, tempArr, mid+1, right);
    // 到这里，说明已经划分完，开始向上合并
    // 指向左边组序列的第一个
    int l = left;
    // 指向右边组序列的第一个
    int r = mid+1;
    // 临时数组的下标，这里的临时数组是存排序后的元素，排完后再复制到原数组中
    int tempIndex = left;
    // 循环比较，直至左边组或右边组没有剩余元素了才停止
    while (l<=mid && r<=right) {
      // 可以想象最简单的情况，倒数第二层，有两个元素，需要对这两个元素排序
      // 如果左边组的一个元素 < 右边组的一个元素，就将小的那个先放到临时数组中。放完后，下标+1指向下一个元素
      if(arr[l]<arr[r]) {
        tempArr[tempIndex++] = arr[l++];
      }else {
        tempArr[tempIndex++] = arr[r++];
      }
    }
    // 可能左边组还有剩余元素，将剩余元素添加到临时数组最后
    while (l<=mid) {
      tempArr[tempIndex++] = arr[l++];
    }
    // 可能右边组还有剩余元素，将剩余元素添加到临时数组最后。这里与上面左边剩余的情况不会同时成立
    while (r<=right) {
      tempArr[tempIndex++] = arr[r++];
    }
    // 最后将排完顺序的临时数组中的元素复制到原数组中
    while (left<=right) {
      arr[left] = tempArr[left];
      left++;
    }
  }
  // 否则，说明已经划分到最小单元，即一个元素
  else {
    return;
  }
}

public void mergeSort(int[] arr) {
  // 开辟一个临时数组
  int[] tempArr = new int[arr.length];
  // 开始归并排序
  merge(arr, tempArr, 0, arr.length-1);
}

public static void main(String[] args) {
  int[] arr = new int[]{5,9,1,4,54,6,77,54,3,9,5,66,2,6,34};
  new Main().mergeSort(arr);
  System.out.println(Arrays.toString(arr));
}

public void shellSort(int[] arr) {
 // 每次增量除2
 for (int inc = arr.length/2; inc > 0; inc/=2) {
   // 每一趟使用插入排序，从第1组的第2个元素开始，到数组的最后一个元素
   // 这里每趟都是对下一组进行排序，即各组交替执行，而不是一个组排序完后再换下一个组
   for (int i = inc; i < arr.length; i++) {
     // 先拿到当前位置的值key
     int key = arr[i];
     int j;
     // 对当前组的当前位置及前面元素进行插入排序
     // j>=inc：保证j-inc非负
     // key<arr[j-inc]：将目标值与前一个元素的值比较
     // j-=inc：指向当前组的前一个元素
     for (j = i; j>=inc&&key<arr[j-inc]; j-=inc) {
       // 将值后移
       arr[j] = arr[j-inc];
     }
     // 将key插入，注意上面的for循环出来前，会执行一次j-=inc
     arr[j] = key;
     // 或者
     /*
       for (j = i-inc; j>=0 && arr[j]>key; j-=inc) {
         arr[j+inc] = arr[j];
       }
       arr[j+inc] = key;
     */
   }
 }

/**
 * 堆排序
 * @param arr 待排序数组
 * @param n 总节点数
 * @param i 当前节点的下标
 */
void heapify(int[] arr, int n, int i) {
  // 记录最大值的节点的下标
  int largest = i;
  // 第i个节点的左子节点的下标：i*2+1
  int lson = i*2+1;
  // 第i个节点的右子节点的下标：i*2+2
  int rson = i*2+2;
  // 先比较根节点与左子节点的大小
  // 如果左子节点的值更大，就记录左子节点的下标
  if (lson<n && arr[lson]>arr[largest]) {
    largest = lson;
  }
  // 再比较根节点(或左子节点，如果上面的if成立的话)与右子节点的大小
  // 如果右子节点的值更大，就记录右子节点的下标
  if (rson<n && arr[rson]>arr[largest]) {
    largest = rson;
  }
  // 若不相等，则说明largest有变动过，即左或右子节点比根节点大了
  if (largest != i) {
    // 交换两者的值，把更大的值放到根节点上
    int temp = arr[largest];
    arr[largest] = arr[i];
    arr[i] = temp;
    // 递归执行堆维护，因为可能本次调整完后，影响了后面的堆性质，如：
    //      3            4
    //     / \          / \
    //    4   1   =>   3   1
    //   / \          / \
    //  5   2        5   2
    // 3跟4换完后，3跟5也需要换
    heapify(arr, n, largest);
  }
}

/**
 * 大顶堆，堆排序
 * @param arr 待排序的数组
 */
public void heapSort(int[] arr) {
  int n = arr.length;
  // 1.建堆
  // 第i个节点的根节点的下标：(i-1)/2
  // 最后一个节点的根节点的下标：((n-1)-1)/2 = n/2-1
  // 从最后一个根节点到0号根节点依次循环
  for (int i = n/2-1; i >= 0; i--) {
    // 从下往上维护堆，递归次数少，效率高
    heapify(arr, n, i);
  }
  // 2.排序
  // 将最大放到最后
  // 由于大顶堆，所以最大值总是在0号节点上
  // 从最后一个节点到0号节点依次循环
  for (int i = n-1; i > 0; i--) {
    // 交换两者的值，把最大值放到后面的节点上
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    // 交换完成后，对剩余的节点继续执行堆维护
    // i: 由于每次都把最大值往后面放，所以这个i可以限制heapify不会影响到后面已排完序的节点
    // 0: 从上往下维护堆，之前已经建完堆，这次可能只需要微调
    heapify(arr, i, 0);
}

public class Node {
  // 为了方便，变量都使用public，而不用private就不需要编写get、set方法了
  public Node prev;
  public Node next;
  public int val;
  // 无参构造方法
  public Node() {}
  // 构造方法，在构造时就能够给val赋值
  public Node(int val) {
    this.val = val;
  }
}

public class LinkedList {
  // 头结点
  private Node head = new Node();
  private int size = 0;

  /**
   * 打印链表
   */
  public void print() {
    Node temp = head;
    while (temp.next != null) {
      temp = temp.next;
      System.out.print(temp.val+"->");
    }
    System.out.println();
  }

  /**
   * 返回链表大小
   * @return 链表的大小
   */
  public int getSize() {
    return size;
  }

  /**
   * 在链表最后添加节点
   * @param val 待添加的值
   */
  public void add(int val) {
    Node temp = head;
    while (temp.next != null) {
      temp = temp.next;
    }
    temp.next = new Node(val);
    size ++;
  }

  /**
   * 在指定位置的插入节点，旧节点后移
   * @param index 待添加的位置，第一个为0
   * @param val 待添加的值
   */
  public void insert(int index, int val) {
    Node temp = head;
    if (index<=size) {
      // 遍历到待删除节点的前一个节点即可
      for (int i = 0; i < index; i++) {
        temp = temp.next;
      }
      Node node = new Node(val);
      node.next = temp.next;
      temp.next = node;
      size ++;
    }
  }

  /**
   * 删除一个节点
   * @param index 节点所在位置，第一个为0
   */
  public void remove(int index) {
    Node temp = head;
    if (index<=size) {
      // 遍历到待删除节点的前一个节点即可
      for (int i = 0; i < index; i++) {
        temp = temp.next;
      }
      // 重新链接，跳过待删除节点
      temp.next = temp.next.next;
      size --;
    }
  }
}

// 节点类
public class Node {
  public int val;
  public Node left;
  public Node right;
  public Node(int val) {
    this.val = val;
  }
}

public Node create() {
  Node root = new Node(0);
  root.left = new Node(1);
  root.right = new Node(2);
  root.left.left = new Node(3);
  root.left.right = new Node(4);
  root.right.left = new Node(5);
  root.right.left.left = new Node(6);
  return root;
}

/**
 * 先序遍历，先输出根节点，再遍历左子节点，再遍历右子节点
 * @param node
 */
public void preTraversal(Node node) {
  if (node != null) {
    System.out.print(node.val+" ");
    preTraversal(node.left);
    preTraversal(node.right);
  }
}

/**
 * 中序遍历，先遍历左子节点，再输出跟节点，再 遍历右子节点
 * @param node
 */
public void midTraversal(Node node) {
  if (node != null) {
    midTraversal(node.left);
    System.out.print(node.val+" ");
    midTraversal(node.right);
  }
}

/**
 * 后序遍历
 * @param node
 */
public void lastTraversal(Node node) {
  if (node != null) {
    lastTraversal(node.left);
    lastTraversal(node.right);
    System.out.print(node.val+" ");
  }
}

/**
 * 层序遍历
 * 通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。
 * 而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，
 * 出队结点的先后顺序就是层次遍历的最终结果。
 * @param root 根节点
 */
public void levelTraversal(Node root) {
  // 先判断根节点非空
  if (root!=null) {
    // 创建一个队列（先入先出FIFO），用于存放节点
    Queue<Node> queue = new LinkedList<>();
    // 先将根节点放入
    queue.offer(root);
    // 然后取出一个节点
    Node node = queue.poll();
    // 循环取出、判断节点是否非空
    while (node!=null) {
      // 输出
      System.out.print(node.val+" ");
      // 判断左子节点非空，若非空则加入队列
      if (node.left!=null) {
        queue.offer(node.left);
      }
      // 判断右子节点非空，若非空则加入队列
      if (node.right!=null) {
        queue.offer(node.right);
      }
      // 从队列取出一个节点
      node = queue.poll();
    }
  }
}

public static void main(String[] args) {
	Node node = create();
  preTraversal(node);
  System.out.println();
  midTraversal(node);
  System.out.println();
  lastTraversal(node);
  System.out.println();
  levelTraversal(node);
  System.out.println();
}

public void insert(Node root, int value) {
  // 当前节点不为空，则继续往下寻找
  if (root != null) {
    // 若待插入的值比当前节点的值小，则往左放
    if (value < root.val) {
      // 左子节点不为空，则递归插入
      if (root.left != null) {
        insert(root.left, value);
      }
      // 否则说明已到最后，可以插入
      else {
        root.left = new Node(value);
      }
    }
    // 同上
    else if (value > root.val) {
      if (root.right != null) {
        insert(root.right, value);
      }else {
        root.right = new Node(value);
      }
    }
  }
  // 当前节点为空，则直接赋值
  else {
    root = new Node(value);
  }
}

   3
  / \
 9   20
    /  \
   15   7

=> [ [3], [9,20], [15,7] ]

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
}

public List<List<Integer>> levelOrder(TreeNode root) {
  // 用于存最终结果
  List<List<Integer>> ret = new ArrayList<>();
  // 队列，用于存储节点信息
  Queue<TreeNode> queue = new LinkedList<>();
  if (root == null){
    return ret;
  }
  // 先将head节点添加入队列，然后开始while循环。
  queue.offer(root);
  // 辅助作用的节点，用于指向出队的节点信息
  TreeNode node;
  while (!queue.isEmpty()){
    // 临时的列表，存某一层的所有节点。
    ArrayList<Integer> temp = new ArrayList<>();
    // 得到队列的长度，此时队列的长度=这一层的节点数（后面可以发现）
    int len = queue.size();
    // 由于输出结果是二维数组结构，第二维的数组内数量就是该层的全部节点。
    // 所以可以通过for循环填入某一层的所以节点。
    for (int i = 0; i < len; i++) {
      // 先出队第一个节点
      node = queue.poll();
      // 将该节点的值加入
      temp.add(node.val);
      // 如果左边子节点存在，则加入队列
      if (node.left != null){
        queue.offer(node.left);
      }
      // 如果右边子节点存在，则加入队列
      if (node.right != null){
        queue.offer(node.right);
      }
    }
    // for循环完成，表示这一层的节点都已获取到，将此接入到结果列表中
    ret.add(temp);
  }
  // 如果是倒序层次遍历，反转一下即可
  Collections.reverse(ret);
  return ret;
}

   A
  / \
 B   C
/ \  / \
D  E F G

=> A B C D E F G

public void levelOrder(TreeNode root) {
  // 创建一个栈
  Stack<TreeNode> stack = new Stack<>();
  // 临时节点
  TreeNode treeNode;
  // 先将head节点放入栈
  stack.add(root);
  // 循环，直至所有节点都处理完
  while (!stack.isEmpty()){
    // 弹出栈顶节点
    treeNode = stack.pop();
    // 获取节点的值
    System.out.println(treeNode.val);
    // 如果右边有节点，则入栈
    // 注意“先入后出”特性，先入右边，先出左边，所以注意搜索顺序
    if (treeNode.right != null){
      stack.add(treeNode.right);
    }
    // 如果左边有节点，则入栈
    if (treeNode.left != null){
      stack.add(treeNode.left);
    }
  }
}

package com.sxf;
import java.util.Arrays;

public class Main {
  public void bulbSort(int[] arr) {
    // 当前个与后一个相比，所以外循环只需n-1次
    for (int i = 0; i < arr.length-1; i++) {
      // 内循环比较大小，因为当第i次循环完后，最后的i+1个已排完序，下一次可以不用参与
      // 如：3 1 4 2
      // 第i=0次循环完(4-1-0=3次)：1 3 2 4，最后一个排完序，下一次可以不用参与
      // 第i=1次循环完(4-1-1=2次)：1 2 3 4，最后两个排完序，下一次可以不用参与
      for (int j = 0; j < arr.length - i - 1; j++) {
        // 相邻元素两两对比，如果第一个比第二个大，就交换他们两个
        if (arr[j]>arr[j+1]) {
          int temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
        }
      }
    }
  }

  public void selectionSort(int[] arr) {
    // 当前个与后一个相比，所以外循环只需n-1次
    for (int i = 0; i < arr.length - 1; i++) {
      // 每次循环，i前面的都是已经排完序了的
      // 初始将当前i位置的数认为是最小的
      int minIndex = i;
      // 从i后面的所有数中，寻找值最小的数
      for (int j = i+1; j < arr.length; j++) {
        // 判断是否比当前已知的最小的数还要小
        if (arr[j]<arr[minIndex]) {
          // 将最小数的索引保存
          minIndex = j;
        }
      }
      // 如果两者不相等，说明存在比它更小的数，需要交换
      if (i!=minIndex){
        // 将i位置的数与最小值的数交换
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
      }
    }
  }

  public void insertSort(int[] arr) {
    // 第i=0个元素默认已经是有序，因此从i=1开始
    // 每个元素都要参与比较，所以arr[n]也要取到
    for (int i = 1; i < arr.length; i++) {
      // 先记录下待插入的元素的值
      int key = arr[i];
      int j;
      // 在已排序中，从后往前扫描
      // 依次对比大小，大于它的往后移动，直至找到正确位置后停止
      // j=i-1：前i-1个元素已经是排完序了的
      for (j = i-1; j>=0 && arr[j]>key; j--) {
        arr[j+1] = arr[j];
      }
      // 将值插入，注意上面的for循环出来前会执行一次j--，所以这里要j+1
      arr[j+1] = key;
    }
  }

  public void quickSort(int[] arr, int left, int right) {
    // 当left=right时，说明左右指针指向了同一个元素
    // 即当前分组只有一个元素，递归结束
    if (left>=right) {
      return;
    }else {
      int l = left;
      int r = right;
      // 将左边第一个元素作为基准值
      // 记录基准值，此时arr[l]这个位置可以放其他值了
      int pivot = arr[l];
      // 对于当前递归
      // 循环比较，直至左右指针相遇，即l=r
      while (l<r) {
        // 先将右指针向左移动，直到遇到一个比基准值小的元素
        while (l<r && arr[r]>pivot) {
          r --;
        }
        // 如果指向了同一个元素，就不需要交换
        // 否则，就需要交换
        if (l<r) {
          // 将右指针指向的元素值赋给左指针指向的元素值
          // 此时arr[r]又可以存其他新的内容了
          arr[l] = arr[r];
          // 左指针已经填值，因此需要l++
          l ++;
        }

        // 再将左指针向右移动，直到遇到一个比基准值大的元素
        while (l<r && arr[l]<pivot) {
          l ++;
        }
        // 同上，下同
        if (l<r) {
          arr[r] = arr[l];
          r --;
        }
      }
      // 此时l=r，说明左右指向了同一个位置
      // 而这个位置应该放的是基准值，且一趟排序完成
      arr[l] = pivot;
      // 对基准值左边部分再进行递归排序
      quickSort(arr, left, l-1);
      // 对基准值右边部分再进行递归排序
      // 由于此时l=r，所以r+1=l+1没影响
      quickSort(arr, r+1, right);
    }
  }

  /**
     * 合并排序部分
     * @param arr 原始数组
     * @param tempArr 临时数组
     * @param left 当前分组的左边位置序号
     * @param right 当前分组的右位置边序号
     */
  public void merge(int[] arr, int[] tempArr, int left, int right) {
    // 大于1个元素，还可继续划分
    if (left < right) {
      // 中间位置
      int mid = (left+right)/2;
      // 左半部分递归划分
      merge(arr, tempArr, left, mid);
      // 右半部分递归划分
      merge(arr, tempArr, mid+1, right);
      // 到这里，说明已经划分完，开始向上合并
      // 指向左边组序列的第一个
      int l = left;
      // 指向右边组序列的第一个
      int r = mid+1;
      // 临时数组的下标，这里的临时数组是存排序后的元素，排完后再复制到原数组中
      int tempIndex = left;
      // 循环比较，直至左边组或右边组没有剩余元素了才停止
      while (l<=mid && r<=right) {
        // 可以想象最简单的情况，倒数第二层，有两个元素，需要对这两个元素排序
        // 如果左边组的一个元素 < 右边组的一个元素，就将小的那个先放到临时数组中。放完后，下标+1指向下一个元素
        if(arr[l]<arr[r]) {
          tempArr[tempIndex++] = arr[l++];
        }else {
          tempArr[tempIndex++] = arr[r++];
        }
      }
      // 可能左边组还有剩余元素，将剩余元素添加到临时数组最后
      while (l<=mid) {
        tempArr[tempIndex++] = arr[l++];
      }
      // 可能右边组还有剩余元素，将剩余元素添加到临时数组最后。这里与上面左边剩余的情况不会同时成立
      while (r<=right) {
        tempArr[tempIndex++] = arr[r++];
      }
      // 最后将排完顺序的临时数组中的元素复制到原数组中
      while (left<=right) {
        arr[left] = tempArr[left];
        left++;
      }
    }
    // 否则，说明已经划分到最小单元，即一个元素
    else {
      return;
    }
  }
  public void mergeSort(int[] arr) {
    // 开辟一个临时数组
    int[] tempArr = new int[arr.length];
    // 开始归并排序
    merge(arr, tempArr, 0, arr.length-1);
  }

  public void shellSort(int[] arr) {
    for (int inc = arr.length/2; inc > 0; inc/=2) {
      for (int i = inc; i < arr.length; i++) {
        int key = arr[i];
        int j;
        for (j = i; j>=inc&&key<arr[j-inc] ; j-=inc) {
          arr[j]=arr[j-inc];
        }
        arr[j]=key;
      }
    }
  }


  void heapify(int[] arr, int n, int i) {
    // 记录最大值的节点的下标
    int largest = i;
    // 第i个节点的左子节点的下标：i*2+1
    int lson = i*2+1;
    // 第i个节点的右子节点的下标：i*2+2
    int rson = i*2+2;
    // 先比较根节点与左子节点的大小
    // 如果左子节点的值更大，就记录左子节点的下标
    if (lson<n && arr[lson]>arr[largest]) {
      largest = lson;
    }
    // 再比较根节点(或左子节点，如果上面的if成立的话)与右子节点的大小
    // 如果右子节点的值更大，就记录右子节点的下标
    if (rson<n && arr[rson]>arr[largest]) {
      largest = rson;
    }
    // 若不相等，则说明largest有变动过，即左或右子节点比根节点大了
    if (largest != i) {
      // 交换两者的值，把更大的值放到根节点上
      int temp = arr[largest];
      arr[largest] = arr[i];
      arr[i] = temp;
      // 递归执行堆维护，因为可能本次调整完后，影响了后面的堆性质，如：
      //      3            4
      //     / \          / \
      //    4   1   =>   3   1
      //   / \          / \
      //  5   2        5   2
      // 3跟4换完后，3跟5也需要换
      heapify(arr, n, largest);
    }
  }

  /**
     * 大顶堆，堆排序
     * @param arr 待排序的数组
     */
  public void heapSort(int[] arr) {
    int n = arr.length;
    // 1.建堆
    // 第i个节点的根节点的下标：(i-1)/2
    // 最后一个节点的根节点的下标：((n-1)-1)/2 = n/2-1
    // 从最后一个根节点到0号根节点依次循环
    for (int i = n/2-1; i >= 0; i--) {
      // 从下往上维护堆，递归次数少，效率高
      heapify(arr, n, i);
    }
    // 2.排序
    // 将最大放到最后
    // 由于大顶堆，所以最大值总是在0号节点上
    // 从最后一个节点到0号节点依次循环
    for (int i = n-1; i > 0; i--) {
      // 交换两者的值，把最大值放到后面的节点上
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;
      // 交换完成后，对剩余的节点继续执行堆维护
      // i: 由于每次都把最大值往后面放，所以这个i可以限制heapify不会影响到后面已排完序的节点
      // 0: 从上往下维护堆，之前已经建完堆，这次可能只需要微调
      heapify(arr, i, 0);
    }

  }


  public static void main(String[] args) {
    int[] arr = new int[]{5,9,1,4,54,6,77,54,3,9,5,66,2,6,34};//,54,3,9,5,66,2,6,34
    System.out.println(Arrays.toString(arr));
    //        new Main().bulbSort(arr);
    //        new Main().selectionSort(arr);
    //        new Main().insertSort(arr);
    new Main().quickSort(arr, 0, arr.length-1);
    //        new Main().mergeSort(arr);
    //        new Main().shellSort(arr);
    //        new Main().heapSort(arr);
    System.out.println(Arrays.toString(arr));
  }
}