1 選擇排序法的定義

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。（來自百度百科）

2 選擇排序法詳細(xì)過程解析

假定有這樣一個(gè)數(shù)組

int［］ nums = new int［］{6， 4， 5， 1， 3， 2};

現(xiàn)在需要將他從大到小排列。

選擇排序法代碼如下：

排序詳細(xì)過程：

［6， 4， 5， 1， 3， 2］ 第一次遍歷6和2交換位置

［6， 5， 4， 1， 3， 2］ 第二次遍歷5和4交換位置

［6， 5， 4， 1， 3， 2］ 第三次遍歷4位置不變

［6， 5， 4， 3， 1， 2］ 第四次遍歷3和1交換位置

［6， 5， 4， 3， 2， 1］ 第五次遍歷2和1交換位置

3 選擇排序法時(shí)間復(fù)雜度

數(shù)據(jù)比較次數(shù)：

C = （N-1）+（N-2）+……+2+1=（（（N-1）+1）*（N-1）） / 2=（N^2）/2-N/2

數(shù)據(jù)交換次數(shù)：

M = N-1

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

C+M=（N^2）/2-N/2+ N-1=O（N^2）

因此，選擇排序的時(shí)間復(fù)雜度為O（N^2）

4 結(jié)語

感謝各位的閱讀，如有問題，歡迎大家留言反饋，我會(huì)在第一時(shí)間修正。