相比于冒泡排序、插入排序、选择排序，时间复杂度都为O(n^2)，适合小规模的数据排序，好处是前两者有稳定性，学习记录一下两种时间复杂度为O(nlogn)的排序算法，归并排序和快速排序。这两种排序算法适合大规模的数据排序。
排序算法的稳定性
仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，还有一个重要的度量指标，稳定性。
这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
比如我们有一组数据2，9，3，4，8，3，按照大小排序之后就是2，3，3，4，8，9。 这组数据里有两个3。经过某种排序算法排序之后，如果两个3的前后顺序没有改变，这种排序算法叫作稳定的排序算法;如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
归并排序
归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一
起，这样整个数组就都有序了。
分治与递归
归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
分治思想和递归思想很像。分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。
递推公式
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
- p 开始下标
- q 中间下标
- r 结束下标
终止条件
p >= r
merge_sort(p…r)表示，给下标从p到r之间的数组排序。
将这个排序问题转化为了两个子问题，merge_sort(p…q)和merge_sort(q+1…r)，其中下标q等于p和r的中间位置，也就是(p+r)/2。
当下标从p到q和从q+1到r这两个子数组都排好序之后，再将两个有序的子数组合并在一起，这样下标从p到r之间的数据就也排好序了。
示例代码
示例中我将p修改为left、q修改为mid、r修改为right以方便理解。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58public static void main(String[] args) {
int[] array = {4, 0, 3, 6, 1, 2, 9, 7, 8, 5};
Arrays.stream(array).forEach(System.out::print);
System.out.println();
mergeSortCopy(array, 0, array.length - 1);
Arrays.stream(array).forEach(System.out::print);
}
public static void mergeSortCopy(int[] array,int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) >> 1;
mergeSortCopy(array, left, mid);
mergeSortCopy(array, mid + 1, right);
mergeArray(array, left, mid, right);
}
public static void mergeArray(int[] array, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int tmpIndex = 0;
int pre = left;
int post = mid + 1;
while (pre <= mid && post <= right) {
if (array[pre] <= array[post]) {
tmp[tmpIndex++] = array[pre++];
} else {
tmp[tmpIndex++] = array[post++];
}
}
// 判断剩余元素位置
int start = pre;
int end = mid;
if (post <= right) {
start = post;
end = right;
}
// 将剩余元素拷贝至临时数组
while (start <= end) {
tmp[tmpIndex++] = array[start++];
}
/**
while (pre <= mid) {
tmp[tmpIndex++] = array[pre++];
}
while (post <= r) {
tmp[tmpIndex++] = array[post++];
}
*/
// 将临时数组拷贝至原数组
for (int i = 0; i < right - left + 1; i++) {
array[i + left] = tmp[i];
}
}
性能分析
归并排序是稳定排序算法么？
归并排序稳不稳定关键要看merge()函数，也就是两个有序子数组合并成一个有序数组的那部分代 码。
在合并的过程中，如果A[p…q]和A[q+1…r]之间有值相同的元素，那我们可以像伪代码中那样，先把A[p…q]中的元素放入tmp数组。这样就保证了值相同的元素， 在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。
时间复杂度
归并排序涉及递归，时间复杂度的分析稍微有点复杂。正好借此机会来学习一下，如何分析递归代码的时间复杂度。
递归的适用场景是，一个问题a可以分解为多个子问题b、c，那求解问题a就可以分解为求解问题b、c。问题b、c解决之后，我们再 把b、c的结果合并成a的结果。
如果我们定义求解问题a的时间是T(a)，求解问题b、c的时间分别是T(b)和 T( c)，那我们就可以得到这样的递推关系式:
T(a) = T(b) + T(c) + K
其中K等于将两个子问题b、c的结果合并成问题a的结果所消耗的时间。不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
套用这个公式，分析一下归并排序的时间复杂度。 假设对n个元素进行归并排序需要的时间是T(n)，那分解成两个子数组排序的时间都是T(n/2)。merge()函数合并两个有序子数组的时间复杂度是O(n)。
所以，套用前面的公式，归并排序的时间复杂度的计算公式就是:
T(1) = C;
n=1时，只需要常量级的执行时间，所以表示为C。
T(n) = 2*T(n/2) + n; n>1 通过这个公式，进一步分解一下计算过程来求解T(n)。
1 | T(n) = 2*T(n/2) + n |
通过这样一步一步分解推导，可以得到T(n) = 2^kT(n/2^k)+kn。
当T(n/2^k)=T(1)时，也就是n/2^k=1，我们得到k=log2n 。我们将k值代入上面的公式，得到T(n)=Cn+nlog2n 。如果我们用大O标记法来表示的话，T(n)就等于O(nlogn)。
所以归并排序的时间复杂度是O(nlogn)。 从我们的原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是O(nlogn)。
空间复杂度
归并排序由于merge时需要创建临时的数组存储数据，所以不是原地排序算法，即非O(1)。
尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会 超过n个数据的大小，所以空间复杂度是O(n)。
快速排序
快速排序利用的也是分治思想，乍看起来，优点像归并排序，但是思路其实完全不一样。
快排的主要思想是：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤后，数据p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面q+1到r之间是大于pivot的。
递推公式
根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。
1 | quick_sort(p...r) = quict_sort(p, q-1) + qucik_sort(q+1, r) |
终止条件
1 | p >= r |
通过游标i把数组[p…r-1]分成两部分。[p…i-1]的元素都是小于pivot的，我们暂且叫它“已处理区间”，A[i…r-1]是“未处理区 间”。我们每次都从未处理的区间[i…r-1]中取一个元素[j]，与pivot对比，如果小于pivot，则将其加入到已处理区间的尾部，也就是[i]的位置。
示例代码
1 | public void quickSort(int[] nums, int left, int right) { |
