在选择排序中，降序数组的性能要比升序数组快。为什么？
提问于 2020-09-13 06:54:09
我在C studio中使用排序数组(升序)和未排序数组(下降顺序)运行选择排序算法。其结果是，未排序数组的性能要比较大大小的排序数组的性能要快。
我觉得这很荒谬。选择排序不是总是花费恒定的时间取决于数组大小吗？这是为什么？？
这是选择排序。我用100,000到1,000,000做了这个。我每跑一次就增加10万。
int main() {
int array[1000000]; //1,000,000
int i = 100000; //100,000
int n = 100000; //100,000
for (int k = 0; k < 10; ++k) {
insert_ascending(array, n); //stuff elements in ascending order
//time check
sort(array, n);
insert_decending(array, n); //stuff elements in descending order
//time check
sort(array, n);
n += i;
}
}
void selectionSort(int *list, const int n)
{
int i, j, indexMin, temp;
for (i = 0; i < n - 1; i++)
{
indexMin = i;
for (j = i + 1; j < n; j++)
{
if (list[j] < list[indexMin])
{
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-09-13 08:55:35
这是我的0.02欧元。
在GCC上，我可以看到4%的速度差倾向于下行数组而不是升序数组。我的假设是它是由
if (list[j] < list[indexMin]) {
indexMin = j;
}被编译成
...
jge .L4
mov eax, DWORD PTR [rbp-8]
mov DWORD PTR [rbp-12], eax
.L4:
add DWORD PTR [rbp-8], 1也就是说，它不是分支预测失败--对于上升情况，jge 总是分支，而对于降序情况，则从不分支。接受分支的jge比实际更新缓存中的索引变量花费更多的周期。
当然，如果您在启用优化的情况下编译，升序代码将获胜。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/63872148
复制相关文章
腾讯云开发者
