十大排序算法——插入排序

Java实现代码：

public class Insert {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 5, 8, 9, 0, 4, 5, 1, 6, 8, 7};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
    private static void sort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            for (int j = i ; j >0 ; j--) {
                if (array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j-1] = temp;
                }
            }
        }
    }
}

C实现代码：

//从小到大排n个个数
void Insert() { 
        //循环从第二个数组元素开始，因为arr[0]作为最初已排序部分 
        for(int i=1;i<n;i++){ 
        //temp标记为未排序第一个元素 
                int temp=arr[i];
                int j=i-1; 
                while (j>=0 && arr[j]>temp){ 
/*将temp与已排序元素从小到大比较，寻找temp应插入的位置*/ 
                          arr[j+1]=arr[j]; 
                          j--; 
              } 
                       arr[j+1]=temp; 
     } 
} 

最优复杂度：

当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度。

最差复杂度：

当输入数组为倒序时，复杂度为O(n^2)

与冒泡、选择相同，适用于排序小列表 ;若列表基本有序，则插入排序比冒泡、选择更有效率。