public void insertSort(int[] array){
  for(int i=1;i<array.length;i++)//第0位独自作为有序数列，从第1位开始向后遍历
  {
   if(array[i]<array[i-1])//0~i-1位为有序，若第i位小于i-1位，继续寻位并插入，否则认为0~i位也是有序的，忽略此次循环，相当于continue
   {
    int temp=array[i];//保存第i位的值
    int k = i - 1;
    for(int j=k;j>=0 && temp<array[j];j--)//从第i-1位向前遍历并移位，直至找到小于第i位值停止
    {
     array[j+1]=array[j];
     k--;
    }
    array[k+1]=temp;//插入第i位的值
   }
  }
}

public static void main(String [] args)
{
 int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
  System.out.println("排序之前：");
  for(int i=0;i<a.length;i++)
  {
   System.out.print(a[i]+" ");
  }
  //希尔排序
  int d=a.length;
   while(true)
   {
    d=d/2;
    for(int x=0;x<d;x++)
    {
     for(int i=x+d;i<a.length;i=i+d)
     {
      int temp=a[i];
      int j;
      for(j=i-d;j>=0&&a[j]>temp;j=j-d)
      {
       a[j+d]=a[j];
      }
      a[j+d]=temp;
     }
    }
    if(d==1)
    {
     break;
    }
   }
   System.out.println();
   System.out.println("排序之后：");
    for(int i=0;i<a.length;i++)
    {
     System.out.print(a[i]+" ");
    }
  }
}

public class BubbleSort
{
 public void sort(int[] a)
 {
  int temp = 0;
  for (int i = a.length - 1; i > 0; --i)
  {
   for (int j = 0; j < i; ++j)
   {
    if (a[j + 1] < a[j])
    {
     temp = a[j];
     a[j] = a[j + 1];
     a[j + 1] = temp;
    }
   }
  }
 }
}

public class SelectionSort {
 public void selectionSort(int[] list) {
  // 需要遍历获得最小值的次数
  // 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列
  for (int i = 0; i < list.length - 1; i++) {
   int temp = 0;
   int index = i; // 用来保存最小值得索引
   // 寻找第i个小的数值
   for (int j = i + 1; j < list.length; j++) {
    if (list[index] > list[j]) {
     index = j;
    }
   }
   // 将找到的第i个小的数值放在第i个位置上
   temp = list[index];
   list[index] = list[i];
   list[i] = temp;
   System.out.format("第 %d 趟:\t", i + 1);
   printAll(list);
  }
 }
 // 打印完整序列
 public void printAll(int[] list) {
  for (int value : list) {
   System.out.print(value + "\t");
  }
  System.out.println();
 }
 public static void main(String[] args) {
  // 初始化一个随机序列
  final int MAX_SIZE = 10;
  int[] array = new int[MAX_SIZE];
  Random random = new Random();
  for (int i = 0; i < MAX_SIZE; i++) {
   array[i] = random.nextInt(MAX_SIZE);
  }
  // 调用排序方法
  SelectionSort selection = new SelectionSort();
  System.out.print("排序前:\t");
  selection.printAll(array);
  selection.selectionSort(array);
  System.out.print("排序后:\t");
  selection.printAll(array);
 }
}

public class MergeSort {
 
 public static void merge(int[] a, int low, int mid, int high) {
  int[] temp = new int[high - low + 1];
  int i = low;// 左指针
  int j = mid + 1;// 右指针
  int k = 0;
  // 把较小的数先移到新数组中
  while (i <= mid && j <= high) {
   if (a[i] < a[j]) {
    temp[k++] = a[i++];
   } else {
    temp[k++] = a[j++];
   }
  }
  // 把左边剩余的数移入数组
  while (i <= mid) {
   temp[k++] = a[i++];
  }
  // 把右边边剩余的数移入数组
  while (j <= high) {
   temp[k++] = a[j++];
  }
  // 把新数组中的数覆盖nums数组
  for (int k2 = 0; k2 < temp.length; k2++) {
   a[k2 + low] = temp[k2];
  }
 }
 
 public static void mergeSort(int[] a, int low, int high) {
  int mid = (low + high) / 2;
  if (low < high) {
   // 左边
   mergeSort(a, low, mid);
   // 右边
   mergeSort(a, mid + 1, high);
   // 左右归并
   merge(a, low, mid, high);
   System.out.println(Arrays.toString(a));
  }
 
 }
 
 public static void main(String[] args) {
  int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
  mergeSort(a, 0, a.length - 1);
  System.out.println("排序结果：" + Arrays.toString(a));
 }
}