插入排序InsertionSort

/**

 *

 * @author Administrator

 * 功能：插入排序法

 */

package com.test1;

import java.util.Calendar;

public class InsertionSort {

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] arr = new int[50000];

        for (int i = 0; i < arr.length; i++) {

            //让程序随机产生一个1 - 10000个数

            //Math.random会产生一个0到1的数

            arr[i] = (int)(Math.random()*50000);

        }

        //int[] arr = { 1, 6, 0, -1, 9, -100, -90 };

        Insert insert = new Insert();

        //在排序前打印系统时间

        //Calendar是单开模式，在系统里面只有一个，且只需要一个实例，不是new 出来的

        //Java共有23中模式

        Calendar cal = Calendar.getInstance();

        System.out.println("排序前："+cal.getTime());

        insert.sort(arr);

        //在排序后打印系统时间

        //因为是单开的，所有首先重新得到实例

        cal = Calendar.getInstance();

        System.out.println("排序后："+cal.getTime());

//        System.out.println("插入排序的结果是：");

//        for (int i = 0; i < arr.length; i++) {

//            System.out.print(arr[i]+" ");

//        }

    }

}

//插入排序

class Insert

{

    //插入排序方法

    public void sort(int[] arr)

    {

        for (int i = 1; i < arr.length; i++) {

            int insertVal = arr[i];

            //insertVal准备和前一个数比较

            int index = i - 1;

            while(index >= 0 && insertVal < arr[index])

            {

                //将arr[index]向后移动一位

                arr[index+1] = arr[index];

                //让index向前移动一位，-1结束while循环继续往下执行

                index--;

            }

            //将insertVal插入到适当位置

            arr[index+1] = insertVal;

        }

    }

}