经典排序算法总结--冒泡、快排、插入、希尔、归并、选择

前言

互联网面试，排序是经典问题，总结几种经典排序代码，方便后期查阅。

本文链接 http://www.alijava.com/sort-summary/ 转载请注明出处。

如何测试编写的排序代码? 可以利用在线编程OJ系统 ，比如牛客网的
http://www.nowcoder.com/questionTerminal/508f66c6c93d4191ab25151066cb50ef

冒泡排序

对纵向排列的关键字序列，按照自下而上的扫描方向对两两相邻的关键字进行比较，
若为逆序(k_j < k_j-1 )，则将两个记录交换位置；
重复上述扫描排序过程，直至没有记录需要交换为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void bubbleSort(int[] arr, int size) {
	boolean swap = false;
	for (int i = 0; i < size - 1; i++) { //最多进行 n-1 趟
		swap = false;
		for (int j = size - 1; j > i; j--) { //从下往上扫描
			if (arr[j] < arr[j - 1]) {
				swap(arr, j, j - 1);
				swap = true;
			}
		}
		if (!swap) {
			break; // 未发生交换，终止算法
		}
	}
}

冒泡排序的优化：
至多需要 n-1 趟扫描，如果在某趟扫描后，待排序记录已是有序，可以在此趟扫描后终止。
可引入布尔量swap，每次扫描前值为false，若排序过程中发生了交换，置为true。
在一趟扫描后，如果swap仍为false，表示本次未曾交换记录，可以终止算法。

交换函数

1
2
3
4
5
public static void swap(int[] arr, int one, int two) {
	int temp = arr[one];
	arr[one] = arr[two];
	arr[two] = temp;
}

快速排序

通过一趟排序将记录序列分成两个子序列，
再分别对这两个子序列进行排序以达到整个序列有序。

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
// 排序范围 [start, end], 包含 end 
public static void quickSort(int[] arr, int start, int end) {
	if (start < end) {
		int p = partition(arr, start, end);
		quickSort(arr, start, p - 1);
		quickSort(arr, p + 1, end);
	}
}
// 一次划分代码，返回被划分后的基准位置
public static int partition(int[] arr, int left, int right) {
	int pivot = arr[left];
	while (left < right) {
		while (left < right && arr[right] >= pivot)
			right--;
		if (left < right)
			arr[left++] = arr[right];
		while (left < right && arr[left] <= pivot)
			left++;
		if (left < right)
			arr[right--] = arr[left];
	}
	arr[left] = pivot;
	return left;
}

快速排序的优化：
基准的选择影响快速排序的性能，最理想的情况是：选择的基准恰好能把待排序序列分成两个等长的子序列。

上文选择基准是固定使用序列的第1个元素，改进思路是：使用左端、右端和中间位置上的三个元素的中位数作为基准。

非递归实现 快速排序

思路就是用栈模拟递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void quickSort(int[] arr, int start, int end) {
	int[] stack = new int[end - start + 1]; // 数组模拟栈
	int len = 0;
	stack[len++] = start; // 入栈
	stack[len++] = end;
	while (len > 0) { // 栈中还有元素
		int right = stack[--len]; // 注意是 --len
		int left = stack[--len];
		int p = partition(arr, left, right);
		if (p - 1 > left) {
			stack[len++] = left;
			stack[len++] = p - 1;
		}
		if (p + 1 < right) {
			stack[len++] = p + 1;
			stack[len++] = right;
		}
	}
}

插入排序

把关键字k_i依次与有序区的关键字k_i-1、k_i-2、··· 、k_1比较
找到应该插入的位置，将k_i插入，后面的序列要往后移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void insertSort(int[] arr, int size) {
	int temp = arr[0];
	for (int i = 1; i < size; i++) {
		// 若 arr[i] 不小于有序区的最后一个元素，直接扩大有序区
		if (arr[i] < arr[i - 1]) { 
			temp = arr[i];
			int j = i - 1;
			while (j >= 0 && temp < arr[j]) {
				arr[j + 1] = arr[j--];
			}
			arr[j + 1] = temp;
		}
	}
}

希尔排序

插入排序当 n 较小时效率较高；当一组记录有序时，插入排序的算法复杂度可达到最优，即 O(n)。
希尔排序正是基于这两点对插入排序进行改进的。

希尔排序的基本思想：设置 t 个整数增量：d_1、d_2、···、d_t，其中d_1 < n, d_t=1
以d_1为增量，将所有距离为d_1的记录放到同一个组，可以得到d_1个组，在各组内进行直接插入排序；
然后取第二个增量d_2，重复上述的分组和排序，直至增量d_t=1

