排序算法之插入排序 |Java 刷题打卡

排序算法之插入排序 |Java 刷题打卡

技术杂谈小彩虹2021-09-13 17:00:15641A+A-

本文正在参加「Java主题月 - Java 刷题打卡」,详情查看 活动链接

1、算法思想

  1. 从第一个元素开始,该元素可以认为已经被排序

  2. 取出第一个未排序元素存放在临时变量temp中,在已经排序的元素序列中从后往前扫描,逐一比较

  3. 如果temp小于已排序元素,将该元素移到下个位置

  4. 重复步骤3,直到找到已排序的元素小于或者等于

2、实例分析

{13,15,37,89,60,39,12,109,56,72}

第一趟: 13 {15,37,89,60,39,12,109,56,72} temp = 15

temp>13

第二趟: 13 ,15 { 37,89,60,39,12,109,56,72} temp = 37

temp>15 temp>13

第三趟: 13,15 ,37 {89,60,39,12,109,56,72} temp = 89

temp>37 temp>15 temp>13

第三趟: 13,15 ,37 ,89 {60,39,12,109,56,72} temp =60

temp< 89:60<->89 13,15 ,37 , 60,89 {39,12,109,56,72}

temp>37 temp>15 temp>13

第四趟: 13,15 ,37 , 60,89 {39,12,109,56,72} temp = 39

temp<89: 39<->89 13,15 ,37 , 60,39,89 {12,109,56,72}

temp<60 : 39<->60 13,15 ,37 , 39,60,89 {12,109,56,72}

temp>37 temp>15 temp >13

第五趟: 13,15 ,37 , 39,60,89 {12,109,56,72} temp = 12

temp<89 :12<->89 13,15 ,37 ,39,60, 12,89 {109,56,72}

temp<60:12<->60 13,15 ,37 ,39,12,60,89 {109,56,72}

temp<39 :12<->39 13,15 ,37 ,12,39,60,89 {109,56,72}

temp<37 :12<->37 13,15 ,12 ,37 ,39,60,89 {109,56,72}

temp<15: 12<->15 13,12,15 ,37 ,39,60,89 {109,56,72}

temp<13 :12<->13 12,13,15 ,37 ,39,60,89 {109,56,72}

第六趟: 12,13,15 ,37 ,39,60,89 {109,56,72} temp = 109

……

3、算法代码

import java.util.Arrays;

/** * 插入排序 * @author xcbeyond * */
public class InsertSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		a = insertSort(a);
		String s = Arrays.toString(a);
		System.out.println(s);
	}
	
	public static int[] insertSort(int[] ary){
		for(int i = 1;i < ary.length;i++){
			int temp = ary[i];
			int j;
			for(j = i-1;j>=0 && temp < ary[j];j--){
				ary[j+1] = ary[j];
			}
			ary[j+1] = temp;
		}
		
		return ary;
	}
}

另一种(易于理解):

import java.util.Arrays;

/** * 插入排序 * @author xcbeyond * */
public class InsertSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		a = insertSort(a);
		String s = Arrays.toString(a);
		System.out.println(s);
	}
	
	public static int[] insertSort(int[] ary){
		for(int i = 1;i < ary.length;i++){
			int temp = ary[i];
			int j;
			for(j = i-1;j>=0;j--){
				if(temp < ary[j]){
					ary[j+1] = ary[j];
				}
				else
					break; //找到插入位置
			}
			ary[j+1] = temp;
		}
		
		return ary;
	}
}

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交
  • 1条评论

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示 | 支付宝红包
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1
本网站由 提供CDN/云存储服务

联系我们