1、快排优化 递归式的快速排序在数据量很小时,函数调用等额外开销会显得比较大,此时换用选择排序等简单排序方式会更有效率。现以7为界,数据量为7个及以下时改用选择排序,请在下面的快速排序代码的适当位置插入这段优化代码。 #include <cstdlib> #include <ctime> void qsort(int* a, int l, int r) { if(l >= r)return; int i = l; int j = r; int x = a[l]; while(i < j) { while(i < j && x <= a[j])--j; a[i] = a[j]; while(i < j && a[i] <= x)++i; a[j] = a[i]; } a[i] = x; qsort(a, l, i - 1); qsort(a, i + 1, r); } int main() { srand(time(0)); const int N = 10000; int a[N]; for(int i = 0; i < N; ++i) { a[i] = rand() % 1000; } qsort(a, 0, N - 1); return 0; }
时间: 2024-04-12 13:29:52 浏览: 19
要在上述的快速排序代码中插入优化代码,可以在递归基准条件的判断语句之前添加一个判断,当数据量小于等于7时,调用选择排序进行排序。
下面是插入优化代码后的修改版快速排序代码:
```cpp
#include <cstdlib>
#include <ctime>
void selectionSort(int* a, int l, int r)
{
for (int i = l; i <= r; ++i)
{
int minIndex = i;
for (int j = i + 1; j <= r; ++j)
{
if (a[j] < a[minIndex])
{
minIndex = j;
}
}
std::swap(a[i], a[minIndex]);
}
}
void qsort(int* a, int l, int r)
{
if (l >= r) return;
if (r - l + 1 <= 7)
{
selectionSort(a, l, r);
return;
}
int i = l;
int j = r;
int x = a[l];
while (i < j)
{
while (i < j && x <= a[j]) --j;
a[i] = a[j];
while (i < j && a[i] <= x) ++i;
a[j] = a[i];
}
a[i] = x;
qsort(a, l, i - 1);
qsort(a, i + 1, r);
}
int main()
{
srand(time(0));
const int N = 10000;
int a[N];
for (int i = 0; i < N; ++i)
{
a[i] = rand() % 1000;
}
qsort(a, 0, N - 1);
return 0;
}
```