- 算法总览
- 冒泡排序（Bubble Sort）
- 选择排序（Selection Sort）
- 插入排序（Insertion Sort）
排序算法作为面试必问的题目，其重要性不言而喻，因此必须掌握每种算法的思路以及时间、空间复杂度，最好能够手写出各个排序算法的代码。下面，我将结合 其他资料以及自己的理解，逐个分析十种排序算法。 算法总览
比较类排序：通过比较来决定元素间的相对次序，其时间复杂度不能突破O(nlogn)。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行。
稳定：如果 a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
不稳定：如果 a 原本在 b 的前面，而 a = b，排序之后 a 可能会出现在 b 的后面。
按时间复杂度可以分为三类排序
1. O(n * 2)
选择排序、插入排序、冒泡排序
2. O(n * logn)
快速排序、归并排序、堆排序
3. O(n)
计数排序、桶排序、基数排序
从第一个数开始遍历，如果大于后面的数，就交换位置，交换后继续比较，直至有序。
public class Test {
// 常规冒泡排序
public static void BubbleSort(int[] arr) {
// 外层循环：比较的轮次
for (int i = 0; i < arr.length - 1; i++) {
// 内层循环：每一轮将当前的最大值交换至最后位置，同时缩短数组范围
// 从第一个数开始遍历，如果大于后面的数，就交换位置，交换后继续比较，直至将最大值放至末尾
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
}
}
}
// 冒泡排序优化：设置标志位，当目前数组已经有序后，不用再继续遍历比较。
// 最好情况时间复杂度可降低至 O(N)：即当初始数组已经是一个有序数组的情况。
public static void BubbleSortOptimize(int[] arr) {
// 设置标志位，作为判断是否已经有序的标志
int flag = 0;
int length = arr.length;
// 如果此时数组长度不为 0 ，则循环
while (length > 0) {
// 每一轮都需要更新标志为：0
flag = 0;
// 从第一个数开始遍历，如果大于后面的数，就交换位置，交换后继续比较，直至将最大值放至末尾
for (int i = 0; i < length - 1; i++) {
if (arr[i] > arr[i + 1]) swap(arr, i, i + 1);
// 更新标志位：记录下当前最大值的位置
flag = i + 1;
}
// 更新长度
length = flag;
}
}
// 交换数组元素方法
public static void swap(int[] arr, int cur, int next) {
int temp = arr[cur];
arr[cur] = arr[next];
arr[next] = temp;
}
// 测试
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
BubbleSortOptimize(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
外层 for 循环次数：n - 1；
内层 for 循环次数（平均）：(n - 1) + (n - 2) + … + 1 = n * (n - 1) / (2 * (n - 1)) = n / 2；
时间复杂度：(n - 1) * n / 2 = O(n * 2)。 -
时间复杂度（最坏）
外层 for 循环次数：n - 1；
时间复杂度 ：(n - 1) + (n - 2) + … + 1 = n * (n - 1) / 2 = O(n * 2) -
时间复杂度（最好）
最好情况时间复杂度可降低至 O(N)：即当初始数组已经是一个有序数组的情况，见上述方法 BubbleSortOptimize(int[] arr)。 -
空间复杂度
O(1)： 只需原地交换元素，使用常数大小的额外空间。
稳定性
稳定：a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
public class Test {
public static void SelectionSort(int[] arr) {
// 保存最小元素的数组下标
int minIndex = 0;
// 外层循环：确定无序数组的左边界下标
for (int i = 0; i < arr.length - 1; i++) {
minIndex = i;
// 内层循环：找出 [i, arr.length] 中的最小值下标，并与 i 位置的元素进行替换
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
swap(arr, i, minIndex);
}
}
// 交换数组元素方法
public static void swap(int[] arr, int cur, int minIndex) {
int temp = arr[cur];
arr[cur] = arr[minIndex];
arr[minIndex] = temp;
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
SelectionSort(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
- 时间复杂度（平均）
外层 for 循环次数：n - 1；
内层 for 循环次数（平均）：(n - 1) + (n - 2) + … + 1 = n * (n - 1) / (2 * (n - 1)) = n / 2；
时间复杂度：(n - 1) * n / 2 = O(n * 2)。 - 时间复杂度（最坏）
外层 for 循环次数：n - 1；
时间复杂度 ：(n - 1) + (n - 2) + … + 1 = n * (n - 1) / 2 = O(n * 2)。 - 时间复杂度（最好）
O(n * 2)：同平均和最坏情况。 - 空间复杂度
O(1)： 只需原地交换元素，使用常数大小的额外空间。
稳定性
不稳定：a 原本在 b 前面，而 a = b，排序之后 a 不在 b 的前面（当将最大元素放至数组末尾的时候会出现该情况）。
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
public class Test {
public static void InsertionSort(int[] arr) {
// 外层循环：遍历第一个元素以外的所有其他元素，将其插入到前面的有序数组中
for (int i = 1; i < arr.length; i++) {
// 保存前一个元素的下标
int preIndex = i - 1;
// 保存待插入的当前元素
int current = arr[i];
// 如果前一个元素下标合法，同时元素值大于待插入的当前元素
// 则将前一个元素向后移动，同时前一个元素下标向前移动
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
// 将待插入元素插入到合适的位置
arr[preIndex + 1] = current;
}
}
public static void main(String[] args) {
int[] arr = {6, 5, 4, 3, 2, 1};
InsertionSort(arr);
for (int num : arr) System.out.println(num);
}
}
时间/空间复杂度分析
-
时间复杂度（平均）
外层 for 循环次数：n - 1；
内层 for 循环次数（平均）：1 + 2 + … + (n - 2) + (n - 1) = n * (n - 1) / (2 * (n - 1)) = n / 2；
时间复杂度：(n - 1) * n / 2 = O(n * 2)。 -
时间复杂度（最坏）
外层 for 循环次数：n - 1；
时间复杂度 ：1 + 2 + … + (n - 2) + (n - 1) = n * (n - 1) / 2 = O(n * 2) -
时间复杂度（最好）
最好情况时间复杂度为 O(N)：即当初始数组已经是一个有序数组的情况，只需考虑外层循环复杂度即可。 -
空间复杂度
O(1)： 只需原地交换元素，使用常数大小的额外空间。
稳定性
稳定：a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面。
