插入排序

实现思路：

1.从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果符合条件（比前面的大或者小，自定义），则让他们交换位置。

2.然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，比如有 5个数8，15，20，45, 17,17比45小，需要交换，但是17也比20小，也要交换，当不需要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前面的数据都是有序的。

3.重复步骤二，一直到数据全都排完。
动图演示：

代码实现：

package 排序;

import java.text.SimpleDateFormat;
import java.util.Date;

public class InsertSort {
	//输出排序前后的时间，看看大概需要花多久
    public static void main(String[] args){
        SimpleDateFormat startTime = new SimpleDateFormat("yyyy:MM:dd:HH:mm:ss");
        System.out.println("排序开始时间："+startTime.format(new Date()));

        sort();
        
        SimpleDateFormat endTime = new SimpleDateFormat("yyyy:MM:dd:HH:mm:ss");
        System.out.println("排序结束时间："+endTime.format(new Date()));

    }

    public static void sort(){
        //测试80万个数据的排序
        int[] arr = new int[800000];
        for (int index = 0; index < 800000; index++) {
            arr[index] = (int)(Math.random() * 80000);
        }

        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0){
                if (arr[j] < arr[j-1]){
                    int temp ;
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    //System.out.println(Arrays.toString(arr));
                    j--;
                }else {
                    break;
                }
            }
        }
        //System.out.println(Arrays.toString(arr));
    }
}

测试结果：

80万个数据总共耗时：2分零8秒。结果出乎意料。然而在开始写这个文章之前我已经开始了测试冒泡排序和选择排序，同样也是80万个数据，，，，然鹅，快10分钟了，还没结束。。。。估计是没戏了。

性能分析：

1.属于稳定的排序，适合于数据量小，部分数据有序的情况排序。

2.如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择

最后：

在这个文章快写完的时候，刚刚说的冒泡排序测试结果出来了，给大家看看，结果经供参考，由于测试的方法存在科学性和严谨性，不一定真的代表这个算法的实际性能,有不足或错误之处，欢迎留言指正，谢谢~~~~

花了21分23秒？？？？看来我的冒泡算法有待优化~~~~各位大神如果有比较好的优化方案，欢迎留言指教。谢谢！

下面是我测试冒泡算法的代码：

package 排序;

import java.text.SimpleDateFormat;
import java.util.Date;

public class BubbleSort {
    public static void main(String[] args){
//        int[] arr={1,3,5,8,45,74};
        SimpleDateFormat time = new SimpleDateFormat("yyyy:MM:dd:HH:mm:ss");
        System.out.println(time.format(new Date()));

        int[] arr = new int[800000];
        for (int index = 0; index < 800000; index++) {
            arr[index] = (int)(Math.random() * 80000);
        }
        int temp = 0;
        boolean flag = true;

        for (int i = 0;i < arr.length-1;i++ ){
            for (int j = 0; j < arr.length-1-i ; j++) {
                if (arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                }
            }

            if (flag){
                break;
            }else {
                flag = true;
            }
        }
//        System.out.println(Arrays.toString(arr));
        SimpleDateFormat time2 = new SimpleDateFormat("yyyy:MM:dd:HH:mm:ss");
        System.out.println(time2.format(new Date()));
    }
}

插入排序

实现思路：

动图演示：

代码实现：

测试结果：

性能分析：

最后：