using namespace std;
int threshold;
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
int partition(int R[], int m, int n) {
int K = R[m];
int L = m + 1;
int G = n;
while (L <= G) {
while (L <= G && R[L] <= K) L++;
while (R[G] > K) G--;
if (L < G) {
swap(R[L], R[G]);
L++;
G--;
}
}
swap(R[m], R[G]);
return G;
}
void shiftDown(int R[], int n, int i) {
while (true) {
int left = 2 i + 1;
int right = 2 i + 2;
int maxchd = i;
if (left < n && R[left] > R[maxchd])
maxchd = left;
if (right < n && R[right] > R[maxchd])
maxchd = right;
if (maxchd == i) break;
swap(R[i], R[maxchd]);
i = maxchd;
}
}
void buildHeap(int R[], int n) {
for (int i = (n - 1) / 2; i >= 0; i--)
shiftDown(R, n, i);
}
void HeapSort(int R[], int n) {
buildHeap(R, n);
cout << "Heap:";
for (int i = 0; i < n; i++)
cout << R[i] << " ";
cout << endl;
for (int i = n - 1; i > 0; i--) {
swap(R[0], R[i]);
shiftDown(R, i, 0);
}
}
void insertSort(int R[], int n) {
for (int i = 1; i < n; i++) {
int temp = R[i];
int j = i - 1;
while (j >= 0 && R[j] > temp) {
R[j + 1] = R[j];
j--;
}
R[j + 1] = temp;
}
}
void QuickSort(int R[], int m, int n, int depth, int depth2) {
if (m >= n) return;
if (depth > depth2) {
int length = n - m + 1;
HeapSort(R + m, length);
return;
}
if (n - m + 1 > threshold) {
int p = partition(R, m, n);
QuickSort(R, m, p - 1, depth + 1, depth2);
QuickSort(R, p + 1, n, depth + 1, depth2);
}
}
void sort(int R[], int n) {
if (n == 0) return;
int depth2 = floor(2 * log(n) / log(2));
cout << "depth_limit:" << depth2 << endl;
QuickSort(R, 0, n - 1, 1, depth2);
cout << "Intermediate:";
for (int i = 0; i < n; i++)
cout << R[i] << " ";
cout << endl;
insertSort(R, n);
}
int main() {
int n;
scanf("%d %d", &n, &threshold);
int* a = new int[n];
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
sort(a, n);
printf("Final:");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
delete[] a;
return 0;
}
输入样例1:
10 2
10 9 8 7 6 5 4 3 2 1
输出样例1:
depth_limit:6
Heap:7 6 5 4
Intermediate:1 2 3 4 5 6 7 8 9 10
Final:1 2 3 4 5 6 7 8 9 10
输入样例2:
60 2
66 61 92 22 50 80 39 2 25 60 49 17 37 19 24 57 40 82 11 52 45 0 33 78 32 25 19 42 92 50 39 87 74 87 56 79 63 63 80 83 50 3 87 2 91 77 87 10 59 23 25 6 49 85 9 95 60 16 28 1
输出样例2:
depth_limit:11
Heap:24 19 23 19 17 22
Intermediate:1 0 2 2 3 6 10 9 11 16 17 19 19 22 23 24 25 25 25 28 32 33 37 39 39 42 40 45 49 49 50 50 50 52 56 57 59 60 60 61 63 63 66 77 74 78 79 80 80 82 83 85 87 87 87 87 91 92 92 95
Final:0 1 2 2 3 6 9 10 11 16 17 19 19 22 23 24 25 25 25 28 32 33 37 39 39 40 42 45 49 49 50 50 50 52 56 57 59 60 60 61 63 63 66 74 77 78 79 80 80 82 83 85 87 87 87 87 91 92 92 95
代码长度限制
16 KB
时间限制
100 ms
内存限制
64 MB
C++ STL是Standard Template Library的简称,即标准模板库。简单来说,STL将常用的数据结构与算法进行了封装,用户需要时可以直接调用,不用重新开发。排序算法sort( )是STL包含的一个重要算法。
STL中的sort()函数基于快速排序算法实现,众所众知,快速排序是目前已知平均情况下最快的排序算法,被IEEE评选为20世纪十大算法之一,但其最坏情况下时间复杂度会退化为O(n
2
)。STL中的sort()对传统快速排序做了巧妙的改进,使其最坏情况下时间复杂度也能维持在O(nlogn),它是如何实现的呢?
(1)快速排序算法最坏情况下时间复杂度退化为O(n
2
)的主要原因是,每次划分(Partition)操作时,都分在子数组的最边上,导致递归深度恶化为O(n)层。而STL的sort()在Partition操作有恶化倾向时,能够自我侦测,转而改为堆排序,使效率维持在堆排序的O(nlogn)。其具体方法是:侦测快速排序的递归深度,当递归深度达到⌊2log
2
n⌋=O(logn)层时,强行停止递归,转而对当前处理的子数组进行堆排序。
(2)此外,传统的快速排序在数据量很小时,为极小的子数组产生许多的递归调用,得不偿失。为此,STL的sort()进行了优化,在小数据量的情况下改用插入排序。具体做法是:当递归处理的子数组长度(子数组包含的元素个数)小于等于某个阈值threshold 时,停止处理并退出本层递归,使当前子数组停留在“接近排序但尚未完成”的状态,最后待所有递归都退出后,再对整个序列进行一次插入排序(注意不是对当前处理的子数组进行插入排序,而是在快速排序的所有递归完全退出后,对整个数组统一进行一次插入排序)。实验表明,此种策略有着良好的效率,因为插入排序在面对“接近有序”的序列时拥有良好的性能。输入格式:
输入第一行为2个正整数n和threshold,n为待排序的元素个数,不超过50000,threshold为改用插入排序的阈值,不超过20,含义如上所述。第二行为n个空格间隔的整数。本题中读入数据的操作无需你来实现,而由框架程序完成。
输出格式:
输出第一行为以depth_limit:开头的整数,表示转为堆排序的递归深度,即⌊2log
2
n⌋。从第二行开始,输出对某子数组转为堆排序后,该子数组初始建堆的结果,每个元素后一个空格,每个堆占一行,以Heap:开头。注意,可能不止一个堆。接下来下一行,输出n个整数,每个整数后一个空格,为快速排序所有递归退出后,插入排序执行前的数组元素,以Intermediate:开头。最后一行为n整数,每个整数后一个空格,表示排序后的数组,以Final:开头(最后一行由框架程序完成,无需你来输出)。
帮我改代码,符合题意和输出样例
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
感谢您使用通义灵码~