文章

插入排序 - Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 *  "插入排序 ",对少量元素进行排序的有效算法。
 *  《算法导论》原文摘要:
 * Insertion sort works the way many people sort a hand
 * of playing cards. We start with an empty left hand and the cards face down on
 * the table. We then remove one card at a time from the table and insert it
 * into the correct position in the left hand. To find the correct position for
 * a card, we compare it with each of the cards already in the hand, from right
 * to left, as illustrated in Figure 2.1. At all times, the cards held in the
 * left hand are sorted, and these cards were originally the top cards of the
 * pile on the table. 
 * 伪代码如下: 
 * for j<- 2 to length[A] 
 * 	do key <- A[j] 
 * 		>Insert A[j] into the sorted sequence A[1..j-1] (>符号代表后面的部分是注释)
 * 		i <- j-1 
 * 		while i>0 and A[i]>key 
 * 			do A[i+1] <- A[i] 
 * 			i <- i-1 
 * 		A[i+1] <- key 
 * 算法复杂度:n^2
 * @author lihzh(OneCoder)
 * @OneCoder-Blog http://www.coderli.com
 */
public class InsertionSort {

	private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };

	public static void main(String[] args) {
		//从数组第二个元素开始排序,因为第一个元素本身肯定是已经排好序的
		for (int j = 1; j < input.length; j++) {// 复杂度 n
			int key = input[j];
			int i = j - 1;
			//依次跟之前的元素进行比较,如果发现比前面的原素小,则交换位置,最终完成排序。
			while (i >= 0 && input[i] > key) {//复杂度:1+2+...+(n-1)=&Theta;(n^2)
				input[i + 1] = input[i];
				input[i] = key;
				i--;
			}
		}
		/*
		 * 所以最终复杂度为n*n=n^2。最优情况下(即都已经排列好的情况下),第二个n=1, 所以在最优情况下,复杂度为n。
		 */
		// 打印数组
		printArray();
	}

	private static void printArray() {
		for (int i : input) {
			System.out.print(i + " ");
		}
	}
}
本文由作者按照 CC BY 4.0 进行授权