一.摘要
什么叫做插入排序算法?在一组排序好的数组中插入当前值,找到插入的合适位置。很喜欢用来比喻的一个例子:咋俩一起打扑克牌,我左手拿着排序好的牌,右手将摸到的牌放到左手中,找到合适的位置保证插入后是有序的。
二.作用
Java或android开发中最简单的排序算法,适合对少量元素进行快速排序,不需要额外的存储空间,最坏的运行时间是O(n2),通常对数组进行排序或其他操作可以参考《Arrays方法解析》。
三.封装
插入排序算法根据排序的特点,选定一个position位置,确定当前值currentValue,然后让当前值与左边每个值比较,左边的值大于currentValue则彼此交换位置,继续一轮的比较,知道插入排序完成,代码如下:
第一种写法:
- public void insertSort(int[] array){
- if (array == null || array.length < 2) {
- return;
- }
- for (int i = 1; i < array.length; i++) {
- int position = i; //记录当前位置
- int currentValue = array[i]; //获取当前值
- //当前值与左边每个值比较,交换位置
- for (int j = i - 1; j >= 0; j--) {
- if (array[j] > currentValue) {
- array[j + 1] = array[j];
- position -= 1;
- } else {
- break;
- }
- array[position] = currentValue;
- }
- }
第二种写法:
- public void insertSort(int a[]){
- int length=a.length; //数组长度
- int j; //当前值的位置
- int i; //指向j前的位置
- int key; //当前要进行插入排序的值
- //从数组的第二个位置开始遍历值
- for(j=1;j<length;j++){
- key=a[j];
- i=j-1;
- //a[i]比当前值大时,a[i]后移一位,空出i的位置,好让下一次循环的值后移
- while(i>=0 && a[i]>key){
- a[i+1]=a[i]; //将a[i]值后移
- i--; //i前移
- }//跳出循环(找到要插入的中间位置或已遍历到0下标)
- a[i+1]=key; //将当前值插入
- }
- }
你可能感兴趣的文章
来源:TeachCourse,
每周一次,深入学习Android教程,关注(QQ158#9359$239或公众号TeachCourse)
转载请注明出处: https://www.teachcourse.cn/330.html ,谢谢支持!
转载请注明出处: https://www.teachcourse.cn/330.html ,谢谢支持!