插入排序_ O(n^2)

定义：
从索引1开始，与前面的元素逐个比较，若比前面的元素小，则交换位置。
由于前面的序列是有序的，若当前元素大于前一个元素，那么它就肯定大于前面所有元素，则可以提前终止内循环。
优化：
由于插入排序，每比较一次，若当前元素小于前一个元素就会相互交换位置。非常损耗性能。
可以先将当前元素的值用一个变量记下来，将前面大于此变量值的元素后移一位，直至前面的元素值不大于此变量的值，则终止内循环，将此变量值赋予此时的元素位置。

特点：
1.由于插入排序可以提前终止内循环，当要排序的数组近乎有序时，此时插入排序的时间复杂度可以进化到O(n)级别。
2.插入排序的常系数很小，在数据量n比较小的时候，插入排序比O(nlogn)的算法有优势。

c++代码：

#include <iostream>
using namespace std;

template <typename T>
void insertionSort( T arr[], int n ){
    for(int i=1; i<n; i++){
        T temp = arr[i];
        int j;
        //前面都是排好序的，如果你比上一个大的话，就肯定比前面所有的大，可以直接结束这层for循环。
        for( j=i; j>0 && arr[j-1]>temp; j--){
            arr[j] = arr[j-1];
        }
        arr[j] = temp;
    }
}

Java代码：

public class InsertionSort {
    
    public static void sort( Comparable[] arr ){
        for(int i=1; i<arr.length; i++){
            Comparable temp = arr[i];
            int j;
            for(j=i; j>0 && arr[j-1].compareTo(temp)>0; j--){
                arr[j] = arr[j-1];
            }
            arr[j] = temp;
        }
    }
    
}

插入排序可视化🌰 http://mengmei219.top/Algorithm/insertSort/insertSort.php