这是什么算法？

Question

我似乎无法理解这个特定的算法。它似乎是一种冒泡排序，但不是传统意义上的。它是什么？

public static void main(String[] args) 
{
    double[] a = {0.75, 0.5, 1.0};                          
    sort(a);

    for (int i = 0; i < a.length; i++)
        System.out.println(a[i]);
}

public static void sort(double[] tal)
{
    double p = 0;
    int k = 0;

    for (int i = 0; i < tal.length - 1; i++)
    {
        k = i;
        for (int j = i + 1; j < tal.length; j++)
        {
            if (tal[j] < tal[k])
                k = j;
        }

        p = tal[i];
        tal[i] = tal[k];
        tal[k] = p;
    }
}

- user3071133

Answer 1

一开始我错误地认为这是一个插入排序。事实上，它是一个选择排序（参见维基百科）。

- Elliott Frisch

---

动画很好，但 OP 算法不是插入排序。 - Henry

艾略特，你是如何制作那个动画的？ - committedandroider

@committedandroider 这是来自维基百科链接文章的内容。但这是一个相当标准的动画gif图像。通常我使用gimp和gifsicle制作全新的动画图像。 - Elliott Frisch

Answer 2

这是一种选择排序算法。内部循环在剩余元素中找到最小值并与未排序范围的第一个元素互换。

- Henry

---

内联交换被认为比使用单独的交换方法要快一些。 - WonderWorld

你能详细解释一下所谓的低效吗？该代码使用一个本地变量来存储最小元素的索引，并且仅为下一个元素执行一次交换。我不确定你如何显着提高它的效率。 - Bernhard Barker

@Dukeling 经过仔细检查，你是对的，我忽略了交换不是在内部循环中发生的。 - Henry

Answer 3

这是选择排序。插入排序使用一个for循环和一个while循环。

- WonderWorld