设置增量序列时，要使得增量值没有除 1 之外的公因子，最后一个增量值必须为 1。
希尔排序的时间复杂度取决于增量序列的选取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// shellSort(origins, origins.length, new int[] { 5, 3, 1 });
public static void shellSort(int[] arr, int size, int[] d) {
	for (int k = 0; k < d.length; k++) {
		int gap = d[k];
		for (int j = 0; j < gap; j++) { // 对于增量值 gap，一共 gap 组，0~gap-1
			for (int i = j + gap; i < size; i++) {
				if (arr[i] < arr[i - gap]) { // 如果大于，不需要插入排序
					int pivot = arr[i];
					int t = i - gap;
					while (t >= 0 && pivot < arr[t]) {
						arr[t + gap] = arr[t];
						t = t - gap;
					}
					arr[t + gap] = pivot;
				}
			}
		}
	}
}

归并排序

归并的含义是：将两个或两个以上的有序表合并成一个新的有序表。
归并排序的思路是：
假设初始表含有 n 个记录，可看成是 n 个有序的子表，每个子表的长度为1，然后两两归并，
得到 n/2 个长度为 2 的有序子表，再两两归并，如此重复，直至得到长度为 n 的有序子表为止。

合并两个有序表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 将arr[low]~arr[center]与arr[center+1]~arr[right]合并成有序表
public static void merge(int[] arr, int left, int center, int right) {
	int[] result = new int[right - left + 1];
	int i = left, j = center + 1, k = 0;
	while (i <= center && j <= right) {
		if (arr[i] < arr[j])
			result[k++] = arr[i++];
		else
			result[k++] = arr[j++];
	}
	while (i <= center)
		result[k++] = arr[i++];
	while (j <= right)
		result[k++] = arr[j++];
	System.arraycopy(result, 0, arr, left, right - left + 1);
}

一趟归并：
假设长度为n的待排序序列中，每个有序表的长度为 step，归并前共有n/step个子序列：
arr[0]~arr[step-1], arr[step]~arr[step*2-1], ··· ，一趟归并将相邻的一对有序表进行归并。
需要考虑三种情况：

  • 有序表的个数为偶数，且长度均为step
  • 有序表的个数为偶数，但最后一个有序表的长度小于step
  • 有序表的个数为奇数（轮空，不需要归并）
1
2
3
4
5
6
7
8
9
10
11
12
// 子表的长度为 step，对数组进行一趟归并
public static void mergePass(int[] arr, int step) {
	int length = arr.length;
	int i = 0;
	// 循环，归并长度为 step 的两个有序表
	for (; i + step * 2 - 1 < length; i += step * 2) {
		merge(arr, i, i + step - 1, i + step * 2 - 1);
	}
	if (i + step < length)
		merge(arr, i, i + step - 1, length - 1);
	// 注意: 若 i + step >= length, 最后一个子表轮空，无需归并
}

归并排序时，有序表的初始长度为1，每趟归并后有序表长度增大一倍；
若干趟归并后，有序表的长度>=n，排序结束。

1
2
3
4
5
public static void mergeSort(int[] arr, int size) {
	for (int i = 1; i < size; i *= 2) {
		mergePass(arr, i);
	}
}

直接选择排序

算法思路：第一趟排序将待排序记录 arr[0]~arr[n-1]作为无序区，从中找出最小的记录并与无序区
第1个记录arr[0]交换，此时得到有序区为arr[0]，无序区为arr[1]~arr[n-1]。
第二趟排序从arr[1]~arr[n-1]选出最小的记录，与arr[1]交换。
重复上述过程…

1
2
3
4
5
6
7
8
9
10
11
public static void selectSort(int[] arr, int size) {
	for (int i = 0; i < size; i++) {
		int min = i;
		for (int j = i + 1; j < size; j++) {
			if (arr[j] < arr[min])
				min = j;
		}
		if (min != i)
			swap(arr, min, i);
	}
}

堆排序

堆排序需要建立最小堆，参见这篇文章 http://www.alijava.com/heap-sort/

排序汇总

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定
冒泡 O(n2) O(n2) O(1) 稳定
快排 O(nlogn) O(n2) O(logn) 不稳定
插入 O(n2) O(n2) O(1) 稳定
希尔 O(n1.3) O(n2) O(1) 不稳定
归并 O(nlogn) O(nlogn) O(n) 稳定
选择 O(n2) O(n2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(1) 不稳定

利用递归实现快速排序，需要O(logn)的辅助空间;
归并排序大多数实现方法是O(logn)的辅助空间，少数是 O(1);
常见的稳定的排序为：冒泡、插入、归并。