算法基础：排序
基本概念
排序，就是让一组无序数据变成有序的过程。
衡量一个排序算法的优劣，主要从以下 3 个角度进行分析：
- 时间复杂度。具体包括：最好时间复杂度、最坏时间复杂度以及平均时间复杂度。
- 空间复杂度。如果空间复杂度为
O(1)，就叫作原地排序。 - 稳定性。排序的稳定性是指相等的数据对象，在排序之后，顺序是否能保证不变。
常见的排序算法及其思想
冒泡排序
public static void main(String[] args) {
int[] arr = { 1, 0, 3, 4, 5, -6, 7, 8, 9, 10 };
System.out.println("原始数据: " + Arrays.toString(arr));
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println("冒泡升序: " + Arrays.toString(arr));
}原理
从第一个数据开始，依次比较相邻元素的大小。如果前者大于后者，则进行交换操作，把大的元素往后交换。通过多轮迭代，直到没有交换操作为止。冒泡排序就像是在一个水池中处理数据一样，每次会把最大的那个数据传递到最后。
性能
最好时间复杂度：O(n)。当输入数组刚好是顺序的时候，只需要挨个比较一遍就行了，不需要做交换操作。
最坏时间复杂度：O(n^2)。当数组刚好是完全逆序的时候，每轮排序都需要挨个比较 n 次，并且重复 n 次。
平均时间复杂度：O(n^2)。当输入数组杂乱无章时，每轮排序都需要挨个比较 n 次，并且重复 n 次。
空间复杂度：O(1)。不需要额外的空间。
稳定性：元素相同时不做交换，是稳定的排序算法。
插入排序
public static void main(String[] args) {
int[] arr = { 2, 3, 5, 1, 23, 6, 78, 34 };
System.out.println("原始数据: " + Arrays.toString(arr));
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;
for (; j >= 0; j--) {
if (arr[j] > temp) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = temp;
}
System.out.println("插入升序: " + Arrays.toString(arr));
}原理
选取未排序的元素，插入到已排序区间的合适位置，直到未排序区间为空。插入排序顾名思义，就是从左到右维护一个已经排好序的序列。直到所有的待排数据全都完成插入的动作。
性能
最好时间复杂度：O(n)。当数组刚好是完全顺序时，每次只用比较一次就能找到正确的位置；这个过程重复 n 次，就可以清空未排序区间。
最坏时间复杂度：O(n^2)。当数组刚好是完全逆序时，每次都要比较 n 次才能找到正确位置；这个过程重复 n 次，就可以清空未排序区间。
平均时间复杂度：O(n^2)。往数组中插入一个元素的平均时间复杂度为 O(n)，而插入排序可以理解为重复 n 次的数组插入操作。
空间复杂度：O(1)。不需要开辟额外的空间。
稳定性：元素相同时不做交换，是稳定的排序算法。
归并排序
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 76, 13, 27, 50 };
System.out.println("原始数据: " + Arrays.toString(arr));
customMergeSort(arr, 0, arr.length - 1);
System.out.println("归并升序: " + Arrays.toString(arr));
}
public void customMergeSort(int[] a, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
// 对左侧子序列进行递归排序
customMergeSort(a, start, mid);
// 对右侧子序列进行递归排序
customMergeSort(a, mid + 1, end);
// 合并
customDoubleMerge(a, start, mid, end);
}
}
public void customDoubleMerge(int[] a, int left, int mid, int right) {
int[] tmp = new int[a.length];
int p1 = left, p2 = mid + 1, k = left;
while (p1 <= mid && p2 <= right) {
if (a[p1] <= a[p2])
tmp[k++] = a[p1++];
else
tmp[k++] = a[p2++];
}
while (p1 <= mid)
tmp[k++] = a[p1++];
while (p2 <= right)
tmp[k++] = a[p2++];
// 复制到原数组
for (int i = left; i <= right; i++)
a[i] = tmp[i];
}原理
归并排序的原理其实就是分治法。它首先将数组不断地二分，直到最后每个部分只包含 1 个数据。然后再对每个部分分别进行排序，最后将排序好的相邻的两部分合并在一起，这样整个数组就有序了。
性能
最好、最坏、平均时间复杂度：O(nlogn)。采用了二分的迭代方式，复杂度是 O(logn)。每次的迭代，需要对两个有序数组进行合并，这样的动作在 O(n) 的时间复杂度下就可以完成。同时，它的执行频次与输入序列无关。
空间复杂度：O(n)。每次合并的操作都需要开辟基于数组的临时内存空间。
稳定性：合并的时候，相同元素的前后顺序不变，是稳定的排序算法。
快速排序
public static void main(String[] args) {
int[] arr = { 6, 1, 2, 7, 9, 11, 4, 5, 10, 8 };
System.out.println("原始数据: " + Arrays.toString(arr));
customQuickSort(arr, 0, arr.length - 1);
System.out.println("快速升序: " + Arrays.toString(arr));
}
public void customQuickSort(int[] arr, int low, int high) {
int i, j, temp, t;
if (low >= high) {
return;
}
i = low;
j = high;
temp = arr[low];
while (i < j) {
// 先看右边，依次往左递减
while (temp <= arr[j] && i < j) {
j--;
}
// 再看左边，依次往右递增
while (temp >= arr[i] && i < j) {
i++;
}
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
arr[low] = arr[i];
arr[i] = temp;
// 递归调用左半数组
customQuickSort(arr, low, j - 1);
// 递归调用右半数组
customQuickSort(arr, j + 1, high);
}原理
快速排序法的原理也是分治法。它的每轮迭代，会选取数组中任意一个数据作为分区点，将小于它的元素放在它的左侧，大于它的放在它的右侧。再利用分治思想，继续分别对左右两侧进行同样的操作，直至每个区间缩小为 1，则完成排序。
性能
最好时间复杂度：O(nlogn)。每次选取分区点时，都能选中中位数，把数组等分成两个。
最坏时间复杂度：O(n^2)。每次分区都选中了最小值或最大值，得到不均等的两组。那么就需要 n 次的分区操作，每次分区平均扫描 n / 2 个元素。
平均时间复杂度：O(nlogn)。在大部分情况下，统计上是很难选到极端情况的，因为大多数时候都不是选中最大或最小值。
空间复杂度：O(1)。使用了交换法，不需要开辟额外的空间。
稳定性：快速排序的分区过程涉及交换操作，是不稳定的排序算法。
总结
插入排序和冒泡排序算法的异同点
- 插入排序和冒泡排序的平均时间复杂度都是
O(n^2)；且都是稳定的排序算法，都属于原地排序。 - 冒泡排序每轮的交换操作是动态的，所以需要三个赋值操作才能完成；而插入排序每轮的交换动作会固定待插入的数据，因此只需要一步赋值操作。
四种排序算法的对比
排序最暴力的方法，时间复杂度是 O(n^2)，如冒泡排序和插入排序。
如果利用算法思维去解决问题时，就会想到尝试分治法；此时，利用归并排序就能让时间复杂度降低到 O(nlogn)；然而，归并排序需要额外开辟临时空间，一方面是为了保证稳定性，另一方面则是在归并时，由于在数组中插入元素导致了数据挪移的问题。
如果采用快速排序。通过交换操作，可以解决插入元素导致的数据挪移问题，而且降低了不必要的空间开销。但是由于其动态二分的交换数据，导致了由此得出的排序结果并不稳定。
这些经典的排序算法没有绝对的好和坏，它们各有利弊。在实际使用过程中，需要根据实际问题的情况来选择最优的排序算法。比如，如果对数据规模比较小的数据进行排序，可以选择时间复杂度为 O(n^2) 的排序算法；但是对数据规模比较大的数据进行排序，就需要选择时间复杂度为 O(nlogn) 的排序算法了。