排序算法
当前没有测试数据。
排序算法
验收要求：点击下面的题目完成程序，15分钟内完成一个排序的实现，需要验收排序的思路和时间复杂度
计数排序(countSort)
1、 需要额外的空间来存储计数器
2、 根据元素的值直接定位其在排序后数组中的位置
3、 稳定的排序
4、 适用于数据范围不大的整数排序
实现思想：统计每个元素出现的次数，存储在计数器数组中。根据计数器数组重新排列所有元素，将所有元素放在其正确的位置上。
// 计数排序
void count_sort(vector<int>& arr,int n){
//求数组中的最大值:max_element
int max_v = *max_element(arr.begin(),arr.end());
vector<int> count(max_v+1,0); //计数数组
vector<int> output(n); //输出数组
// 统计每一个元素输出的数量
for(int i=0;i<n;i++){
count[arr[i]]++;
}
// 累积计数确定每个元素的位置
for(int i=1;i<=max_v;i++){
count[i] += count[i-1];
}
// 倒叙输出
for(int i=n-1;i>=0;i--){
output[count[arr[i]]-1] = arr[i];
count[arr[i]]--;
}
// 将输出的数组放回原数组
for(int i=0;i<n;i++){
arr[i] = output[i];
}
}
实现过程：
假设我们有一个待排序的数组 A：
A = [4, 2, 2, 8, 3, 3, 1]
1. 找到数组中的最大值
我们需要找到数组 A 中的最大值，以确定计数数组的长度。在这个例子中，最大值是 8。
2. 创建计数数组
创建一个长度为 9（最大值 8 + 1）的计数数组 count，并初始化为全零：
count = [0, 0, 0, 0, 0, 0, 0, 0, 0]
3. 统计元素出现次数
遍历输入数组 A，统计每个元素出现的次数并存储在 count 数组中：
A = [4, 2, 2, 8, 3, 3, 1]
count[4] += 1 -> count = [0, 0, 0, 0, 1, 0, 0, 0, 0]
count[2] += 1 -> count = [0, 0, 1, 0, 1, 0, 0, 0, 0]
count[2] += 1 -> count = [0, 0, 2, 0, 1, 0, 0, 0, 0]
count[8] += 1 -> count = [0, 0, 2, 0, 1, 0, 0, 0, 1]
count[3] += 1 -> count = [0, 0, 2, 1, 1, 0, 0, 0, 1]
count[3] += 1 -> count = [0, 0, 2, 2, 1, 0, 0, 0, 1]
count[1] += 1 -> count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
4. 计算累计计数
将 count 数组转换为累计计数数组。每个位置 i 的值表示小于或等于 i 的元素个数：
count = [0, 1, 3, 5, 6, 6, 6, 6, 7]
5. 生成排序后的数组
创建一个输出数组 B，长度与输入数组 A 相同，初始化为全零。然后反向遍历输入数组 A，根据累计计数数组 count 确定每个元素在输出数组 B 中的位置，并在 count 中递减相应位置的计数：
B = [0, 0, 0, 0, 0, 0, 0]
遍历 A = [4, 2, 2, 8, 3, 3, 1]：
A[6] = 1 -> count[1] -= 1 -> count = [0, 0, 3, 5, 6, 6, 6, 6, 7]
B[0] = 1 -> B = [1, 0, 0, 0, 0, 0, 0]
A[5] = 3 -> count[3] -= 1 -> count = [0, 0, 3, 4, 6, 6, 6, 6, 7]
B[4] = 3 -> B = [1, 0, 0, 0, 3, 0, 0]
A[4] = 3 -> count[3] -= 1 -> count = [0, 0, 3, 3, 6, 6, 6, 6, 7]
B[3] = 3 -> B = [1, 0, 0, 3, 3, 0, 0]
A[3] = 8 -> count[8] -= 1 -> count = [0, 0, 3, 3, 6, 6, 6, 6, 6]
B[6] = 8 -> B = [1, 0, 0, 3, 3, 0, 8]
A[2] = 2 -> count[2] -= 1 -> count = [0, 0, 2, 3, 6, 6, 6, 6, 6]
B[2] = 2 -> B = [1, 0, 2, 3, 3, 0, 8]
A[1] = 2 -> count[2] -= 1 -> count = [0, 0, 1, 3, 6, 6, 6, 6, 6]
B[1] = 2 -> B = [1, 2, 2, 3, 3, 0, 8]
A[0] = 4 -> count[4] -= 1 -> count = [0, 0, 1, 3, 5, 6, 6, 6, 6]
B[5] = 4 -> B = [1, 2, 2, 3, 3, 4, 8]
最终得到排序后的数组 B：
B = [1, 2, 2, 3, 3, 4, 8]
时间复杂度分析
- 统计元素出现次数：时间复杂度
O(n)，遍历输入数组一次。 - 计算累计计数：时间复杂度
O(k)，遍历计数数组一次。 - 生成排序后的数组：时间复杂度
O(n)，反向遍历输入数组一次，并填充输出数组。
综合起来，计数排序的总时间复杂度为 O(n + k)，其中 n 是输入数组的长度，k 是输入数组中最大元素的值。
基数排序（radixSort）
基数排序：是一种专门为处理数字序列而设计的排序算法。它的灵感来源于人类对数字的处理方式，类似于将数字按照位数逐位进行排序，实现了对整数的高效排序。
稳定性： 基数排序是一种稳定的排序算法，保持相等元素的相对顺序。
适应性： 对于位数相同的数字序列，基数排序表现出良好的适应性，排序效率较高。
非比较性： 基数排序不涉及元素之间的比较操作，减少了算法的复杂度，对于一些特定范围的数字排序更为高效。
基本原理： 基数排序的核心思想是将整数按照位数逐个进行排序，最终形成有序序列。具体步骤包括：
1 按位分配： 从低位到高位，依次按照每一位的数值进行分配，形成桶。
2 按位收集： 将桶中的元素按照顺序收集，形成新的序列。
3 迭代重复： 重复以上两步，直到整个数字序列有序。
void radixSort(){
// 1、求数组中最大值的位数
int max_bit = to_string(*max_element(data+1,data+1+n)).length();
// 2、创建临时数组
int* temp = new int[n+1];
// 3、创建计数器数组
int* count = new int[10]; // 0 ~ 9
// 进行最大位次排序
int radix = 1; //表示个位
for(int i=1;i<=max_bit;i++){
for(int j=0;j<10;j++) count[j] = 0; // 每次分配前清空计数器
for(int j=1;j<=n;j++){
// 求当前在哪个计数器位置
int k = (data[j] / radix) % 10;
count[k]++;
}
for(int j=1;j<10;j++) count[j] += count[j-1];
for(int j=n;j>=1;j--){
// 将每一个数，按照顺序放入临时数组
int k = (data[j] / radix) % 10;
temp[count[k]]= data[j];
count[k]--;
}
// 将临时数组取出
for(int j=1;j<=n;j++){
data[j] = temp[j];
}
// 将位数*10，开始下一位的排序
radix *= 10;
}
delete[] temp;
delete[] count;
}
假设要排序下列数字：2 13 8 3 28
1、先求出最大值的位数：28 2位
先按个位计数排序:
依次取出桶内的数， 得到新数组：2 3 8 13 28
归并排序
1、 将数组不断二分，直到每部分只剩一个元素
2、 将两个有序部分合并为一个有序部分
3、 稳定的排序
4、 平均时间复杂度为 O(n logn)
5、 需要额外的存储空间
实现思想：将数组从中间分成两部分，分别对每部分进行归并排序。在对每部分排序后，将两个有序部分合并为一个有序数组。
核心代码：
// 归并排序函数，排序数组arr从索引l到r的部分
void mergeSort(int arr[], int l, int r) {
// 如果左索引大于或等于右索引，说明数组已经不可分，返回
if (l >= r) return;
// 找到中间索引
int mid = (l + r) / 2;
// 递归地排序左半部分
mergeSort(arr, l, mid);
// 递归地排序右半部分
mergeSort(arr, mid + 1, r);
// 创建临时数组，用于存储合并后的结果
int i = l, j = mid + 1, k = 0;
int* temp = new int[r - l + 1];
// 合并两个有序的子数组
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++]; // 将左子数组的当前元素复制到temp
} else {
temp[k++] = arr[j++]; // 将右子数组的当前元素复制到temp
}
}
// 如果左子数组还有剩余元素，继续复制到temp
while (i <= mid) temp[k++] = arr[i++];
// 如果右子数组还有剩余元素，继续复制到temp
while (j <= r) temp[k++] = arr[j++];
// 将合并后的结果复制回原数组的对应位置
memcpy(arr + l, temp, sizeof(int) * (r - l + 1));
// 释放临时数组的内存
delete[] temp;
}
归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的稳定排序算法。它通过将大问题分解为更小的子问题，递归地解决这些子问题，然后将它们合并成一个有序的解决方案。归并排序的时间复杂度稳定且较好，因此广泛应用于排序问题。
归并排序的步骤
-
分解（Divide）：
- 将数组分解为两个子数组，直到每个子数组只有一个元素（即，子数组的大小为 1）。
-
合并（Merge）：
- 递归地合并这些子数组，将两个已排序的子数组合并成一个有序的数组。
归并排序的时间复杂度
归并排序的时间复杂度主要由两个部分组成：分解和合并。
1. 分解（Divide）
在每一步，将数组分解为两个子数组。分解操作的时间复杂度为 (O(log n))，因为每次分解都会将数组的大小减少一半，递归深度为 (log n)。
2. 合并（Merge）
在每一层递归中，需要将所有的子数组合并。每次合并的操作时间复杂度为 (O(n))，因为每个元素都需要被比较和合并一次。对于每一层递归，需要进行 (O(n)) 次操作。
总时间复杂度
由于递归深度为 (log n)，每一层的合并操作时间复杂度为 (O(n))。因此，总的时间复杂度为： [ O(n log n) ]
分析
假设有一个数组：[38, 27, 43, 3, 9, 82, 10]，我们用归并排序进行排序。
-
分解阶段：
- 将数组分解为：[38, 27, 43, 3] 和 [9, 82, 10]
- 继续分解：
- [38, 27, 43, 3] 分解为：[38, 27] 和 [43, 3]
- [38, 27] 分解为：[38] 和 [27]
- [43, 3] 分解为：[43] 和 [3]
- [9, 82, 10] 分解为：[9] 和 [82, 10]
- [82, 10] 分解为：[82] 和 [10]
- [38, 27, 43, 3] 分解为：[38, 27] 和 [43, 3]
-
合并阶段：
- 合并子数组：
- [38] 和 [27] 合并为：[27, 38]
- [43] 和 [3] 合并为：[3, 43]
- [82] 和 [10] 合并为：[10, 82]
- 合并结果：
- [27, 38] 和 [3, 43] 合并为：[3, 27, 38, 43]
- [9] 和 [10, 82] 合并为：[9, 10, 82]
- 最终合并：
- [3, 27, 38, 43] 和 [9, 10, 82] 合并为：[3, 9, 10, 27, 38, 43, 82]
- 合并子数组：
总结
归并排序的特点包括：
- 时间复杂度：在最坏、最好和平均情况下均为 (O(n \log n))，表现稳定。
- 空间复杂度：归并排序需要额外的空间来存储临时数组，因此空间复杂度为 (O(n))。
- 稳定性：归并排序是一个稳定的排序算法，即相同值的元素在排序后保持其原有的相对位置。
相关
在以下作业中: