1.復(fù)雜度與穩(wěn)定性

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

最壞情況：O(n^2)

最好情況：O(1)           //即不需要排序，本身已是正序

平均情況：O(n^2)

空間復(fù)雜度：S(n)=O(1)

穩(wěn)定性：不穩(wěn)定排序

2.過程介紹（以順序?yàn)槔?/span>

1.我們?cè)O(shè)置兩個(gè)記錄i和j，i自數(shù)組第一個(gè)元素開始，j自i+1個(gè)元素開始。

2.接著j遍歷整個(gè)數(shù)組，選出整個(gè)數(shù)組最小的值，并讓這個(gè)最小的值和i的位置交換（如果i選擇的元素是最小的則不需要交換），我們稱這個(gè)過程為一趟選擇排序。

3.i選中下一個(gè)元素(i++)，重復(fù)進(jìn)行每一趟選擇排序。

4.持續(xù)上述步驟，使得i到達(dá)n-1處，即完成排序 。

3.圖示過程：

以數(shù)據(jù){2,10,9,4,8,1,6,5}為例

如圖所使，每次交換的數(shù)據(jù)使用紅顏色標(biāo)記出，已經(jīng)排好序的數(shù)據(jù)使用藍(lán)底標(biāo)注，

每一趟從待排序的數(shù)據(jù)元素中選出最小的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完，我們只需要進(jìn)行n-1趟排序即可，因?yàn)樽詈笫Ｏ碌囊粋€(gè)數(shù)據(jù)一定是整體數(shù)據(jù)中最大的數(shù)據(jù)。

4.代碼實(shí)現(xiàn)：

#include<iostream>
using namespace std;
void select_sort(int a[],int n){
    int temp;
    for(int i=0;i<n-1;i++){
        temp=i;      //利用一個(gè)中間變量temp來記錄需要交換元素的位置
        for(int j=i+1;j<n;j++){
            if(a[temp]>a[j]){   //選出待排數(shù)據(jù)中的最小值
                temp=j;  
            }
        }
        swap(a[i],a[temp]); //交換函數(shù)
    }
} 
int main(){
    int a[8]={2,10,9,4,8,1,6,5};
    int n=8;
    select_sort(a,n);
    for(int i=0;i<n;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

相比冒泡排序的不斷交換，簡(jiǎn)單選擇排序（simple selection sort）是等到合適的關(guān)鍵字出現(xiàn)后再進(jìn)行交換，并且移動(dòng)（交換）一次就可以達(dá)到一次冒泡的效果。