排序算法

import java.util.Scanner;
import java.util.Arrays;
public class MainSort {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
    Solution so = new Solution();
    so.printArr(arr);
    so.heapSort(arr);
    so.printArr(arr);
  }
}

class Solution {

  /***
   *  冒泡排序
   * @param arr
   */
  public void bubbleSort(int[] arr) {
    if(arr==null || arr.length==0) {
      return;
    }
    for(int j=arr.length-1;j>0;j--) {
      for(int i=0;i<j;i++) {
        if(arr[i]>arr[i+1]) {
          int temp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = temp;
        }
      }
    }
  }

  /****
   *  快速排序
   * @param arr
   * @param start
   * @param end
   */
  public void quickSort(int[] arr,int start,int end) {
    int i = start;
    int j = end;
    if(i>=j) {
      return;
    }
    int baseIndex = i;
    while(i<j) {
      while(i<j && arr[j]>=arr[baseIndex]) {
        j--;
      }
      while(i<j && arr[i]<=arr[baseIndex]) {
        i++;
      }
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
    int temp = arr[baseIndex];
    arr[baseIndex] = arr[i];
    arr[i] = temp;
    quickSort(arr,start,i-1);
    quickSort(arr,i+1,end);
  }

  /***
   *  归并排序
   * @param arr
   * @param start
   * @param end
   */
  public void mergeSort(int[] arr, int start, int end) {
    if(start>=end) {
      return;
    }
    int mid = (start+end)/2;
    mergeSort(arr,start,mid);
    mergeSort(arr,mid+1,end);
    merge(arr,start,mid,end);
  }

  private void merge(int[] arr, int start, int mid, int end) {
    int[] temp = new int[end-start+1];
    int i = start;
    int j = mid+1;
    int index = 0;
    while(i<=mid && j<=end) {
      if(arr[i]<=arr[j]) {
        temp[index++] = arr[i++];
      }else {
        temp[index++] = arr[j++];
      }
    }
    while(i<=mid) {
      temp[index++] = arr[i++];
    }
    while(j<=end) {
      temp[index++] = arr[j++];
    }
    for(i=0;i<temp.length;i++) {
      arr[start+i] = temp[i];
    }
  }

  /***
   *  堆排序
   * @param arr
   */
  public void heapSort(int[] arr) {
    for(int i=arr.length-1;i>=0;i--) {
      adjust(arr,i,arr.length);
    }
    for(int i=arr.length-1;i>=0;i--) {
      int temp = arr[i];
      arr[i] = arr[0];
      arr[0] = temp;
      adjust(arr,0,i);
    }
  }

  private void adjust(int[] arr, int root, int len) {
    int left = root*2 + 1;
    int right = root*2 + 2;
    int maxIndex = root;
    if(left<len && arr[left]>arr[maxIndex]) {
      maxIndex = left;
    }
    if(right<len && arr[right]>arr[maxIndex]) {
      maxIndex = right;
    }
    if(maxIndex!=root) {
      int temp = arr[maxIndex];
      arr[maxIndex] = arr[root];
      arr[root] = temp;
      adjust(arr,maxIndex,len);
    }
  }


  public void printArr(int[] arr) {
    if(arr==null || arr.length==0) {
      return;
    }
    for(int i=0;i<arr.length-1;i++) {
      System.out.print(arr[i]+"-->");
    }
    System.out.println(arr[arr.length-1]+System.lineSeparator());
  }
}