直线选择排序中的比较数

Question

我在一本皮尔逊的书里发现了这个问题。

How many comparisons are needed to sort an array of length 5 
(whose element are already in opposite order) using straight selection sort?
a. 5
b. 20
c. 4
d. 10

给出了的正确答案是b. 20。

但我想应该是第10天

请解释一下答案是20。

我还搜索了直选排序，但我只得到结果的选择排序。我还找到了术语交换选择的排序。到目前为止，我只听说过选择排序，所以请给出一些关于Exchange和直选排序的区别的意见。

提前谢谢。

Answer 1

10应该是正确的答案。

来自维基百科

与其他排序算法相比，选择排序并不难分析，因为没有一个循环依赖于数组中的数据。选择最低的元素需要扫描所有n元素(这需要进行n − 1比较)，然后将其交换到第一个位置。要找到下一个最低的元素，需要扫描其余的n − 1元素等等，以便进行(n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n^2)比较。

因此，对于5个元素，它将是5*4/2 = 20/2 = 10 (注意“没有一个循环依赖于数组中的数据”，所以按降序排列的事实并不在比较的数量中起作用)。

我假设的是直接选择和交换选择排序之间的区别并不会影响比较的数量。

交换(交换)元素和直接转换元素(或者使用不需要向上移动的数据结构，例如链接列表)是有意义的。请注意，我们只进行比较以找到我们想要的元素，没有(元素)比较涉及交换、移位或链接列表插入。

维基百科使用exchanging作为默认算法，并在“变体”下面列出了备选方案。

Answer 2

(n*(n-1))/2给出了no。用于选择排序的比较

Answer 3

用可视化澄清了它

单击此处

或

你可以简单地放置一个柜台来追踪“否”。比较和不。交换内部选择排序。JavaScript代码片段如下所示。

var arr = [10, 6, 4, 9, 13];
let size = arr.length;
let swap = 0;
let comp = 0;

for(let i = 0; i < (size-1); i++)
{
    var min = i;
    for(let j = i+1; j < size; j++ )
    {
        if(arr[j] < arr[min]){ min = j;}
        comp++;
    }
    [arr[i], arr[min]] = [arr[min], arr[i]];
    if(min!=i) { swap++; }
}

console.log("Total Comparison: " + comp);
console.log("Total Swapping: " + swap);

不是的。选择排序= N*(N-1))/2的比较