其实我基础很差，最近无聊同时发现教别人的时候自己才会懂很多东西，给大家分析下面试经常遇到的插入排序。别只会用，要理解才行，随便写的，看不明白的联系我。老鸟飘过（JAVA代码，直接复制可用）
package com.chris;import java.util.ArrayList;import java.util.List;import java.util.Random;/** * 插入排序 * @author chris * */public class InsertSort { List<Integer> al;
/** * 构造方法，生成随机数组 * * @param num * @param mod */ public InsertSort(int num, int mod) { al = new ArrayList<Integer>(num); Random rand = new Random(); System.out.println("排序前的数据:"); for (int i = 0; i < num; i++) { al.add(new Integer(Math.abs(rand.nextInt()) % mod + 1)); System.out.println("al[" + i + "]=" + al.get(i)); } }
/** * 进行排序(由小到大) */ public void SortIt() { int tempInt; int MaxSize = 1;//待比较数据的索引，从第一个开始 System.out.println("/n/n【观察以下部分每行数据与排序前每个数据的位置】"); for (int i = 1; i < al.size(); i++) { tempInt = (int) al.remove(i);//移除当前位置的数据，并将这个数据存放到tempInt中 if (tempInt >= ((int) al.get(MaxSize - 1))) { al.add(MaxSize, tempInt);//如果移除的这个数据比前一个大，就把这个数据放回原位，不做处理 MaxSize++;//索引+1 System.out.println("当前list中的数据：" + al.toString()); //2,7，5 } else { /** * 下面的操作就是把这个数据插入当前索引之前第一个比它大的数据的索引的位置<br /> * 如果看不懂，就运行看效果就明白了br/> * */ for (int j = 0; j < MaxSize; j++) { if ((int) al.get(j) >= tempInt) { al.add(j, tempInt); MaxSize++;//索引+1 System.out.println("当前list中的数据：" + al.toString()); break; } } } } System.out.println("【观察以上部分每行数据与排序前每个数据的位置】/n/n"); System.out.println("排序后的数据:"); for (int i = 0; i < al.size(); i++) { System.out.println("al[" + i + "]=" + al.get(i)); } }
public static void main(String[] args) { InsertSort is = new InsertSort(10, 100); is.SortIt(); }}
