package com.xj.www.sort;
/**
 * 插入排序算法
 *
 * @author xiongjing
 *
 */
public class InsertSort {
      /**
       * 插入排序算法具体流程实现如下： 插入算法通过比较和插入来实现排序。 1.首先对数组的前两个数据进行从小到大的排序。
       * 2.接着将第3个数据与排号需的两个数据比较，将第3个数据插入合适的位置。 3.然后，将第4个数据插入已排好序的前3个数据中。
       * 4.不断重复上述过程，直到把最后一个数据插入合适的位置。
       */
      final static int SIZE = 10;
      // 插入排序算法实现，从小到大
      public static void insert(int[] a) {
            int i, j, temp;
            for (i = 1; i < a.length; i++) {
                  temp = a[i];
                  j = i - 1;
                  // 循环查找合适的位置
                  while (j >= 0 && temp < a[j]) {
                        a[j + 1] = a[j];
                        j--;
                  }
                  a[j + 1] = temp;
            }
      }
      // 插入排序算法实现，从大到小
      public static void insertSort(int[] a) {
            int i, j, temp;
            for (i = 1; i < a.length; i++) {
                  temp = a[i];
                  j = i - 1;
                  // 循环查找合适的位置
                  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("排序前的数组为：");
            for (i = 0; i < SIZE; i++) {
                  System.out.print(shuzu[i] + " ");
            }
            System.out.print("\n");
             insert(shuzu);
//          insertSort(shuzu);
            System.out.println("排序后的数组为：");
            for (i = 0; i < SIZE; i++) {
                  System.out.print(shuzu[i] + " ");
            }
            System.out.print("\n");
      }
}