一.java代码部分
public static void Insert_Sort(int []array)
{
for (int i=1;i 0 &&temp< array[j - 1]; j--) {
array[j] = array[j - 1];
}
array[j]=temp;
}
}二.代码分析部分
i变量 存储的是待排序部分第一个元素的下标
temp 储存的是数组下标为i的值
j变量 存储的是需要插入的数组下标
插入排序中是将一个未排序的元素插入前面已经排序的部分 也就是说在实际循环中下标i之前的数组已经是有顺序的了 所需要的只是在前面的有序数组中找到 一个位置合适的位置插入 依旧使的数组有序 就可以了
首先
外层循环变量i从1开始 数组后面的9个元素需要进行插入操作 每次循环后已经排序的部分长度加1
for (int i=1;i
temp 变量储存待排序部分第一个元素的值
int temp=array[i];
默认从小到大排序
循环的判断条件是如果temp小于下标j-1处的值 这个主要能够确定 temp在哪里执行插入操作 循环直到temp大于等于下标j-1的值 说明下标为j的部分就是temp需要插入的地方 但是在数组中原本下标为j的部分就已经储存了元素 这个就需要观察这个循环体了
循环体 array[j] = array[j - 1]注意 在这次循环条件不满足的时候这个j处表示是temp变量值插入的部分 但是这次循环的j处的值在j+1处已经有一份了 这个主要因为循环体在不满足表达式的上一个循环中所做的操作 所以才可以直接将temp的值插入就去保证数据的完整性
for ( j = i; j >0 &&temp< array[j - 1]; j--) {
array[j] = array[j - 1];
}最后部分就是在下标为j的部分插入元素
array[j]=temp;
}
}
具体效果如下
三.最好最坏情况分析
最坏情况就是 数组是逆序的 时间复杂度为O(
)
最好情况就是 数组已经是有序的了 那么内层循环条件始终为假 相当于没有内层循环 时间复杂度为O(n)
平均时间复杂度 O()
四.用时时间测试
排序耗时分析需要用到一个方法 该方法是System类的静态方法 返回值是Long型的具体是
System.currentTimeMillis();返回值是从1970年1月1日到现在的毫秒值
long begin = System.currentTimeMillis();
Sort.Insert_Sort(array);
long end=System.currentTimeMillis();
// 记录 多少毫秒
long ms=(end-begin);
System.out.println("\n运行时间排序"+max+"数字总共耗时"+ms+"毫秒");时间测试
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
