1 冒泡排序

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

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

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í)間復(fù)雜度：O(n^2)

穩(wěn)定性：不穩(wěn)定（排序后，相同元素的相對位置可能發(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í)間復(fù)雜度：O(n^2)

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

適用場景：部分元素已有序

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í)間復(fù)雜度：O(n^1.25)

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

適用場景：大規(guī)模亂序

相關(guān)說明：希爾排序是基于插入排序進(jìn)行改進(jìn)而來的算法。插入排序只交換相鄰的元素，在大規(guī)模亂序情況下，極有可能發(fā)生某個元素從某一端逐位交換至另一端，嚴(yán)重影響效率。希爾排序的思路是：先進(jìn)行遠(yuǎn)距離跨越交換，從而使得元素盡快靠近最終位置，達(dá)到部分有序的目的，然后，再進(jìn)行插入排序（當(dāng)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í)間復(fù)雜度：O(nlogn)

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

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

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分割數(shù)組

對于左半部分，重復(fù)操作：以首元素分割數(shù)組

6 歸并排序

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

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

適用場景：合并多個已有序的子數(shù)組

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

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

歸并兩個已有序的子數(shù)組

自底向上方式排序

7 堆排序

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

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

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

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

二叉堆數(shù)組：將完全二叉樹的結(jié)點(diǎn)，按照層級順序，將每一層的結(jié)點(diǎn)，從左至右放入數(shù)組中，且下標(biāo)從1開始，即根節(jié)點(diǎn)的下標(biāo)為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;
		}
	}
}

堆有序化

排序