package com.xj.www.sort;
/**
 * 插入排序算法
 *
 * @author xiongjing
 *
 */
public class InsertSort {
      /**
       * 插入排序算法具體流程實(shí)現(xiàn)如下： 插入算法通過(guò)比較和插入來(lái)實(shí)現(xiàn)排序。 1.首先對(duì)數(shù)組的前兩個(gè)數(shù)據(jù)進(jìn)行從小到大的排序。
       * 2.接著將第3個(gè)數(shù)據(jù)與排號(hào)需的兩個(gè)數(shù)據(jù)比較，將第3個(gè)數(shù)據(jù)插入合適的位置。 3.然后，將第4個(gè)數(shù)據(jù)插入已排好序的前3個(gè)數(shù)據(jù)中。
       * 4.不斷重復(fù)上述過(guò)程，直到把最后一個(gè)數(shù)據(jù)插入合適的位置。
       */
      final static int SIZE = 10;
      // 插入排序算法實(shí)現(xiàn)，從小到大
      public static void insert(int[] a) {
            int i, j, temp;
            for (i = 1; i < a.length; i++) {
                  temp = a[i];
                  j = i - 1;
                  // 循環(huán)查找合適的位置
                  while (j >= 0 && temp < a[j]) {
                        a[j + 1] = a[j];
                        j--;
                  }
                  a[j + 1] = temp;
            }
      }
      // 插入排序算法實(shí)現(xiàn)，從大到小
      public static void insertSort(int[] a) {
            int i, j, temp;
            for (i = 1; i < a.length; i++) {
                  temp = a[i];
                  j = i - 1;
                  // 循環(huán)查找合適的位置
                  while (j >= 0 && temp > a[j]) {
                        a[j + 1] = a[j];
                        j--;
                  }
                  a[j + 1] = temp;
            }
      }
      // 程序主入口
      public static void main(String[] args) {
            int[] shuzu = new int[SIZE];
            int i;
            for (i = 0; i < SIZE; i++) {
                  shuzu[i] = (int) (100 + Math.random() * (100 + 1));
            }
            System.out.println("排序前的數(shù)組為：");
            for (i = 0; i < SIZE; i++) {
                  System.out.print(shuzu[i] + " ");
            }
            System.out.print("\n");
             insert(shuzu);
//          insertSort(shuzu);
            System.out.println("排序后的數(shù)組為：");
            for (i = 0; i < SIZE; i++) {
                  System.out.print(shuzu[i] + " ");
            }
            System.out.print("\n");
      }
}