有效的选择排序算法？

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 循环每次迭代结束时的选择排序一样，您将正确放置另一个元素，但它的运行速度比真正的选择排序慢，因为您进行的交换比所需的要多得多.

Answer 2

selection sort

，但交换应该发生在嵌套循环之外。在最里面的循环中，您应该只保存剩下要排序的最小元素的索引（如果在我第一次编辑答案期间放置，我误读了您）。

selection sort

和

bubble sort

之间的主要区别主要（但不完全）在于它们的嵌套循环。事实上，

selection sort

尝试在其嵌套循环中找到i之后的最小元素，然后将其放置在第i个位置。这样，在外循环的每次迭代中，可以保证第 i 个元素对应于剩下要排序的元素中最小的元素（从 i 到 n-1）。

public void selectionSort(int[] arr){
    int temp, min;
    
    // At every iteration, the outer loop checks whether the i-th element is already at the right place,
    // i.e. being the smallest value among the ones that follow it
    for (int i = 0; i < arr.length-1; i++) {

        //Assuming that the element in position i is the smallest among the ones left to sort
        min = i;

        //At every iteration of the outer loop, the innermost loop checks if there's a smaller value than the one in position i
        for (int j = i + 1; j < arr.length; j++) {

            //If a smaller value than the min-th element is found then j is stored as the current smallest index
            if (arr[min] > arr[j]) {
                min = j;
            }
        }

        //Swapping the smallest element found with the one in position i.
        //If min is still equal to i then no actual swap happens
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

另一方面，

bubble sort

算法实现了相同的效果，但它不是从左到右遍历，而是从右到左迭代，并携带它遇到的新的最小元素。

public void bubbleSort(int[] vet) {
    int temp;

    //At every iteration, the outermost loop checks if there are any elements after i which are smaller than it
    for (int i = 0; i < vet.length - 1; i++) {
        // The innermost loop starts from the right bound 'till the i index.
        // Every time this loop finds in [j-1] a bigger element than the one in [j], 
        // then these two are swapped to carry along the smaller element in position j during the traverse.
        // Instead if the element in [j-1] is smaller than the one in [j], 
        // then it leaves them like that and keeps carrying [j-1] along instead of [j].
        for (int j = vet.length - 1; j >= i + 1; j--) {
            if (vet[j] < (vet[j - 1])) {
                temp = vet[j];
                vet[j] = vet[j - 1];
                vet[j - 1] = temp;
            }
        }
    }
}

Answer 3

Answer 4

这是更正后的版本：

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

}

此版本正确遵循选择排序过程。识别此过程中的最小部分并每次迭代仅切换一次。