首页 > 代码库 > 直接插入排序
直接插入排序
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）.
直接插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。