選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最幸舭瘛（或最大）的一個(gè)元素，存放在序列的起始位置赠叼，然后擦囊，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最凶彀臁（大）元素，然后放到已排序序列的末尾涧郊。以此類推贯被，直到全部待排序的數(shù)據(jù)元素排完妆艘。 選擇排序是不穩(wěn)定的排序方法。
選擇排序輸出的是原序列的一個(gè)重排 <a1*,a2*,a3*,...,an*>批旺；幌陕，使得 a1*<=a2*<=a3*<=...<=an*
排序算法有很多汽煮，包括插入排序棚唆，冒泡排序，堆排序搬卒，歸并排序，選擇排序契邀，計(jì)數(shù)排序摆寄，基數(shù)排序坯门，桶排序，快速排序等古戴。插入排序欠橘，堆排序现恼，選擇排序肃续，歸并排序和快速排序叉袍，冒泡排序都是比較排序，它們通過(guò)對(duì)數(shù)組中的元素進(jìn)行比較來(lái)實(shí)現(xiàn)排序喳逛，其他排序算法則是利用非比較的其他方法來(lái)獲得有關(guān)輸入數(shù)組的排序信息瞧捌。
思想
n 個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò) n-1 趟直接選擇排序得到有序結(jié)果：
①初始狀態(tài)：無(wú)序區(qū)為 R[1..n]润文，有序區(qū)為空。
②第 1 趟排序
在無(wú)序區(qū) R[1..n] 中選出關(guān)鍵字最小的記錄 R[k]典蝌，將它與無(wú)序區(qū)的第 1 個(gè)記錄 R[1] 交換曙砂，使 R[1..1] 和 R[2..n] 分別變?yōu)橛涗泜€(gè)數(shù)增加 1 個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1 個(gè)的新無(wú)序區(qū)赠法。
……
③第 i 趟排序
第 i 趟排序開始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為 R[1..i-1] 和 R(i..n）砖织。該趟排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄 R[k]款侵，將它與無(wú)序區(qū)的第 1 個(gè)記錄 R 交換侧纯，使 R[1..i] 和 R 分別變?yōu)橛涗泜€(gè)數(shù)增加 1 個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1 個(gè)的新無(wú)序區(qū)。?[1]
解釋
對(duì)比數(shù)組中前一個(gè)元素跟后一個(gè)元素的大小眶熬，如果后面的元素比前面的元素小則用一個(gè)變量 k 來(lái)記住他的位置妹笆，接著第二次比較，前面 “后一個(gè)元素” 現(xiàn)變成了 “前一個(gè)元素”拳缠，繼續(xù)跟他的“后一個(gè)元素” 進(jìn)行比較如果后面的元素比他要小則用變量 k 記住它在數(shù)組中的位置(下標(biāo))墩新，等到循環(huán)結(jié)束的時(shí)候窟坐，我們應(yīng)該找到了最小的那個(gè)數(shù)的下標(biāo)了，然后進(jìn)行判斷哲鸳，如果這個(gè)元素的下標(biāo)不是第一個(gè)元素的下標(biāo)臣疑，就讓第一個(gè)元素跟他交換一下值徙菠，這樣就找到整個(gè)數(shù)組中最小的數(shù)了。然后找到數(shù)組中第二小的數(shù)婿奔，讓他跟數(shù)組中第二個(gè)元素交換一下值缺狠，以此類推萍摊。
算法性能
時(shí)間復(fù)雜度
選擇排序的交換操作介于 0 和 (n - 1） 次之間儒老。選擇排序的比較操作為 n (n - 1） / 2 次之間记餐。選擇排序的賦值操作介于 0 和 3 (n - 1） 次之間薇正。
比較次數(shù) O(n^2），比較次數(shù)與關(guān)鍵字的初始狀態(tài)無(wú)關(guān)挖腰，總的比較次數(shù) N=(n-1）+(n-2）+...+1=n*(n-1）/2雕沿。交換次數(shù) O(n）猴仑，最好情況是，已經(jīng)有序辽俗，交換 0 次疾渣；最壞情況交換 n-1 次崖飘，逆序交換 n/2 次榴捡。交換次數(shù)比冒泡排序少多了朱浴，由于交換所需 CPU 時(shí)間比比較所需的 CPU 時(shí)間多达椰，n 值較小時(shí)，選擇排序比冒泡排序快项乒。?[1]
其他排序算法的復(fù)雜度如右圖所示。
穩(wěn)定性
選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的檀何，比如給第一個(gè)位置選擇最小的蝇裤，在剩余元素里面給第二個(gè)元素選擇第二小的埃碱，依次類推，直到第 n-1 個(gè)元素砚殿，第 n 個(gè)元素不用選擇了啃憎，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了似炎。那么，在一趟選擇羡藐，如果一個(gè)元素比當(dāng)前元素小贩毕，而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面仆嗦，那么交換后穩(wěn)定性就被破壞了辉阶。比較拗口瘩扼，舉個(gè)例子，序列 5 8 5 2 9集绰，我們知道第一遍選擇第 1 個(gè)元素 5 會(huì)和 2 交換巡通，那么原序列中兩個(gè) 5 的相對(duì)前后順序就被破壞了魄宏，所以選擇排序是一個(gè)不穩(wěn)定的排序算法潮模。
java代碼如下：
package 數(shù)據(jù)結(jié)構(gòu);
public class xuanzepaixu {
? public static void sort(long arr[]){
? long temp=0;//中間變量用來(lái)交換數(shù)據(jù)
? int k;//定義一個(gè)選擇變量來(lái)進(jìn)行選擇
? for(int i=0;i<arr.length-1;i++){//循環(huán)
? k=i;//每次循環(huán)都將這一次i的值賦給k
? for(int j=i;j<arr.length;j++){//數(shù)據(jù)比較
? if(arr[k]>arr[j]){//效率比冒泡高碍岔，如果arr[k]后面的數(shù)據(jù)比它小，則交換數(shù)據(jù)
? temp=arr[j];
? arr[j]=arr[k];
? arr[k]=temp;
? }
? }
? arr[i]=arr[k];//通過(guò)選擇k找到每一輪的最小值arr[k]賦給arr[i]蔼啦，即順序已經(jīng)排好
? }
? }
}
測(cè)試：
package 數(shù)據(jù)結(jié)構(gòu);
public class Testxuanzepaixu {
? ? public static void main(String args[]){
? ? long arr[]=new long[6];
? ? arr[0]=2;
? ? arr[1]=1;
? ? arr[2]=5;
? ? arr[3]=3;
? ? arr[4]=8;
? ? arr[5]=0;
? ? xuanzepaixu.sort(arr);
? ? for(int i=0;i<arr.length;i++){
? ? System.out.println(arr[i]);
? ? }
? }
? ? }
輸出結(jié)果如下：
好啦,這次就到這里啦兰珍，有問(wèn)題可以和我留言哦询吴！
其他博客的鏈接：
Github個(gè)人網(wǎng)站??知乎??簡(jiǎn)書
歡迎各位訪問(wèn)哦亮元，這次就到這里啦！
