文 | 莫若吻
1.簡(jiǎn)介
排序就是算法拓劝。
? 選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法考赛。
選擇排序是不穩(wěn)定的排序方法一罩。
? eg：序列[9，9灯蝴， 1]第一次就將第一個(gè)[9]與[1]交換抗碰，導(dǎo)致第一個(gè)9挪動(dòng)到第二個(gè)9后面
Note：一般面試的時(shí)候才會(huì)用到選擇、冒泡排序绽乔。
2.原理
選擇排序的工作原理是**每一次從待排序的數(shù)據(jù)元素中選出最谢∮（或最大）的一個(gè)元素，存放在序列的起始位置折砸，直到全部待排序的數(shù)據(jù)元素排完看疗。 **
3.原理過(guò)程圖
內(nèi)循環(huán)結(jié)束一次，最值出現(xiàn)頭角標(biāo)位置上睦授。（原理過(guò)程如下圖）
4.時(shí)間復(fù)雜度
簡(jiǎn)單選擇排序的比較次數(shù)與序列的初始排序無(wú)關(guān)两芳。 假設(shè)待排序的序列有 n 個(gè)元素，選擇排序的賦值操作介于 0 和 3 (n - 1） 次之間; 則比較次數(shù) 永遠(yuǎn)都是n (n- 1) / 2; 而移動(dòng)次數(shù)（即：交換操作）與序列的初始排序有關(guān),介于 0 和 (n - 1） 次之間去枷。當(dāng)序列正序時(shí)怖辆，移動(dòng)次數(shù)最少，為 0删顶。當(dāng)序列反序時(shí)竖螃，移動(dòng)次數(shù)最多，為n - 1 次;逆序交換n/2次逗余。綜上特咆，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為 O(n2)。
選擇排序的移動(dòng)次數(shù)比冒泡排序少多了录粱，由于交換所需CPU時(shí)間比 比較所需的CPU時(shí)間多腻格，n值較小時(shí)，選擇排序比冒泡排序快啥繁。
5.性能分析 (穩(wěn)定性)
選擇排序的時(shí)間復(fù)雜度為O(n2)菜职，由于每次選擇僅考慮某一位置上的數(shù)據(jù)情況，可能會(huì)破壞之前數(shù)據(jù)的相對(duì)位置旗闽，因此它是一種不穩(wěn)定的排序方法酬核。
6.選擇排序有兩個(gè)重要特點(diǎn):
1)運(yùn)行時(shí)間和輸入無(wú)關(guān)
即不論數(shù)組的初始狀態(tài)的有序程度，選擇排序的比較次數(shù)都沒(méi)有變化宪睹〕钭拢考慮到比較次數(shù)與元素個(gè)數(shù)的關(guān)系是n (n- 1)/ 2，所以當(dāng)一個(gè)已經(jīng)比較有序的數(shù)組使用選擇排序會(huì)很不劃算亭病。
2)數(shù)據(jù)的移動(dòng)操作最少
移動(dòng)操作次數(shù)是一個(gè)常量鹅很，最多為n-1，其他的算法都不具備這個(gè)特征罪帖。
7.選擇排序與冒泡排序哪個(gè)效率更高促煮？
選擇排序邮屁、冒泡排序都用for（for(if)）結(jié)構(gòu)語(yǔ)句。一般選擇排序效率會(huì)更高一些菠齿。
自我總結(jié)分析原因：（更詳細(xì)情況請(qǐng)參考上面選擇排序的時(shí)間復(fù)雜度）
冒泡排序的思想為每一次排序過(guò)程佑吝，通過(guò)相鄰元素的交換，將當(dāng)前沒(méi)有排好序中的最大（猩取）移到數(shù)組的最右（左）端芋忿。而選擇排序的思想也很直觀：每一次排序過(guò)程，我們獲取當(dāng)前沒(méi)有排好序中的最大（屑部谩）的元素和數(shù)組最右（左）端的元素交換戈钢，循環(huán)這個(gè)過(guò)程即可實(shí)現(xiàn)對(duì)整個(gè)數(shù)組排序。
同樣數(shù)據(jù)的情況下是尔，兩種算法的循環(huán)次數(shù)是一樣的殉了，但選擇排序只有0到1次交換，而冒泡排序只有0到n次交換 拟枚。而影響我們算法效率的主要部分是循環(huán)和交換薪铜，顯然，次數(shù)越多恩溅，效率就越差隔箍。選擇排序的平均時(shí)間復(fù)雜度比冒泡排序的稍低。所以相比較而言選擇排序效率會(huì)更高一些暴匠。
8.示例代碼（Java）
對(duì)給指定數(shù)組進(jìn)行排序：{5,1,6,4,2,8,9}
核心代碼：
/*
選擇排序鞍恢。
內(nèi)循環(huán)結(jié)束一次傻粘，最值出現(xiàn)頭角標(biāo)位置上每窖。
*/
public static void selectSort(int[] arr)
{
for (int x=0; x<arr.length-1 ; x++)
{
for(int y=x+1; y<arr.length; y++)
{
if(arr[x]>arr[y]) //缺點(diǎn)：性能低。
{
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
}```
__詳細(xì)代碼：__
? （注：大家可以自行運(yùn)行結(jié)果查看）
import java.util.*;
class ArraySort
{
public static void main(String[] args)
{
int[] arr = {5,1,6,4,2,8,9};
//排序前弦悉；
printArray(arr);
//選擇排序
selectSort(arr);
//冒泡排序
//bubbleSort(arr);
//排序后：
printArray(arr);
//Arrays.sort(arr); //java中已經(jīng)定義好的一種排序方式窒典。開(kāi)發(fā)中，對(duì)數(shù)組排序稽莉。要使用該句代碼瀑志。
}
/*
選擇排序。
內(nèi)循環(huán)結(jié)束一次污秆，最值出現(xiàn)頭角標(biāo)位置上劈猪。
*/
public static void selectSort(int[] arr)
{
for (int x=0; x<arr.length-1 ; x++)
{
for(int y=x+1; y<arr.length; y++)
{
if(arr[x]>arr[y]) //缺點(diǎn)：性能低。
{
swap(arr,x,y);
}
}
}
}
/*
無(wú)論什么排序良拼。都需要對(duì)滿足條件的元素進(jìn)行位置置換战得。
所以可以把這部分相同的代碼提取出來(lái)，單獨(dú)封裝成一個(gè)函數(shù)庸推。
*/
public static void swap(int[] arr,int a,int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/*
排序顯示格式
*/
public static void printArray(int[] arr)
{
System.out.print("[");
for(int x=0; x<arr.length; x++)
{
if(x!=arr.length-1)
System.out.print(arr[x]+", ");
else
System.out.println(arr[x]+"]");
}
}
}
<br/>
***
版權(quán)聲明：本文為博主原創(chuàng)文章常侦，轉(zhuǎn)載請(qǐng)必須注明出處浇冰，謝謝！
<br/>