原理
選擇排序是從一堆參與比較的資料中找出最小值,然後拿着這個最小值與此時參與比較的元素中的最前面的那個交換位置。除去這個最小值,剩下的元素為下一輪循環的參與比較的元素,繼續找出最小值,然後與目前參與比較的元素中的最前面的那個進行交換,直到最後。
舉例
例如數組元素為:5,6,4,7,1
第一次循環:
(1最小,5和1交換位置): 1,6,4,7,5
至此,1被選出來,剩下的元素為下一輪參與比較的元素:6,4,7,5
第二次循環:
(4最小,6與4交換位置): 4,6,7,5
至此,4被選出來,剩下的元素為下一輪參與比較的元素:6,7,5
第三次循環:
(5最小,6與5交換位置):5,7,6
至此,5被選出來,剩下的元素為下一輪參與比較的元素:7,6
第四次循環:
(6最小,7與6交換位置):6,7
至此,循環結束,排序結果為:1,4,5,6,7
如何選出最小值
先假設目前參與比較的元素中最前面的數為最小值(arr[min]),再依次和後面的數進行比較,若無比這個數還小的數,則這個數就是最小值;若有比這個數還小的數,則将下标指派給min,循環結束将找到的最小值與目前參與比較的元素中最前面的數進行交換。
Java代碼
public static void main(String[] args){
int[] arr={5,6,4,7,1};
for (int i=0;i<arr.length-1 ;i++ )
{
//i剛好是每一次的待比較資料的第一個元素的下标
//先假設最小值下标為最前面的元素的下标
int min=i;
for (int j=i+1;j<arr.length ;j++ )
{
//如果有比目前最小值還小的數,就将該值的下标賦給min
if (arr[j]<arr[min])
{
min=j;
}
}
//如果min還是i的話,則證明目前參與比較的數中最前面的就是最小值,就不需要交換位置了.
//如果min不是i的話,則證明最小值是其他的數,就交換位置,将最小值與目前參與比較的數的最前面的交換
if (i!=min)
{
//交換位置
int temp;
temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
//按序輸出數組元素
for (int i=0;i<arr.length;i++)
{
System.out.println(arr[i]);
}
}
輸出結果
1
4
5
6
7