排序算法-3-插入排序

一、插入排序基本思想

主要思想（以从小到大排序为例）：
1）给定一个含有n个数的数组，将其看成一个有序列表和一个无序列表，有序列表中1个数，无序列表中n-1个数。
2）遍历无需列表（n-1轮），每一轮从无序列表取一个数就和有序列表中的数比较大小，直到找到合适的位置将其插入有序列表。
3） n-1轮遍历结束后，无序列表中的所有数都插入到了有序列表的合适位置，所有数据排序完毕。

二、代码实现

package sort;

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

/**
 * 插入排序
 *
 * 实现逻辑分析：
 * 1）默认数组的第一个数为有序列表中的数，从第二个数开始所有数都是无序列表中的数。
 * 2）从无序列表中取一个数定义为待插入数值 int insertValue = arr[i];
 * 3）将 insertValue 从有序列表的最后一个元素挨个比较（有序列表中的最后一个数，即开始比较的元素下标是i-1，是insertValue的前一个数，从这个数开始比较，往前找，直到找到可插入的位置），
 * 4）由于是从小到大排序，又是从后往前比较，在找位置的过程中，如果insertValue<arr[i-1],则要继续往前找。将arr[i-1]的值赋值给arr[i],让 i--，继续和前一个数比较。
 * 5）直到跳出循环，说明找到了那个位置，将insertValue的值赋值给 arr[i+1](当发现insertValue的值比下标为i的位置上的数大了，则要把insertValue放到它后面，因此最后insertValue的位置是下标为 i+1 的位置).
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = new int[80000];
        for(int i = 0;i<arr.length;i++){
            int value = (int)(Math.random()*10);
            arr[i] = value;
        }
        SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        System.out.println("排序前："+ format.format(new Date() ));
//        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后："+format.format(new Date() ));

    }

    public static void insertSort(int[] arr){
        int insertValue = 0;
        int compareIndex = 0 ;
        for(int i=1;i<arr.length;i++){
            insertValue = arr[i];
            compareIndex = i-1;
            while(compareIndex>=0 && insertValue < arr[compareIndex]){
                arr[compareIndex+1] = arr[compareIndex];//此处其实并没有交换位置，只是一次赋值
                compareIndex--;
            }
            arr[compareIndex+1]=insertValue;
//            System.out.println("第"+i+"轮遍历后");
//            System.out.println(Arrays.toString(arr));
        }
    }
}

三、时间复杂度分析

插入排序的时间复杂度为O(n^2)：

• 最好情况(刚好是按照预期有序数据进行排序)：
  所以结果就是：n-1
• 最坏情况：
  从无序列表中每取出一个数经过比较后都要插入到最前面，因此数值挪动次数如下：
  插入下标为1的数：需要挪动1次
  插入下标为2的数：需要挪动2次
  …依此类推
  插入下标为n-1的数：需要挪动 n-1次。
  总共挪动次数为：(n-1+1)(n-1)/2=(n^2-n)/2
  【结论】：
  插入排序结果影响时间复杂度最大的因子仍然是n^2，
  所以最终的时间复杂度仍然是:O(n^2)
  我本地以80000个数据多次排序测试，时间大概500ms～600ms左右。
  

四、插入排序的缺点

如果是从小到大排序，当需要插入的数比较小时，后移次数比较多，如果是从大到小排序，当需要插入的数比较大时，后移次数比较多，这些都对效率有影响。