排序算法之插入排序

package com.wang.sort;
/**
 * 插入排序：每次将一个待排序的记录，按其关键之大小插入到前面已经排好序的子序列中的适当位置，知道全部记录插入完毕
 * 
 * @author wxe
 * @since 0.0.1
 */
public class InsertSort {
    public static int count = 0;
    
    public static void main(String[] args){
        int[] array = {2,3,7,3,9,4,5};
        insertSort(array, array.length);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ",");
        }
        System.out.println();
        System.out.println("总次数："+count);
    }
    
    public static void insertSort(int[] array,int length){
        for(int i = 1;i<length;i++){
            for (int j = i-1; j >=0 && array[j]>array[j+1]; j--) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                count++;
            }
        }
    }

}

比较相同数据，只需要5次排序即可，所以说插入排序还是优于冒泡排序的。
简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(n²)。