public void insertSort(int[] array){
  for(int i=1;i<array.length;i++)//第0位獨(dú)自作為有序數(shù)列，從第1位開(kāi)始向后遍歷
  {
   if(array[i]<array[i-1])//0~i-1位為有序，若第i位小于i-1位，繼續(xù)尋位并插入，否則認(rèn)為0~i位也是有序的，忽略此次循環(huán)，相當(dāng)于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) {
  // 需要遍歷獲得最小值的次數(shù)
  // 要注意一點(diǎn)，當(dāng)要排序 N 個(gè)數(shù)，已經(jīng)經(jīng)過(guò) N-1 次遍歷后，已經(jīng)是有序數(shù)列
  for (int i = 0; i < list.length - 1; i++) {
   int temp = 0;
   int index = i; // 用來(lái)保存最小值得索引
   // 尋找第i個(gè)小的數(shù)值
   for (int j = i + 1; j < list.length; j++) {
    if (list[index] > list[j]) {
     index = j;
    }
   }
   // 將找到的第i個(gè)小的數(shù)值放在第i個(gè)位置上
   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) {
  // 初始化一個(gè)隨機(jī)序列
  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);
  }
  // 調(diào)用排序方法
  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;
  // 把較小的數(shù)先移到新數(shù)組中
  while (i <= mid && j <= high) {
   if (a[i] < a[j]) {
    temp[k++] = a[i++];
   } else {
    temp[k++] = a[j++];
   }
  }
  // 把左邊剩余的數(shù)移入數(shù)組
  while (i <= mid) {
   temp[k++] = a[i++];
  }
  // 把右邊邊剩余的數(shù)移入數(shù)組
  while (j <= high) {
   temp[k++] = a[j++];
  }
  // 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
  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("排序結(jié)果：" + Arrays.toString(a));
 }
}