选择排序比气泡排序慢吗？

Question

我在做一些编码来练习算法，我发现了一些奇怪的事情，当我用Python实现简单的分类器时，随机输入99个元素，选择排序比冒泡排序快：

这是我在Python中的bubble和insert排序实现：

from typing import List, TypeVar

T = TypeVar('T')


def bubble_sort(elems: List[T]) -> List[T]:
    """Sorts a list using the bubble sort algorithm"""
    if not elems:
        return elems

    for mx in range(len(elems), 0, -1):
        for idx in range(1, mx):
            if elems[idx - 1] > elems[idx]:
                elems[idx - 1], elems[idx] = elems[idx], elems[idx - 1]

    return elems


def selection_sort(elems: List[T]) -> List[T]:
    """Sorts a list using the selection sort algorithm"""
    if not elems:
        return elems
    n = len(elems)
    for i in range(0, n):
        smidx = i
        for j in range(i + 1, n):
            if elems[smidx] > elems[j]:
                smidx = j
        elems[i], elems[smidx] = elems[smidx], elems[i]
    return elems

当然，测试（使用PyTest和PyTest基准测试）：

import random
from sorting import *

entry = [48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26]

expected = list(range(1, 100))

def test_bubble_sort(benchmark):
    x = entry.copy()
    assert benchmark(bubble_sort, x) == expected

def test_select_sort(benchmark):
    x = entry.copy()
    assert benchmark(selection_sort, x) == expected

现在，当我尝试在Go中实现相同的算法时，我的select sort实现得到了更糟糕的结果：

package algo

func BubbleSort(elems []int) []int {
    if elems == nil {
        return nil
    }
    for mx := len(elems) - 1; mx >= 0; mx-- {
        for idx := 1; idx <= mx; idx++ {
            if elems[idx-1] > elems[idx] {
                elems[idx-1], elems[idx] = elems[idx], elems[idx-1]
            }
        }
    }
    return elems
}

func Selection(elems []int) []int {
    if elems == nil {
        return nil
    }
    n := len(elems) - 1
    for i := 0; i <= n; i++ {
        maxIdx := i
        for j := i + 1; j <= n; j++ {
            if elems[j] < elems[maxIdx] {
                maxIdx = j
            }
        }
        elems[i], elems[maxIdx] = elems[maxIdx], elems[i]
    }
    return elems
}

以下是测试：

func BenchmarkBubbleSort(b *testing.B) {
    for n := 0; n < b.N; n++ {
        var longSeq = []int{48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26}
        BubbleSort(longSeq)
    }
}

func BenchmarkSelectionSort(b *testing.B) {
    for n := 0; n < b.N; n++ {
        var longSeq = []int{48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26}
        Selection(longSeq)
    }
}

是的，我知道在最佳情况下，选择排序可能比冒泡排序更糟糕（我不认为这是基于混合输入的情况），但是为什么，如果是这样的话，为什么在Python中它的行为与预期的一样呢？（比气泡排序更快）

我已经尝试将for循环更改为Go中的range，但时间是相似的。也许有人知道这里发生了什么

非常感谢

Answer 1

首先，用一组固定的数字对排序算法进行基准测试毫无意义，因为排序所涉及的步骤数不仅取决于算法，还取决于特定的输入。使用一种输入时，一种算法可能更快，而使用另一种输入时，另一种算法可能更快

忽略这一点，您的Python代码甚至不会度量对特定数组进行排序的性能。相反，它采用单个全局数组，在执行基准测试之前（即在多次运行排序函数之前）复制它（entry.copy()），在适当的位置对它进行一次排序，然后在已经排序的数组上执行一次“排序”。因此，Python代码测量原始输入的一个排序和已排序输入的多个排序

与此相反，Go实现从每次运行sort函数的新数组开始。因此，Go代码度量原始输入的许多排序

换句话说：在Python和Go中测量的是完全不同的东西