1 冒泡排序

平均時(shí)間復雜度：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 選擇排序

平均時(shí)間復雜度：O(n^2)

穩定性：不穩定（排序后，相同元素的相對位置可能發(fā)生變化）

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 插入排序

平均時(shí)間復雜度：O(n^2)

穩定性：穩定（排序前后，相同元素的相對位置保持不變）

適用場(chǎng)景：部分元素已有序

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 希爾排序

平均時(shí)間復雜度：O(n^1.25)

穩定性：不穩定（排序后，相同元素的相對位置可能發(fā)生變化）

適用場(chǎng)景：大規模亂序

相關(guān)說(shuō)明：希爾排序是基于插入排序進(jìn)行改進(jìn)而來(lái)的算法。插入排序只交換相鄰的元素，在大規模亂序情況下，極有可能發(fā)生某個(gè)元素從某一端逐位交換至另一端，嚴重影響效率。希爾排序的思路是：先進(jìn)行遠距離跨越交換，從而使得元素盡快靠近最終位置，達到部分有序的目的，然后，再進(jìn)行插入排序（當H=1時(shí)）。

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 快速排序

平均時(shí)間復雜度：O(nlogn)

穩定性：不穩定（排序后，相同元素的相對位置可能發(fā)生變化）

相關(guān)說(shuō)明：首先，選擇一個(gè)元素，將其余元素分成三部分，一部分小于該元素，一部分大于該元素，一部分等于該元素。然后，對于前兩部分元素，再重復進(jìn)行上述操作，直至每個(gè)部分都已有序。

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 歸并排序

平均時(shí)間復雜度：O(nlogn)

穩定性：穩定（排序前后，相同元素的相對位置保持不變）

適用場(chǎng)景：合并多個(gè)已有序的子數組

相關(guān)說(shuō)明：分治思想（分而治之）的典型案例。有自頂向下和自底向上兩種方式。

// 自底向上方式
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++];
		}
	}
}

歸并兩個(gè)已有序的子數組

自底向上方式排序

7 堆排序

平均時(shí)間復雜度：O(nlogn)

穩定性：不穩定（排序后，相同元素的相對位置可能發(fā)生變化）

堆有序：在一顆二叉樹(shù)中，每個(gè)結點(diǎn)都大于等于它的兩個(gè)子節點(diǎn)。

二叉堆：堆有序的完全二叉樹(shù)。

二叉堆數組：將完全二叉樹(shù)的結點(diǎn)，按照層級順序，將每一層的結點(diǎn)，從左至右放入數組中，且下標從1開(kāi)始，即根節點(diǎn)的下標為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 用于排除已經(jīng)完成排序的位置
 */
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;
		}
	}
}

堆有序化

排序