常用排序算法

热度 ℃

常用的排序算法：冒泡排序，快速排序，选择排序，插入排序。

1.冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

下面是一个数组的排序过程，两两比较，如果前一个元素大于后一个元素，则交换值。每循环一次，第二次循环的时候循环次数就减少1次。

实例演示：

1
2
3
4
5
4.2.6.7.3.8
2.4.6.7.3.8
2.4.6.3.7.8
2.4.3.6.7.8
2.3.4.6.7.8

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bubbleSort(int[] numbers) {
	int temp = 0;
	int size = numbers.length;
	for (int i = 0; i < size - 1; i++) {
		for (int j = 0; j < size - 1 - i; j++) {
			if (numbers[j] > numbers[j + 1]) // 交换两数位置
			{
				temp = numbers[j];
				numbers[j] = numbers[j + 1];
				numbers[j + 1] = temp;
			}
		}
	}
}

2.快速排序

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是：

    1. 设置两个变量i、j，排序开始的时候：i=0，j=N-1；
    1. 以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
    1. 从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]互换;
    1. 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换;
    1. 重复第3、4步，直到i=j；(3, 4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

实例演示：

1
2
3
4
5
6
// k = 49, i = 0; j = 6
49 38 65 97 76 13 27 // 查找第一个比49小的，j=6; // i = 0; j = 6
27 38 65 97 76 13 49 // 查找第一个比49大的，i=2; // i = 2; j = 6
27 38 49 97 76 13 65 // 查找第一个比49小的，j=5; // i = 2; j = 5
27 38 13 97 76 49 65 // 查找第一个比49大的，i=3; // i = 3; j = 5
27 38 13 49 76 97 65 // 查找第一个比49小的，j=3; // j == i; 结束循环

注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对第一遍排序后k对应的索引两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

算法实现：

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
/**
 * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
 * @param numbers 带查找数组
 * @param low 开始位置
 * @param high 结束位置
 * @return 中轴所在位置
 */
public static void fastSort(int[] numbers, int i, int j) {
	if (i < j) {
		int m = getMiddle(numbers, i, j);
		fastSort(numbers, i, m - 1);
		fastSort(numbers, m + 1, j);
	}
}
public static int getMiddle(int[] numbers, int i, int j) {
	int k = numbers[i];
	int temp = 0;
	while (j > i) {
		while (numbers[j] > k && j > i) {
			j--;
		}
		temp = numbers[j];
		numbers[j] = numbers[i];
		numbers[i] = temp;
		while (numbers[i] < k && j > i) {
			i++;
		}
		temp = numbers[j];
		numbers[j] = numbers[i];
		numbers[i] = temp;
	}
	return i;
}

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

快速排序参考：baike

3.选择排序

算法思路：

    1. 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
    1. 在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止；

实例演示：

1
2
3
4
初始数组：57 68 59 52
最小值52，与第一个数交换：52 68 59 57
最小值57，与第二个数交换：52 57 59 68
59就是最小值，无需交换，排序完成：52 57 59 68

算法实现：

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
public static void selectSort2(int[] numbers) {
	for (int i = 0; i < numbers.length - 1; i++) {
		int k = i;
		int min = numbers[i];
		for (int j = i + 1; j < numbers.length; j++) {
			if (min > numbers[j]) {
				min = numbers[j];
				k = j;
			}
		}
		int temp = numbers[k];
		numbers[k] = numbers[i];
		numbers[i] = temp;
	}
}
public static void selectSort3(int[] numbers) {
	for (int i = 0; i < numbers.length - 1; i++) {
		int k = i;
		for (int j = i + 1; j < numbers.length; j++) {
			if (numbers[k] > numbers[j]) {
				k = j;
			}
		}
		int temp = numbers[k];
		numbers[k] = numbers[i];
		numbers[i] = temp;
	}
}

4.插入排序

算法思路：每步将一个待排序的记录，按其顺序码大小插入到前面已经排好序的序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

实例演示：

1
2
3
4
初始状态：57 68 59 52
step1: 57 < 68，不作处理
step2: 68 > 59，59插入到57之后：57 59 68 52
step3: 52 < 68，52 < 59，52 < 57，52插入到57之前：52 57 59 68

step3: 需要不断的比较两两相邻元素的数值。

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 从第一个元素开始，该元素可以认为已经被排序，取出下一个元素，在已经排序的元素序列中从后向前扫描
 */
public static void insertSort(int[] numbers) {
	for (int i = 1; i < numbers.length; i++) {
		for (int j = i; j >= 1; j--) {
			if (numbers[j] < numbers[j - 1]) {
				int temp = numbers[j - 1];
				numbers[j - 1] = numbers[j];
				numbers[j] = temp;
			}
		}
	}
}

参考: Link

红黑数，2-3数