（2）排序算法——插入排序之直接插入排序

发表于   |   分类于   |   阅读次数

1、基本思想：

插入排序就是当前待排序的元素插入到一个已排序的列表中。排序的思路就像整理扑克牌，从未排序的扑克牌中摸起一张牌，插入到手中已排好序的牌中。与整理扑克不同的是，程序中不能直接将一个元素插入到两个元素之间，因此要将插入点之后的元素往后移动一个单元。

2、算法描述：

假定需要排序的数组为arr[n]，按降序排列。

  1. 从第一个元素arr[0]开始，可以认为该元素的已经排好序。这样的话我们只需要对剩余元素，即1 ~ n-1范围的元素进行排序。
  2. 取出下一个元素，将该元素与已经排好序的元素依次（从后向前）比较。
  3. 如果已排序的元素大于该元素，则直接将该元素与已排序的元素交换位置。并且将该元素与下一个（前一个）已排序的元素比较。
  4. 重复步骤3，直到找到已排序的元素小于或者等于该元素。
  5. 将该元素插入到下一位置。
  6. 重复步骤2~5，直到列表全部排序。

3、Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 直接插入算法
 * @author lizhen
 */
public class InsertSort {
	public void insertSort (int[] array) {
		// 降序排列
		for (int i = 1; i < array.length; i++) {
			int currentNum = array[i];
			for (int j = i; j > 0; j--) {
				if (array[j-1] <= currentNum) {
					array[j] = array[j-1];
					array[j-1] = currentNum;
				}
			}
		}
	}
}

以上程序，第二个for循环无论在什么情况下，每次都是循环i-1遍，而实际上，当要插入的元素找到合适的位置之后，就不需要再进行元素移动的操作了。所有可以优化为以下代码。需要插入的元素只需要在最后找到正确的位置之后进行插入即可。

1
2
3
4
5
6
7
8
9
10
11
public static void insertSort (int[] array) {
	// 降序排列
	int j;
	for (int i = 1; i < array.length; i++) {
		int currentNum = array[i];
		for (j = i; j > 0 && currentNum > array[j-1]; j--) {
			array[j] = array[j-1];
		}
		array[j] = currentNum;
	}
}

4、效率分析：

Alt text

注意：排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前和排序后他们的相对位置不发生变化。