已知数据序列为（12,5，9,20,6，31,24），对该数据序列进行排序，写出插入排序、冒泡排序、快速排序、简单选择排序、堆排序以及二路归并排序每趟的结果。

/**
 *作者：魏宝航
 *2080年14月45日,上午8:41
 */
package 八大排序;
import java.util.Arrays;
import java.util.Scanner;
public class 八大排序 {
  public static void main(String[] args) {
    int[] a=new int[] {12,5,9,20,6,31,24};
    System.out.println("冒泡排序:");
    bubbleSort(new int[] {12,5,9,20,6,31,24});
    System.out.println("选择排序:");
    chooseSort(new int[] {12,5,9,20,6,31,24});
    System.out.println("插入排序:");
    insertSrot(new int[] {12,5,9,20,6,31,24});
    System.out.println("希尔排序:");
    hillSort(new int[] {12,5,9,20,6,31,24});
    System.out.println("基数排序:");
    baseSort(new int[] {12,5,9,20,6,31,24});
    System.out.println("归并排序:");
    mergeSort(a, 0, a.length-1, new int[7]);
    System.out.println("快速排序:");
    quickSort(new int[] {12,5,9,20,6,31,24});
    System.out.println("堆排序:");
    heapSort(new int[] {12,5,9,20,6,31,24});    
  }
  //冒泡排序
  public static void bubbleSort(int [] a) {
    int i,j;
    for(i=0;i<a.length-1;i++) {
      for(j=0;j<a.length-i-1;j++)
        if(a[j]>a[j+1]) {
          int temp=a[j];
          a[j]=a[j+1];
          a[j+1]=temp;
        }
      System.out.println(Arrays.toString(a));
    }
  }
  //选择排序
  public static void chooseSort(int [] a) {
    int i,j;
    for(i=0;i<a.length;i++) {
      int min=a[i];
      int minindex=i;
      for(j=i+1;j<a.length;j++)
        if(a[j]<min) {
          min=a[j];
          minindex=j;
        }
      a[minindex]=a[i];
      a[i]=min;
      System.out.println(Arrays.toString(a));
    }
  }
  //插入排序
  public static void insertSrot(int [] a) {
    int i,j;
    for(i=1;i<a.length;i++) {
      j=i;
      int temp=a[j];
      if(a[j]<a[j-1]) {
        while(j-1>=0&&temp<a[j-1]) {
          a[j]=a[j-1];
          j--;
        }
        a[j]=temp;
      }
      System.out.println(Arrays.toString(a));
    }
  }
  //希尔排序
  public static void hillSort(int [] a) {
    int i,j;
    for(int gap=a.length/2;gap>0;gap/=2) {
      for(i=gap;i<a.length;i++) {
        j=i;
        int temp=a[j];
        if(a[j]<a[j-gap]) {
          while(j-gap>=0&&temp<a[j-gap]) {
            a[j]=a[j-gap];
            j-=gap;
          }
          a[j]=temp;
        }
      }
      System.out.println(Arrays.toString(a));
    }
  }
  //基数排序
  public static void baseSort(int [] a) {
    int i,j,k,n;
    int max=a[0];
    for(i=1;i<a.length;i++)
      if(a[i]>max)
        max=a[i];
    int maxlength=(max+"").length();
    int [][] bucket=new int [10][a.length];
    int [] bucketcount=new int [10];
    for(k=0,n=1;k<maxlength;k++,n*=10) {
      for(i=0;i<a.length;i++) {
        int dight=a[i]/n%10;
        bucket[dight][bucketcount[dight]]=a[i];
        bucketcount[dight]++;
      }
      int index=0;
      for(i=0;i<10;i++) {
        if(bucketcount[i]!=0) {
          for(j=0;j<bucketcount[i];j++) {
            a[index]=bucket[i][j];
            index++;
          }
        }
        bucketcount[i]=0;
      }
      System.out.println(Arrays.toString(a));
    }
  }
  //归并排序
  public static void merge(int [] a,int left,int mid,int right,int [] temp) {
    int i=left;
    int j=mid+1;
    int t=0;
    while(i<=mid&&j<=right) {
      if(a[i]<a[j]) {
        temp[t]=a[i];
        t++;
        i++;
      }
      else {
        temp[t]=a[j];
        t++;
        j++;
      }
    }
    while(i<=mid) {
      temp[t]=a[i];
      t++;
      i++;
    }
    while(j<=right) {
      temp[t]=a[j];
      t++;
      j++;
    }
    int templeft=left;
    t=0;
    while(templeft<=right) {
      a[templeft]=temp[t];
      templeft++;
      t++;
    }
  }
  public static void mergeSort(int [] a,int left,int right,int [] temp) {
    if(left<right) {
      int mid=(left+right)/2;
      mergeSort(a,left,mid,temp);
      mergeSort(a,mid+1,right,temp);
      merge(a,left,mid,right,temp);
      System.out.println(Arrays.toString(a));
    }
  }
  //快速排序
  public static void quickSort(int [] a) {
    if(a==null||a.length<=1)
      return;
    quickSort(a,0,a.length-1);
  }
  public static void quickSort(int [] a,int left,int right) {
    if(left>=right)
      return;
    int pivotindex=left+(int)(Math.random()*(right-left+1));
    swap(a,pivotindex,right);
    int i=left;
    int j=right-1;
    while(i<=j) {
      if(a[i]<=a[right])
        i++;
      else {
        swap(a,i,j);
        j--;
      }
    }
    swap(a,i,right);
    System.out.println(Arrays.toString(a));
    quickSort(a,left,i-1);
    quickSort(a,i+1,right);
  }
  public static void swap(int [] a,int x,int y) {
    int temp=a[x];
    a[x]=a[y];
    a[y]=temp;
  }
  //堆排序
  public static void heapSort(int[] a) {
    for(int i=a.length/2-1;i>=0;i--) {
      adjustHeap(a,i,a.length);
    }
    int temp;
    for(int j=a.length-1;j>0;j--) {
      temp=a[j];
      a[j]=a[0];
      a[0]=temp;
      adjustHeap(a,0,j);
      System.out.println(Arrays.toString(a));
    }
  }
  public static void adjustHeap(int[] a,int i,int length) {
    int temp=a[i];
    for(int k=i*2+1;k<length;k=k*2+1) {
      if(k+1<length&&a[k]<a[k+1]) {
        k++;
      }
      if(a[k]>temp) {
        a[i]=a[k];
        i=k;
        a[i]=temp;
      }else {
        break;
      }
    }
  }
}