java - 为什么我的冒泡排序对反转数据的排序速度远快于随机数据或具有多个相同值的数据？

Question

因此据我了解，冒泡排序在对反向数据进行排序时应该比任何其他类型都慢。我目前正在研究排序算法并实现了我自己的 Bubble 算法，它在对随机数据和具有多个值的数据进行排序时又慢了一半，这些值与反向数据相同(使用 java 的 System.nanoTime())。我对这个结果很感兴趣，但我无法解释。

这是我的算法代码:

public static void bubbleSort(int[] arr)
{
    //Will only check elements which haven't been sorted yet. checks and newChecks will handle this.
     int checks = arr.length, newChecks;

     //Continues comparing elements until a swap does not occur, indicating a sorted list.
     do
     {
        newChecks = 0;

        for (int i = 1; i < checks; i++)
        {
            if (arr[i - 1] > arr[i])
             {
                swapElements(arr, i - 1, i);

                //Gives newChecks the position of the element just switched
            newChecks = i;
            }
        }

        //The last switched element indicates after which point the array is sorted. Thus the assigning of newChecks to checks.
        checks = newChecks;
    } while (checks > 0);
}

Answer 1

我怀疑这是因为 branch prediction .

当你的数据以相反的顺序排序时，比较的结果 if (arr[i - 1] > arr[i]) 最初总是为真，但随着排序的进行这样，在数据列表的末尾将会有越来越多的正确排序的项目。在数据的排序部分，这种比较总是返回false。

因此，一个简单的分支预测启发式(即假设每次比较的结果与前一次比较的结果相同)每次都会产生正确的结果，除了每个循环两次——一次在数据的开头，一次是在未排序的数据与已排序的数据相遇的地方。

通过提前预测这种比较的结果，您的处理器可以使用其管道同时处理循环的更多迭代，并比随机排序数据更早地完成排序。

( You should still avoid using bubble sort, however. )