插入排序>>代码实现，深度理解

今天中午正准备午休下
趴在电脑桌前
楼上公司装修的声音让我久久不能入眠。。。。
大家都玩过斗地主吧，一般我们抓好牌，都要对牌经行一系列的排序，从小到大，从大到小都行
就像如下图片

插入排序>>代码实现，深度理解
代码实现过程如同下图如图

好了废话不多说，先附上源码
有不清楚的地方可以留言

package com.huawei.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**

@author Lpf.
@version 创建时间：2019年4月3日下午1:24:18

*/
public class InsertSort {

public static void main(String[] args) {
	// 随机生成一个长度为30的list
	List<Integer> list = new ArrayList<>();
	for (int i = 0; i < 30; i++) {
		list.add((int) (1 + Math.random() * (100)));
	}
	Integer[] arr = new Integer[list.size()];
	arr = list.toArray(arr);
	System.out.println("原始数据" + Arrays.toString(arr));

	// insertSort1(arr); //调取第一中方法
	insertSort2(arr); // 调取优化后的方法
	System.out.println("排序后的" + Arrays.toString(arr));
}

public static void insertSort1(Integer[] arr) {

	for (int i = 1; i < arr.length; i++) { // 要对数组经行length-1次循环，仔细看完图二应该能够理解的
		for (int j = i; j > 0; j--) { // 每次内层循环经行数组位置的交换
			if (arr[j] < arr[j - 1]) {
				int temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
			}
		}
	}
}

/**
 * 针对上面的这个排序算法改进：首先上面的这个每次替换都要定义一个temp赋值需要插入的数，这样会造成不必要的浪费：
 * 所以我们可以吧所有的大于需要插入的数先保存，然后进行比较，然后将最后的正确位置空出来。吧之前保存的需要插入的数放到正确位置上；
 * 
 * @param arr
 */
public static void insertSort2(Integer[] arr) {

	for (int i = 1; i < arr.length; i++) {
		int temp = arr[i]; // 保存每次需要插入的那个数
		int j;
		for (j = i; j > 0 && arr[j - 1] > temp; j--) {// 这个较上面有一定的优化
			arr[j] = arr[j - 1];// 吧大于需要插入的数往后移动。最后不大于temp的数就空出来j
		}
		arr[j] = temp;// 将需要插入的数放入这个位置
	}
}

}

插入排序>>代码实现，深度理解

相关推荐