插入排序————Java实现

插入排序（InsertSort）

插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。1、思想 每次选择一个元素K插入到之前已排好序的部分A[1…i]中，插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现发现A[x]>=K,则将K插入到A[x]的后面，插入前需要移动元素

2、算法时间复杂度

最好的情况下：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n)          最坏的情况下：逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n^­2)          平均情况下：O(n^­2)

3、稳定性

插入排序是稳定的

4、实现

public static void insertSort(int []data , int low ,int high){

for(int i = low ;i < high;i++){

int temp = data[i];

int j = i -1 ;

for(;j>=0 && temp<data[j];j--){

data[j+1] = data[j];

}

data[j+1] = temp;

}

}