有效的选择排序算法？

Question

我写了下面的方法，它试图使用 selection sort 对数组进行排序：

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

public final class SelectionSort {

    public static void sortAsc(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++)
            swap(arr, i, getMinIndex(arr, i));
    }

    private static int getMinIndex(int[] arr, int i) {
        int minIndex = i;

        for (; i < arr.length; i++)
            if (arr[i] < arr[minIndex])
                minIndex = i;

        return minIndex;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

Answer 2

您的实现绝对类似于 selection sort，但交换应该发生在嵌套循环之外。在最内层的循环中，您应该只保存剩下要排序的元素中最小元素的索引（如果在我第一次编辑答案时放置，我误会了您）。

selection sort 和 bubble sort 之间的主要区别主要但不完全在于它们的嵌套循环。事实上，selection sort 试图在其嵌套循环中找到 i 之后的最小元素，然后将其放置在 i-th 位置。这样，在外循环的每次迭代中，都保证 i-th 元素对应于剩余要排序的元素中的最小元素（从 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

你的算法实际上是交换排序.

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

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

有效的选择排序算法？

Valid selection sort algorithm?

java

sorting

selection-sort