去选择排序比气泡排序慢？[关闭]

Question

结束了。 这个问题是 不可复制或由错别字造成的。. 目前不接受回答。

---

想改进这个问题？ 请更新问题，使之成为 题外话 为Stack Overflow。

已关闭 上月.

改进这个问题

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

这是我在Python中实现的气泡和插入排序。

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 Benchmark):

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中实现同样的算法时，我的选择排序实现得到的数据更糟糕。

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中它的表现和预期一样？(比气泡排序快)。

我已经尝试过在 Go 中把 for 循环改成 range，但时间上还是一样。也许有人知道这里发生了什么？

非常感谢

Answer 1

用一组固定的数字来对一个排序算法进行基准测试，首先是没有意义的，因为排序所涉及的步骤数不仅取决于算法，还取决于具体的输入。一种算法可能用一种输入更快，而另一种则用不同的输入。

忽略这一点，你的 Python 代码甚至没有测量排序一个特定数组的性能。相反，它只是取一个单一的全局数组，复制它 (entry.copy())在做基准测试之前(即在多次运行排序函数之前)，准确地在原地进行一次排序，从那时起，每一次 "排序 "都是在已经排序的数组上进行的。因此，你的 Python 代码测量的是对原始输入的一次排序和对已经排序的输入的多次排序。

与此相反的是，Go 的实现在每次运行排序函数时都从一个新的数组开始。因此，你的 Go 代码测量的是原始输入的多次排序。

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