Java - 选择排序算法

Question

我对选择排序有一些问题，感到有些困惑。

 int [] arr = {5,4,3,2,1}; // This is my array
    int min = 0;

    for(int i = 0;i<arr.length;i++)
    {
        //Assume first element is min
        min = i;//Selection sort algorithm says that find the minimum in the
                // array, but first element is not minimum.What's point here?
        for(int j = i + 1;j<arr.length;j++)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            System.out.println(arr[i]);//I print the in ascending order 
        }
    }

输出结果为：

4
3
2
1
4
3
2
4
3
4

有什么问题吗？

- snnlankrdsm

Answer 1

选择排序是在循环的每一步中找到最小值。如果没有找到最小值（可能是通过 if 语句），只需在内部循环中简单地交换值。因此，您实际上没有进行排序。

根据您的实现进行更正：

final int[] arr = { 5, 4, 3, 2, 1 }; // This is my array
    int min;
    for (int i = 0; i < arr.length; i++) {
        // Assume first element is min
        min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;

            }
        }
        if (min != i) {
            final int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        System.out.println(arr[i]);// I print the in ascending order
    }

这应该能给你输出：

1
2
3
4
5

- Kent

---

你在每个最小元素处都进行交换 - 这不是冒泡排序，而是选择排序吗？ - corsiKa

公平地说，经过进一步的检查，它并不是冒泡排序，因为它确实总是交换相邻元素。这也不完全是插入排序。这是选择排序的一种独特方法，肯定不同于其他方法，对我来说，它应该有一个类似“选择排序变体”的称号。 - corsiKa

@glowcoder 我认为这是选择排序。选择排序总是假设第一个元素是最小的，然后从剩下的元素中找到最小的。如果找到的最小值的索引不等于原始（第一个）元素的索引，则进行交换。我的做法是每次找到一个新的最小值就进行交换，从而节省了变量 "min" 的空间，但是会进行更多的交换操作。我已经修改了代码，现在应该和教科书上的一模一样了（没有测试，但应该可以正常工作）。 冒泡排序不是这样的，尽管它也会进行交换操作，但是它只交换相邻的两个元素。 - Kent

Answer 2

正确：

public class Test {

public static void main(String args[]){
    int[] arr = {5,4,3,2,1}; // This is my array
    int min = 0;

    for(int i = 0;i<arr.length;i++)
    {
        //Assume first element is min
        min = i;
        for(int j = i + 1;j<arr.length;j++)
        {
            if(arr[j] < arr[min]) { min = j;}
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
        System.out.println(arr[i]);//I print the in ascending order 
    }
}

}

关于min部分：它只是指当前最小值的索引。您继续向下移动数组，直到遇到新的最小值，并将min设置为该索引。所以，5是最小的数字[min = 0]，直到你看到4 [所以现在min = 1]，但然后你将3与存储在4处的内容进行比较[当min = 1时]，然后意识到应该将min = 2....等等。

- varatis

---

仅仅给别人代码来修复他们的作业，而没有任何解释，这样是毫无用处的。即使你是正确的，你也没有帮助他们理解，他们的问题首先不是为了修复代码，而是为了理解算法的某些方面。 - corsiKa

我稍后添加了注释...如果你能等待2分钟就好了。 - varatis

我也不同意知道答案没有用，但这只是个人观点。你见过没有答案解析的练习试卷吗？ - varatis

我看到了你的更改（它们可能需要一些工作，但还可以），但是除非进行编辑注册，否则我无法取消我的反对票。 :( - corsiKa

Answer 3

你的问题似乎在你的评论中

min = i;//Selection sort algorithm says that find the minimum in the
        // array, but first element is not minimum.What's point here?

这样做的目的是你可以假设你正在检查的第一个元素是最低的，只是为了让你有一个起点。毕竟，它可能不是所有元素中的最小值，但在此迭代中你已经检查过的元素中，它是到目前为止最低的！

- corsiKa

Answer 4

你应该先找到最小值，而不是假设第一个元素是最小值

int[] array = {5, 4, 3, 2, 1};
for ( int i = 0; i < array.length; i++ ) {

  //find minimum, starting from index i
  int minIndex = i;
  int min = array[i];
  for ( int j = i + 1; j < array.length; j++ ) {
    if ( array[ j ] < min ) {
      minIndex = j;
      min = array[j];
    }
  }

  // now move the smallest element to the front, and the element at index i to the index of the minimal element
  int temp = array[ i ];
  array[ i ] = min;
  array[ minIndex ] = temp;
}

- Robin

Answer 5

    int[] arr = {5,4,3,2,1};

    for (int i = 0; i < arr.length - 1; i++)
         {
            int index = i;
              for (int j = i + 1; j < arr.length; j++)
                  if (arr[j] < arr[index]) 
                   index = j;

            int smallerNumber = arr[index];  
            arr[index] = arr[i];
            arr[i] = smallerNumber;
      }

这是选择排序的正确方法。 你一直做错的事情是在内部循环中进行交换，但实际上交换需要在第一轮内部循环完成后进行，此时最小元素已确定。

- Ibtihaj Uddin

---

虽然这可能解决问题，但它并没有解释为什么。 - cyroxis

Answer 6

/* Implementation of selection sort */

import java.util.Arrays;
import java.util.Scanner;


public class SelectionSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        System.out.println("Enter the number of elements of the array");
        int n = in.nextInt();
        int []a = new int[n];
        System.out.println("Enter the integer array of elements");
        for (int i=0; i<n ; i++)
        {
            a[i] = in.nextInt();
        }
        System.out.println("Before Sorting: "+Arrays.toString(a));
        a = sort(a);
        System.out.println("After Sorting: "+Arrays.toString(a));
    }

