java数据结构之插入排序

java数据结构之插入排序

插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。 一个非常形象的例子就是右手抓取一张扑克牌，并把它插入左手拿着的排好序的扑克里面。

插入排序的最坏运行时间是O(n2)， 所以并不是最优的排序算法。

如NfiMTmUh果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。

如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是(n2)。

简单例子：

public class Demo6 {

public static void main(String[] args) {

//定义一个整型数组

int[] nums = new int[]{4,3,-1,9,2,1,8,0,6};

//打印没有进行排序的数组

System.out.println("没有排序之前的结果:" + Arrays.toString(nums));

for(int index=0; index

//获得需要插入的数值

int key = nums[index];

//取得下标值

int position = index;

/循环比较之前排序好的数据，找到合适的地方插入

while(position >0 && nums[position-1] > key) {

nums[position] = nums[position-1];

position--;

}

nums[position] = key;

}

//打印排序后的结果

System.out.println("排序后的结果:" + Arrays.toString(nums));

}

}

//获得需要插入的数值

int key = nums[index];

//取得下标值

int position = index;

/循环比较之前排序好的数据，找到合适的地方插入

while(position >0 && nums[position-1] > key) {

nums[position] = nums[position-1];

position--;

}

nums[position] = key;

}

//打印排序后的结果

System.out.println("排序后的结果:" + Arrays.toString(nums));

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。