几种排序算法的思想与实现。
快速排序
思想
快速排序基于分治的思想，从待排序数组中任意选择一个元素作为枢轴pivot，经过一轮排序过后，pivot元素被放置在适当位置上，其左边的元素都小于它，右边的元素都大于等于它。
代码
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
|
int partition(std::vector<int>& nums, int left, int right) {
int mid = left + (right - left) / 2;
if (nums[left] > nums[mid]) std::swap(nums[left], nums[mid]);
if (nums[mid] > nums[right]) std::swap(nums[mid], nums[right]);
if (nums[left] > nums[mid]) std::swap(nums[left], nums[mid]);
std::swap(nums[left], nums[mid]);
int pivot = nums[left];
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;
}
void quickSort(std::vector<int>& nums, int left, int right) {
if (left >= right) return;
int mid = partition(nums, left, right);
quickSort(nums, left, mid - 1);
quickSort(nums, mid + 1, right);
}
int main() {
std::vector<int> a = {3, 4, 5, 6, 1, 6, 3, 7};
quickSort(a, 0, static_cast<int>(a.size()) - 1);
std::copy(a.begin(), a.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}
|
复杂度分析
（1）空间复杂度
算法需要递归栈，其复杂度与递归调用次数一致。最好情况 logN， 最坏N，平均logN
（2）时间复杂度：平均O（NlogN）
复杂度解释：
以F（n）表示长度为n的区间比较次数，我们可以得到：
$F(n) = n+2F(n/2) =n+2(n/2 +2(F(n/4)))=2n+4F(n/4)$
不难看出：
$F(n) = k*n +2^kF(n/2^k)$
当k为$log_2^n$ 时， $F(n) = nlog_2^n +nF(1)$ ，F（1）为0，因此$F(n) = nlog_2^n$
插入排序
每次选取一个元素插入到已排好序的数组，重复直到全部排好序。
直接插入排序
步骤：
- 找出L[i]在L[1..i-1]的插入位置k
- 将L[k..i-1]所有元素后移一位
- 复制L[i] 到L[k]
空间复杂度：O（1）
时间复杂度：O（N^ 2）
优化：折半查找出插入位置k，时间复杂度仍然为O（N^ 2）
希尔排序
（1）思想
直接插入排序只适用于基本有序的排序表和数据量小的表。直接插入排序的特点就是数据越有序，速度越快。
希尔排序希望通过间隔设计，使得数组基本有序，然后优化插入排序。
（2）步骤
希尔排序算法：
- 表中距离为增量”d“的元素为一组，对各组进行直接插入排序。
- 然后缩小增量，重复排序过程。
- 最后整张表基本有序，对全体进行一次插入排序。
归并排序
思想
基于分值，把数组分为两份，两份都排好序，我只需合并两个已排好序的数组。
归并：将两个或以上的有序表合并为一个新有序表的过程。
2路归并排序：n个元素视作n张有序表，进行2-归并，那么剩下 $\lceil n/2 \rceil$ 张表。重复此过程，直至合并为一个大表。
代码
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
| void merge(std::vector<int>& nums, int l1, int r1, int l2, int r2) {
std::vector<int> temp;
int i = l1, j = l2;
while (i <= r1 && j <= r2) {
if (nums[i] <= nums[j]) {
temp.push_back(nums[i++]);
} else {
temp.push_back(nums[j++]);
}
}
while (i <= r1) temp.push_back(nums[i++]);
while (j <= r2) temp.push_back(nums[j++]);
for (int k = 0; k < static_cast<int>(temp.size()); ++k) {
nums[l1 + k] = temp[k];
}
}
void mergeSort(std::vector<int>& nums, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, mid + 1, right);
}
int main() {
std::vector<int> a = {3, 4, 5, 6, 1, 6, 3, 7};
mergeSort(a, 0, static_cast<int>(a.size()) - 1);
std::copy(a.begin(), a.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}
|
性能分析
空间复杂度：递归O（logN），新开辟数组O（N）。
时间复杂度：O（NlogN），一趟比较N，一共logN趟。
堆排序
堆的概念
堆：一维数组可在逻辑上看作一颗完全二叉树，若每个结点的值都大于其左右结点的值，则称之为大顶堆。
数学描述：数组 L[1…N] ，满足 $L_k \ge L_{2k} , L_k \ge L_{2k+1}$
1
2
3
4
5
| 1 k
/ \ / \
2 3 2k 2k+1
/ \ / \
4 5 6 7
|
注意：在实际数组存储中，根结点从0开始，那么左右子树的结点关系是2k+1和2k+2.
堆排序思想
堆排序算法的思想：将数组调整为堆，取堆顶就能得到当前最大/小的元素。然后再把剩余的数组元素调整为新堆，再次取堆顶元素，重复直到数组剩余一个元素。
算法流程：
- 初始化：将乱序数组调整为堆；
- 输出根结点，然后交换堆顶元素与堆底元素（第一个数组元素和当前最后一个数组元素）；
- 维护减少一个元素的堆；
- 重复2、3步骤直到剩余一个元素。
关键点：
基数排序
思想
何为基数？进位计数制中数码的个数，比如10进制就是10，16进制就是16。
基于数位上的数字键大小进行排序，经多轮“收集”“分配”后完成排序。比如对于三位数排序，首先看百位，然后看十位，最后看个位。
排序过程
基于数码创建容器，10进制就创建10个容器，对应0～9这十个数码
低位优先法：从数字的低位开始到高位
- 分配：从左到右遍历数组，按照关键字对应的数位数码分配进容器
- 收集：按照容器顺序依次收集，如此当前数位有序
- 按照下一个数位，重复1、2过程
时间复杂度：O（k*n），k是最大数的位数，n是数组长度
空间复杂度：O（m+n），m是开辟的容器大小，n是数组大小