java - 有效的选择排序算法？

Question

我编写了以下使用选择排序对数组进行排序的方法:

public T[] selection(T[] arr)
{
   T temp, min;
   for(int i = 0; i < arr.length-1; i++)
   {
      for(int j = i + 1; j < arr.length; j++)
      {
         min = arr[i];
         if(min.compareTo(arr[j]) > 0)
         {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
         }
      }
   return arr;
}

但是，我无法区分我的算法和冒泡排序。我的排序方法是否通过选择排序方法？

Answer 1

你的算法实际上是一种叫做交换排序的东西。

在选择排序中，您对数组进行遍历以找到最小的元素。每当发现一个元素小于迄今为止发现的最小元素时，您就记下它的位置，但不要移动或交换它。只有在扫描完数组元素后，您才会将找到的项目交换到数组中较早的位置。这意味着您始终最多进行总共 n - 1 次交换，外循环每次迭代一次。

这与您代码中的内容不符，因为您在外部 i 循环的每次迭代中执行多次交换。您拥有的算法称为交换排序。这是一种合法的排序算法，就像外部 i 循环每次迭代结束时的选择排序一样，您将正确放置另一个元素，但它的运行速度比真正的选择排序慢，因为您进行的交换比所需的要多得多.