c++ - 为什么选择排序比自定义排序快？

Question

为什么 selectionSort 比 customSort 快？似乎 customSort 移动值比它必须的更多。但是，selectionSort 有更多的变量赋值，我不确定这是如何影响速度的。

void selectionSort(int array[], int size)
{
    int startScan, minIndex, minValue;
    for (startScan = 0; startScan < (size - 1); startScan++)
    {
        minIndex = startScan;
        minValue = array[startScan];
        for (int index = startScan + 1; index < size; index++)
        {
            if (array[index] < minValue)
            {
                minValue = array[index];
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        array[startScan] = minValue;
    }
}

void customSort(int a[],int n){
    for(int j=0;j<n-1;j++){
        for(int i=j+1;i<n;i++){
            if(a[j]>a[i]){
                a[j]=a[j]^a[i];
                a[i]=a[j]^a[i];
                a[j]=a[j]^a[i];
            }
        }        
    }
}

Answer 1

两种算法都进行 O(n^2) 次比较。 customSort 进行 O(n^2) 次交换，而 selectionSort 进行 O(n) 次交换。但这只能告诉您 n 趋于无穷大时的相对性能。这实际需要多长时间取决于优化器、处理器以及缓存和内存速度。它可以采用任何一种方式，尤其是当 n 为“小”时。

要知道哪个实际上更快，唯一的方法就是测量。这不是怎么想问题的问题。

鉴于您已经确定 selectionSort 在您的情况下更快，我们可以提出一些假设。

因为 selectionSort 只需要两个额外的值，优化器很可能安排将它们保存在寄存器中。它还对缓存非常友好，因为几乎所有内存读取都是顺序的。

与 customSort 相比，它必须从内存中读取两个值。交换发生得更频繁，并且至少需要两次存储到内存中。

如果存储到内存比存储到寄存器慢(这是可能的)，那么 selectionSort 更快也就不足为奇了，即使它 customSort 使用了一个技巧来避免需要临时变量。