冒泡排序（Bubble Sort）

冒泡排序算法的操作如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 冒泡排序，a 表示数组，n 表示数组大小 
public void bubbleSort(int[] a, int n) { 
	if (n <= 1) return;

	for (int i = 0; i < n; ++i) { 
		// 提前退出冒泡循环的标志位 
		boolean flag = false; 
		for (int j = 0; j < n - i - 1; ++j) { 
			if (a[j] > a[j+1]) { // 交换 
				int tmp = a[j]; 
				a[j] = a[j+1]; 
				a[j+1] = tmp; 
				flag = true; // 表示有数据交换
			}
		} 
		if (!flag) break; // 没有数据交换，提前退出
	} 
}

插入排序（Insertion Sort）

插入排序算法的操作如下：

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤 2-5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 插入排序，a 表示数组，n 表示数组大小 
public void insertionSort(int[] a, int n) { 
	if (n <= 1) return;
	for (int i = 1; i < n; ++i) { 
		int value = a[i]; 
		int j = i - 1; 
		// 查找插入的位置 
		for (; j >= 0; --j) { 
			if (a[j] > value) { 
				a[j+1] = a[j]; // 数据移动
			} else { 
				break;
			}
		} 
		a[j+1] = value; // 插入数据
	} 
}

选择排序（Selection Sort）

选择排序算法的操作如下：

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
  2. 再从剩余未排序元素中继续寻找最小（大）元素；
  3. 放到已排序序列的末尾；
  4. 以此类推，直到所有元素均排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//a 表示数组，n 表示数组大小 
public void selectionSort(int[] a, int n) { 
	if (n <= 1) return;

	int temp = 0;
    for (int j = 0; j <n - 1;j++) {
        for (int i = j; i < n - 1; i++) {
            if (a[j] > a[i + 1]) {
                // 交换
                temp = a[j];
                a[j] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }
}

总结

原地排序算法，空间复杂度为 O(1)。
稳定的排序算法，相同元素的前后顺序不变。

原地排序 稳定的排序算法 最好 最坏 平均
冒泡排序 是 是 $$O(n) O(n^2) O(n^2)$$
插入排序 是 是 $$O(n) O(n^2) O(n^2)$$
选择排序 是 否 $$O(n^2) O(n^2) O(n^2)$$