本文目录

1 冒泡排序

2 选择排序

3 插入排序

4 希尔排序

5 快速排序

6 归并排序

7 堆排序

8 相关文章

---

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);
}

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位置。

堆的有序化：以最大堆为例。

/**
 * 上浮法：将子节点逐步向上提升
 *
 * @param data 数组
 * @param index 起始位置
 */
private static void swim(int[] data, int index) {
  while (index > 1) {
    int parentIndex = index / 2;
    if (data[parentIndex] < data[index]) {
      swap(data, index, parentIndex);  // 交换位置
      index = parentIndex;
    } else {
      break;
    }
  }
}

/**
 * 下沉法：将父节点逐步向下沉淀
 *
 * @param data 数组
 * @param index 起始位置
 * @param stopIndex 截止位置
 */
private static void sink(int[] data, int index, int stopIndex) {
  while (index < stopIndex) {
    int maxValue = data[index], swapIndex = -1;
    int leftIndex = 2 * index, rightIndex = leftIndex + 1;
    if (leftIndex < stopIndex && data[leftIndex] > maxValue) {
      maxValue = data[leftIndex];
      swapIndex = leftIndex;
    }
    if (rightIndex < stopIndex && data[rightIndex] > maxValue) {
      maxValue = data[rightIndex];
      swapIndex = rightIndex;
    }
    if (swapIndex > -1) {
      swap(data, index, swapIndex);  // 交换位置
      index = swapIndex;
    } else {
      break;
    }
  }
}

堆排序：以下沉法为例。

/**
 * 通过下沉法，进行堆排序。
 *
 * @param data 数组
 */
private static void sort(int[] data) {
  // 堆有序化
  for (int index = (data.length - 1) / 2; index >= 1; index--) {
    sink(data, index, data.length);
  }
  // 排序
  for (int index = data.length - 1; index > 1; index--) {
    swap(data, 1, index);
    sink(data, 1, index);
  }
}

8 相关文章

《全排列（Java）》

《位运算：减法与补码》

《异或（^）的性质与应用》

《回溯算法（试探算法）》

《动态规划：鸡蛋掉落》

《动态规划：单词拆分》

《状态机：只出现一次的数字II》

《最小堆：TopK问题》

《链表：快慢指针》