在选择排序中，降序数组的性能比升序数组快。为什么？

Question

I 运行 Cvisual studio中排序数组（升序）和未排序数组（降序）的选择排序算法。结果是未排序数组的性能比大尺寸排序数组之一更快。

我觉得很可笑。选择排序不是总是需要常数时间取决于数组大小吗？这是为什么？？

这是选择排序。我运行 n = 100,000 到 1,000,000。每运行.

我增加了 100,000

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;
    } 
}

Answer 1

这是我的 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 always 分支，对于下降情况它 never 分支。 jge 采用分支确实比实际更新缓存中的索引变量需要更多的周期。

当然，如果您在启用优化的情况下进行编译，则升序代码胜出。

在选择排序中，降序数组的性能比升序数组快。为什么？

In selection sort, descending array's performance is faster than ascending array. why?

c

algorithm

selection-sort