java直接插入排序_JAVA_编程开发_程序员俱乐部

class="java" name="code">
public int[] insertSort(int[] a) {
/**
 * 直接插入排序
 * 把第一个数作为基准，所以排序的循环次数为n-1次 从第二个数开始和第一个数比较
 * 下面是降序排列
 * a[i] < a[i - 1] 如果第二个数小于第一个数，将第二个数记录一下int tmp = a[i]
 * 对前面的有序集合进行插入操作 j=i-1
 * （永远是对当前需要排序的值，插入到前面已经有序的集合里）
 * 从0到i-1 的空间里找出需要插入的位置
 *for (; j >= 0 && tmp< a[j]; j--) 
 *将数据向后移动 直到找到合适的位置 
 *eg: 假如 i = 3，此时j=2 对下面做插入操作
 *(26 48 53) 11 13 48 32 15
 * 0   1  2   3  4  5  6  7 
 * 11<53 则  a[3] = a[2] =53; 此时空出来53的位置 即a[2] 下面接着循环
 * 11<48 则  a[2] = a[1] = 48 把 a[1] 的位置让出来了。继续
 * 11<26 则  a[1] = a[0] = 26 把a[0] 位置的26 赋值给了a[1] 位置，让出a[0] 
 * 循环到了尽头，此时j<0 j=-1 
 * a[j+1] = tmp; 把值插入进去 把这个小的数据插入进去就可以了。

 *a[j + 1]=	a[j] ;
 *
 *
 *a[j+1] = tmp; 把值插入进去
 *
 * 
 */
	for(int i=1;i<a.length;i++){
		if(a[i]<a[i-1]){
			int tmp = a[i], j = i-1; //从后向前对有序的数进行插入，循环的长度应该是当前操作数的前一个数的索引位置。
			//eg：当前操作的是第4个数索引是3，那么插入操作就要针对前面的三个数做，即：j = 3-1=2 即（0-2）这些索引数里面操作。
			//下面for循环是:只要比当前操作数大就向后移动一位，让出当前位，如果比当前值小，直接插入到此值的后面
			for(;j>=0&&tmp<a[j];j--){
				a[j+1] = a[j];
			}
			a[j+1] = tmp;
		}
	}
	return a;
	}

	public static void main(String[] args) {
		InsertSort is = new InsertSort();
		int[] as = { 1, 34, 56, 23, 67, 82, 4, 3, 2, 0, 13, 76, 90, 21, 24, 44,
				4 };
		int[] a = is.insertSort(as);
		System.out.println(Arrays.toString(a));
	}

• 
• 大小: 32.1 KB

• 查看图片附件