的Java：选择排序我的实现与另一

下面是我的实现选择排序的：的Java：选择排序我的实现与另一

package algorithm.selectionsort; 

public class SelectionSort { 

    public static void main(String[] args) { 
     int[] myArray = selectionSort(new int[] { 9, 9, 9, 8, 7, 73, 32, 109, 1100, 432, 321, 0 }); 

     for (int element : myArray) { 
      System.out.print("" + element + " "); 
     } 

    } 

    public static int[] selectionSort(int[] a) { 
     int min; 
     for (int i = 0; i < a.length - 1; i++) { 
      min = i; 
      for (int j = i + 1; j < a.length; j++) { 
       if (a[j] < a[min]) { 
        min = j; 
        int temp = a[i]; 
        a[i] = a[min]; 
        a[min] = temp; 

       } 
      } 
     } 
     return a; 

    } 

}

我发现我的导师代码它略有不同：

public static int[] selectionSort(int[] a) { 
    int min; 
    for (int i = 0; i < a.length - 1; i++) { 
     min = i; 
     for (int j = i + 1; j < a.length; j++) { 
      if (a[j] < a[min]) { 
       min = j; 


      } 
     } 
     int temp = a[i]; 
     a[i] = a[min]; 
     a[min] = temp; 
    } 
    return a; 

}

两种实施工作。我很好奇这里有什么不同。效率如何？

来源

2017-08-29 Dewey Banks

我明白了 - 我不必要地一遍又一遍地重复相同的代码。效果是一样的，但这会让我放慢抓取庞大的数据集。 –

你的老师实现了选择排序，你发明了另一种看起来非常相似但效率较低的排序。 – alfasin

https://codereview.stackexchange.com – nullpointer

你的导师和你的导师之间的区别在于他遍历数组，并且对于每个元素，搜索最小值，然后在墙索引之后与元素进行交换。

对于你的，你遍历数组和每个元素，同时搜索最小值，如果当前值是<那么当前暂定最小值，与墙索引之后的元素进行交换。

所以不是换了N次，你可以可以互换N * N次，最糟糕的情况：

你只是一个通（最坏情况）掉期：

100, 90, 88, 70, 55, 43, 32, 28, 19, 10 
90, 100, 88, 70, 55, 43, 32, 28, 19, 10 
88, 100, 90, 70, 55, 43, 32, 28, 19, 10 
70, 100, 90, 88, 55, 43, 32, 28, 19, 10 
55, 100, 90, 88, 70, 43, 32, 28, 19, 10 
43, 100, 90, 88, 70, 55, 32, 28, 19, 10 
32, 100, 90, 88, 70, 55, 43, 28, 19, 10 
28, 100, 90, 88, 70, 55, 43, 32, 19, 10 
19, 100, 90, 88, 70, 55, 43, 32, 28, 10 
10, 100, 90, 88, 70, 55, 43, 32, 28, 19

你的教练的交换只是一次通过（最糟糕的情况）：

100, 90, 88, 70, 55, 43, 32, 28, 19, 10 
10, 90, 88, 70, 55, 43, 32, 28, 19, 100

实质上，您在搜索最小值的同时交换值。您交换的“min”可能不是数组中的最小值。

来源

2017-08-29 02:45:53 user3437460

ofcouse of your instructor's code is more efficiency and more elegant。什么是选择排序？

该算法将输入列表分为两部分：已经排序的项目的子列表，其从列表的前部（左侧）从左到右构建，以及剩余的待排序项目的子列表占据了名单的其余部分。最初，排序的子列表是空的，未排序的子列表是整个输入列表。该算法通过查找未排序子列表中最小（或最大，取决于排序顺序）元素，与最左边未排序元素交换（交换）它（按排序顺序），并将子列表边界移动到对。

如果要排序的列表的长度为ñ，那么就ň交换的时候应该做的，但在你的代码，它是N *（N-1）*（N- 2）....

来源

2017-08-29 02:49:53 Javdroider

的Java：选择排序我的实现与另一

回答

相关问题