簡介：

簡單選擇排序的思想是：設排序序列的記錄個數(shù)為n，進行n-1次選擇，每次在n-i+1(i = 1,2,...,n-1)個記錄中選擇關(guān)鍵字最小的記錄作為有效序列中的第i個記錄。

例如，排序序列(57，68，59，52)的過程是，進行3次選擇，第1次選擇在4個記錄中選擇最小的值為52，放在第1個位置，得到序列(52，68，59，57)，第2次選擇從位置1開始的3個元素中選擇最小的值57放在第2個位置，得到有序序列(52，57，59，68)，第3次選擇因為最小的值59已經(jīng)在第3個位置不需要操作，最后得到有序序列（52，57，59，68）。

實現(xiàn)：

package suanfa;
/*
 * 簡單選擇排序
 */
public class EasySelect {
    
    public static void SelectionSort(int[] array) {

        for (int i = 0; i < array.length - 1; i++) {    
             
            int min = i;

            // 每次從未排序數(shù)組中找到最小值的坐標
            for (int j = i + 1; j < array.length; j++) {

                if (array[j] < array[min]) {
                    min = j;
                }
            }

            // 將最小值放在最前面
            if (min != i) {
                int temp = array[min];
                array[min] = array[i];
                array[i] = temp;
                
            }
           
        }

    }
    
    public static void print(int src[]) {
         for (int i = 0; i < src.length; i++) {
             
                System.out.print(src[i] + " ");
            }
         System.out.println();
     }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int array[]= {57,68,59,52};
        print(array);
        SelectionSort(array);
        print(array);
    }

}

分析：

簡單選擇排序過程中需要進行的比較次數(shù)與初始狀態(tài)下待排序的記錄序列的排列情況 無關(guān)。當i=1時，需進行n-1次比較；當i=2時，需進行n-2次比較；依次類推，共需要進行的比較次數(shù)是(n-1)+(n-2)+…+2+1=n(n-1)/2，即進行比較操作的時間復雜度為 O(n^2) ，進行移動操作的時間復雜度為 O(n) 。總的時間復雜度為 O(n^2) 。

最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動記錄。最壞情況下，即待排序記錄初始狀態(tài)是按第一條記錄最大，之后的記錄從小到大順序排列，則需要移動記錄的次數(shù)最多為3（n-1）。

簡單選擇排序是不穩(wěn)定排序。

總結(jié)

以上是生活随笔為你收集整理的简单选择排序（选择排序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。