图解：常用排序算法（冒泡、选择、插入、希尔、快速、归并、堆）

1 冒泡排序

平均时间复杂度：O(n^2)

稳定性：稳定（排序前后，相同元素的相对位置保持不变）

private static void sort(int[] data) {
	for (int i = 0; i < data.length - 1; i++) {
		boolean complete = true;
		for (int j = 0; j < data.length - 1 - i; j++) {
			if (data[j] > data[j + 1]) {
				int temp = data[j];
				data[j] = data[j + 1];
				data[j + 1] = temp;
				complete = false;
			}
		}
		if (complete) {
			break;
		}
	}
}

2 选择排序

平均时间复杂度：O(n^2)

稳定性：不稳定（排序后，相同元素的相对位置可能发生变化）

private static void sort(int[] data) {
	for (int i = data.length - 1; i > 0; i--) {
		int maxIndex = i;
		for (int j = 0; j < i; j++) {
			if (data[j] > data[maxIndex]) {
				maxIndex = j;
			}
		}
		int temp = data[i];
		data[i] = data[maxIndex];
		data[maxIndex] = temp;
	}
}

3 插入排序

平均时间复杂度：O(n^2)

稳定性：稳定（排序前后，相同元素的相对位置保持不变）

适用场景：部分元素已有序

private static void sort(int[] data) {
	for (int i = 1; i < data.length; i++) {
		for (int j = i; j > 0; j--) {
			if (data[j] < data[j - 1]) {
				int temp = data[j];
				data[j] = data[j - 1];
				data[j - 1] = temp;
			} else {
				break;
			}
		}
	}
}

4 希尔排序

平均时间复杂度：O(n^1.25)

稳定性：不稳定（排序后，相同元素的相对位置可能发生变化）

适用场景：大规模乱序

相关说明：希尔排序是基于插入排序进行改进而来的算法。插入排序只交换相邻的元素，在大规模乱序情况下，极有可能发生某个元素从某一端逐位交换至另一端，严重影响效率。希尔排序的思路是：先进行远距离跨越交换，从而使得元素尽快靠近最终位置，达到部分有序的目的，然后，再进行插入排序（当H=1时）。

private static void sort(int[] data) {
	int N = data.length;
	int h = 1;
	while (h < N / 3) {
		h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
	}
	while (h >= 1) {
		for (int i = 0; i < h; i++) {
			for (int j = i + h; j < N; j = j + h) {
				for (int k = j; k > i; k = k - h) {
					if (data[k] < data[k - h]) {
						int temp = data[k];
						data[k] = data[k - h];
						data[k - h] = temp;
					} else {
						break;
					}
				}
			}
		}
		h = h / 3;
	}
}

5 快速排序

平均时间复杂度：O(nlogn)

稳定性：不稳定（排序后，相同元素的相对位置可能发生变化）

相关说明：首先，选择一个元素，将其余元素分成三部分，一部分小于该元素，一部分大于该元素，一部分等于该元素。然后，对于前两部分元素，再重复进行上述操作，直至每个部分都已有序。

private static void sort(int[] data, int leftStart, int rightEnd) {
	if (leftStart >= rightEnd)
		return;
	int leftIndex = leftStart;
	int rightIndex = rightEnd;
	int index = leftIndex + 1;
	int divisionValue = data[leftStart];
	while (index <= rightIndex) {
		if (data[index] < divisionValue) {
			int temp = data[index];
			data[index] = data[leftIndex];
			data[leftIndex] = temp;
			leftIndex++;
			index++;
		} else if (data[index] > divisionValue) {
			int temp = data[index];
			data[index] = data[rightIndex];
			data[rightIndex] = temp;
			rightIndex--;
		} else {
			index++;
		}
	}
	sort(data, leftStart, leftIndex - 1);
	sort(data, rightIndex + 1, rightEnd);
}

以首元素7分割数组

对于左半部分，重复操作：以首元素分割数组

6 归并排序

平均时间复杂度：O(nlogn)

稳定性：稳定（排序前后，相同元素的相对位置保持不变）

适用场景：合并多个已有序的子数组

相关说明：分治思想（分而治之）的典型案例。有自顶向下和自底向上两种方式。

// 自底向上方式
private static void sort(int[] data) {
	int N = data.length;
	for (int size = 1; size < N; size = size + size) {
		for (int leftStart = 0; leftStart + size < N; leftStart = leftStart + size + size) {
			merge(data, leftStart, leftStart + size - 1, Math.min(leftStart + size + size - 1, N - 1));
		}
	}
}
private static void merge(int[] data, int leftStart, int leftEnd, int rightEnd) {
	int leftIndex = leftStart;
	int rightIndex = leftEnd + 1; // rightStart
	int[] temp = new int[data.length];
	for (int k = leftStart; k <= rightEnd; k++) {
		temp[k] = data[k];
	}
	for (int k = leftStart; k <= rightEnd; k++) {
		if (leftIndex > leftEnd) {
			data[k] = temp[rightIndex++];
		} else if (rightIndex > rightEnd) {
			data[k] = temp[leftIndex++];
		} else if (temp[leftIndex] < temp[rightIndex]) {
			data[k] = temp[leftIndex++];
		} else {
			data[k] = temp[rightIndex++];
		}
	}
}

归并两个已有序的子数组

自底向上方式排序

7 堆排序

平均时间复杂度：O(nlogn)

稳定性：不稳定（排序后，相同元素的相对位置可能发生变化）

堆有序：在一颗二叉树中，每个结点都大于等于它的两个子节点。

二叉堆：堆有序的完全二叉树。

二叉堆数组：将完全二叉树的结点，按照层级顺序，将每一层的结点，从左至右放入数组中，且下标从1开始，即根节点的下标为1位置。

堆的有序化：

private static void swim(int[] data, int index) {
	while (index > 1) {
		if (data[index / 2] < data[index]) {
			int temp = data[index];
			data[index] = data[index / 2];
			data[index / 2] = temp;
			index = index / 2;
		} else {
			break;
		}
	}
}

上浮方式

private static void sink(int[] data, int index) {
	while (2 * index <= data.length - 1) {
		int childIndex = 2 * index;
		if (childIndex + 1 <= data.length - 1) {
			if (data[childIndex] < data[childIndex + 1]) {
				childIndex++;
			}
		}
		if (data[index] < data[childIndex]) {
			int temp = data[index];
			data[index] = data[childIndex];
			data[childIndex] = temp;
			index = childIndex;
		} else {
			break;
		}
	}
}

下沉方式

堆排序：

private static void sort(int[] data) {
	for (int index = (data.length - 1) / 2; index >= 1; index--) {
		sink(data, index, data.length - 1);
	}
	for (int index = data.length - 1; index > 1; index--) {
		int temp = data[index];
		data[index] = data[1];
		data[1] = temp;
		sink(data, 1, index - 1);
	}
}
/**
 * 
 * @param data
 * @param index
 * @param lastIndex 用于排除已经完成排序的位置
 */
private static void sink(int[] data, int index, int lastIndex) {
	while (2 * index <= lastIndex) {
		int childIndex = 2 * index;
		if (childIndex + 1 <= lastIndex) {
			if (data[childIndex] < data[childIndex + 1]) {
				childIndex++;
			}
		}
		if (data[index] < data[childIndex]) {
			int temp = data[index];
			data[index] = data[childIndex];
			data[childIndex] = temp;
			index = childIndex;
		} else {
			break;
		}
	}
}

堆有序化

排序