    private static int[] sort(int[] a) {
        // TODO Auto-generated method stub

        for(int i=0; i<a.length-1;i++)
        {
            int index=i;
            for(int j=i+1; j<a.length;j++)

                if(a[j]<a[index])
                {
                    index=j;
                }
                int small = a[index];
                a[index] = a[i];
                a[i]=small;

        }
        return a;
    }
}

- Mohit Motiani

Answer 7

选择排序算法通过重复从未排序的部分中找到最小元素（考虑升序），并将其放在开头来对数组进行排序。该算法在给定数组中维护两个子数组。

1）已经排序的子数组。 2）剩余未排序的子数组。

在选择排序的每次迭代中，从未排序的子数组中选择最小元素（考虑升序），并将其移动到已排序的子数组中。

例子：

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64 

Java 代码如下：

void sort(int arr[]) 
    { 
        int n = arr.length; 

        // One by one move boundary of unsorted subarray 
        for (int i = 0; i < n-1; i++) 
        { 
            // Find the minimum element in unsorted array 
            int min_idx = i; 
            for (int j = i+1; j < n; j++) 
                if (arr[j] < arr[min_idx]) 
                    min_idx = j; 

            // Swap the found minimum element with the first 
            // element 
            int temp = arr[min_idx]; 
            arr[min_idx] = arr[i]; 
            arr[i] = temp; 
        } 
    } 

请明确数组是按引用传递的！

- Syed Faizan

Answer 8

公共类Selectionsort{

public static int arr[]; public static int y;

public static void main( String args[] ){

System.out.println("输入您要排序的元素数量");

int nofele= Integer.parseInt(args[0]);

System.out.println("Enter number of element entered for sorting is "+ "\n" +nofele);

arr = new int[nofele];

System.out.println("Entered array is");

for(int i=1,j=0;i<=nofele;i++,j++){

arr[j]=Integer.parseInt(args[i]);

  System.out.println(arr[j]);

}

System.out.println("Sorted array for selection sort is ");

for(int k=0;k<nofele-1;k++)  {





  for(int l=nofele-k,b=1;l>=2;l--,b++){

    if(arr[k]>arr[k+b]){



     int temp=arr[k];

      arr[k]=arr[k+b];

      arr[k+b] = temp;


    }     

  }

   System.out.println(arr[k]);

}

   System.out.println(arr[nofele-1]);

}

}

- suyash saurabh

---

虽然这段代码可能回答了问题，但提供有关它如何以及/或为什么解决问题的附加上下文将改善答案的长期价值。您还应尝试正确格式化代码。 - Sebastian Hofmann

Answer 9

假设有一个最小元素，需要扫描所有元素并将其交换到第一个位置。

private static void selectionSortMethod(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {  //no of iterations for array length
            for (int j = i + 1; j < arr.length; j++) {  //starting from next index to lowest element(assuming 1st index as lowest)
                if (arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }

        }
         //print 
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

- ManishS

Answer 10

public class SelectionSort {

public static void main(String[] args) {
    int[] A = {5,4,3,2,1};
    int l = A.length;

    for (int i = 0; i < l-1; ++i ){
        int minPos = i;

        // Find the location of the minimal element
        for (int j = i + 1; j < l; ++j){
            if ( A[j] < A[minPos]){
                minPos = j;
            }
        }

        if (minPos != i){
            int temp = A[i];
            A[i] = A[minPos];   
            A[minPos] = temp;
        }
    }
    System.out.println(Arrays.toString(A));
}
}

- Ethan

---

虽然这段代码片段可能解决了问题，但包括解释真的有助于提高您的帖子质量。请记住，您正在为未来的读者回答问题，而这些人可能不知道您的代码建议原因。请尽量不要在代码中添加过多的解释性注释，这会降低代码和解释的可读性！ - Kyll