日常算法——插入排序

直接插入排序

基本思想：
在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排 好顺序的，现在要把第 n 个数插到前面的有序数中，使得这 n 个数也是排好顺序的。如此反复循环，直到全部排好顺序。

代码实现

package Suanfa;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 插入排序
 * Created by hushangjie on 2017/11/6.
*/
public class InsertSort {
    public static void sort(int[] arr) {
        int temp = 0;
        for (int i = 1; i < arr.length; i++) {
            temp = arr[i];
            int j = i -1;
            while (j >= 0 && temp < arr[j]) {

                //往后移动
					   arr[j + 1] = arr[j];
                j--;

            }
            arr[j + 1] = temp;

        }
    }

    public static void main(String[] args) {
        int[] arr = {34, 2, 33, 12, 5, 55};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
​

特点

插入排序是稳定的，时间复杂度为 O(n^2),待排序数列越接近有序，则算法效率越高。插入排序一般不会单独使用，因为其效率并不高，但是可以结合其他排序一起使用，比如快速排序，因为快速排序最后的数据往往是有序的，此时可以使用插入排序收尾。