首页 > 代码库 > 直接插入排序

直接插入排序

1、算法思想:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增加1的有序表。
        假设待排序的数据是数组A[1….n]。初始时,A[1]自成1个有序区,无序区为A[2….n]。在排序的过程中,依次将A[i] (i=2,3,….,n)从后往前插入到前面已排好序的子数组A[1,…,i-1]中的适当位置,当所有的A[i] 插入完毕,数组A中就包含了已排好序的输出序列。
2、代码实现:
public void sort(int[] list,int size){
    for (int i = 1;i<size;i++) {
int temp = list[i]; //要插入的数值
for (int j = 0;j<i;j++){
if (temp<list[j]){
for (int m = i-1;m>=j;m--){
list[m+1] = list[m]; //依次顺移
}
list[j] = temp ;
break; //插入后退出循环(记得已经找到并插入后要退出)
}
}
}
}
3、复杂度分析:1.当要排序的表本身就是有序的,则没有移动记录,时间复杂度为O(N)2.当要排序的表是逆序时,需要比较N+N-1+...+2=(N+2)(N+1)/2次,如果排序记录是随机的,根据概率相同原则,则平均比较和移动次数约为N^2/4次。因此,直接插入排序法的时间复杂度为O(N^2).

直接插入排序