JAVA排序算法之 選擇排序

1. 選擇排序

選擇排序的基本思想是周遊數組的過程中，以i代表目前需要排序的序号，則需要在剩餘的[i..n-1]中找出其中的最小值，然後将找到的最小值與i指向的值進行交換。因為每一次确定元素的過程中都會有一個選擇很大值的子流程，是以稱之為選擇排序。

比如[38, 17, 16, 16, 7, 31, 39, 32, 2, 11]

i = 0:  [2 , 17, 16, 16, 7, 31, 39, 32, 38 , 11] (0th [38]<->8th [2])

i = 1:  [2, 7 , 16, 16, 17 , 31, 39, 32, 38, 11] (1st [38]<->4th [17])

i = 2:  [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2nd [11]<->9th [16])

i = 3:  [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] ( 無需交換 )

i = 4:  [2, 7, 11, 16, 16 , 31, 39, 32, 38, 17 ] (4th [17]<->9th [16])

i = 5:  [2, 7, 11, 16, 16, 17 , 39, 32, 38, 31 ] (5th [31]<->9th [17])

i = 6:  [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6th [39]<->9th [31])

i = 7:  [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 無需交換 )

i = 8:  [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 無需交換 )

i = 9:  [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 無需交換 )

選擇排序随着排序的進行(i逐漸增大)，比較的次數會越來越少，但是不論數組初始是否有序，選擇排序都會從i至數組末尾進行一次選擇比較，是以給定長度的數組，選擇排序的比較次數是固定的:1+2+3+…+n=n*(n+1)/2,而交換的次數則跟初始數組的順序有關，如果初始數組順序為随機，則在最壞情況下數組元素将會交換N次，最好的情況是0次。選擇排序的時間複雜度和空間複雜度分别為O(n2 ) 和 O(1)。

package algorithms;

publicabstractclass Sorter<E extends Comparable<E>>  {

    publicabstractvoid sort(E[] array,int from ,int len);

    publicfinalvoid sort(E[] array)

    {

        sort(array,0,array.length);

    }

    protectedfinalvoid swap(E[] array,int from ,int to)

        E tmp=array[from];

        array[from]=array[to];

        array[to]=tmp;

      publicvoid sort(String helloString, int from, int len) {

            // TODO Auto-generated method stub

      }

}

/**

 * @author yovn

 *

 */

publicclass SelectSorter<E extends Comparable<E>> extends Sorter<E> {

      /* (non-Javadoc)

     * @see algorithms.Sorter#sort(E[], int, int)

     */

    @Override

    publicvoid sort(E[] array, int from, int len) {

        for(int i=0;i<len;i++)

        {

            int smallest=i;

            int j=i+from;

            for(;j<from+len;j++)

            {

                if(array[j].compareTo(array[smallest])<0)

                {

                    smallest=j;

                }

            }

            swap(array,i,smallest);

        }

    publicstaticvoid main(String[] args){

      String[] myStringArray = new String[3];

      String[] myStringArray1 = {"a","c","b"};

      String[] myStringArray2 = new String[]{"a","b","c"};

      SelectSorter<String> s1 = new SelectSorter<String>();

      for(int i=0;i<3;i++){

            System.out.println(myStringArray1[i]);

      }

      s1.sort(myStringArray1, 0, 3);

Output:

a

c

b

​