選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
注意選擇排序與冒泡排序的區(qū)別：冒泡排序通過依次交換相鄰兩個(gè)順序不合法的元素位置，從而將當(dāng)前最?。ù螅┰胤诺胶线m的位置；而選擇排序每遍歷一次都記住了當(dāng)前最?。ù螅┰氐奈恢?，最后僅需一次交換操作即可將其放到合適的位置

排序過程

java 實(shí)現(xiàn)：

public class ChooseOrderTest {
    public static void main(String[] args) {
        int[] input = new int[]{2,5,4,89,7,89,52,12,54,78};
        for (int n = 0; n < input.length; n++){
            int minIndex = n;
            for (int m = n; m < input.length; m++){
                if (input[m] < input[minIndex]){
                    minIndex = m;
                }
            }
            if(minIndex != n){
                int temp = input[minIndex];
                input[minIndex] = input[n];
                input[n] = temp;
            }
        }
        PrintUtils.print(input);
    }
}

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(n^2)
  （和冒泡不同，每次循環(huán)，未排序的部分都可能是亂序，所以無(wú)法判斷何時(shí)跳出，例如：1 2 3 4 5, 排到 3，實(shí)際上已經(jīng)完成排序了，但是選擇排序無(wú)法知道，后面的排序是正確的，仍要走完循環(huán)才行）
• 最壞時(shí)間復(fù)雜度：O(n^2)
• 穩(wěn)定性：不穩(wěn)定（不穩(wěn)定發(fā)生在最小元素與 input[i] 交換的時(shí)刻，例如：在取最大值優(yōu)先等情況下，3 2 8 8 5 的排序?yàn)?2 3 5 8 8，可以看到兩個(gè) 8 顛倒了順序）

相比于冒泡排序，選擇排序更劃算，因?yàn)槊芭菪枰粩嗟亟粨Q，而選擇排序則是比較一輪，然后再進(jìn)行交換一次。通常情況交換次數(shù)要少于冒泡排序。