这里主要介绍两种最为常见的排序算法：快速排序，归并排序。
快速排序
快速排序的基本思路为对于一段区间进行快排，确定其中一个数的位置，并且保证在这个数前面的数都小于它，在这个数后面的数都大于它，再对这个数前后两个子区间递归快排。
快排递归的过程如下，partition() 为确定某个数位置的算法，返回值为该数的位置。
1
2
3
4
5
6
7
8
9
| vector<int> nums = {...};
void quicksort(int start, int end) {
if (start >= end) {
return;
}
int mid = partition(start, end);
quicksort(start, mid - 1);
quicksort(mid + 1, end);
}
|
最经典的、确定一个数位置的方法为错位交换。使用区间第一个元素作为哨兵，并置左右指针为区间两个端点。由右指针找到第一个小于等于哨兵的元素，赋给左指针元素，再由左指针遍历找到第一个大于等于哨兵的元素，赋给右指针，如此往复。代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int partition(int start, int end) {
int pivot = nums[start];
int left = start, right = end;
while (left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
nums[left] = nums[right];
while (left < right && nums[left] <= pivot) {
left++;
}
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}
|
另一种方法是对称交换。使用区间的第一个元素作为哨兵，然后从左右两端开始找第一个大于哨兵的元素和小于哨兵的元素，进行交换。代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int partition(int start, int end) {
int pivot = nums[start];
int left = start, right = end, mid;
while (left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
while (left < right && nums[left] <= pivot) {
left++;
}
if (left < right) {
swap(nums[left], nums[right]);
}
}
swap(nums[start], nums[left]);
return left;
}
|
在快排中，有时会遇到每次确定的元素均在区间的端点，快排的时间复杂度会退化到 O(n^2)。此时，需要对快排进行优化，优化的主要策略是随机取哨兵元素（或是取某些特殊点，例如中间的值），与区间的第一个元素交换后，再按正常的快排来做。
归并排序
归并排序采用分治的策略，对于两个已经排好序的序列，可以通过一次遍历完成两个有序序列的归并。
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
| vector<int> nums = {...}, tmp(nums.size());
void mergesort(int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) >> 1;
mergesort(start, mid);
mergesort(mid + 1, end);
int i = start, j = mid + 1, k = start;
while (i <= mid && j <= end) {
if (nums[i] < nums[j]) {
tmp[k] = nums[i];
i++;
}
else {
tmp[k] = nums[j];
j++;
}
k++;
}
for (; i <= mid; i++, k++) {
tmp[k] = nums[i];
}
for (; j <= end; j++, k++) {
tmp[k] = nums[j];
}
for (k = start; k <= end; k++) {
nums[k] = tmp[k];
}
}
|
由于需要归并，这里开辟一个额外的数组 tmp 用于临时存储归并后的序列，再赋回原数组。在分治区间的划分上，有用到二分中的思想，避免死循环。
