數組的排序：冒泡與選擇

數組排序中，冒泡跟選擇往往傻傻分不清楚，這次将詳細了解這兩種排序方法。

冒泡排序：每次比較的都是相鄰間的兩個數，一旦位置不對就交換位置(記住：是每次，是以時間複雜度高，效率慢，但也最穩定)。

選擇排序：每次選出一個最小(大)的數，将最小(大)的數與第一個數進行位置交換，然後在剩下的數中再次找出最小(大)的數與第二個數進行位置交換，直至循環到倒數第二個數與最後一個數為止(因為每次循環隻取最小(大)的一個數進行交換，是以效率比較高，而至于為什麼說是不穩定的排序，下面接着說)。

排序穩定性的定義：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

之是以說選擇排序是不穩定的，正是因為排序前後，相對位置發生了變化。下邊舉個栗子：

 相信大家看到這裡就會去對比冒泡排序，這裡部落客就直接上圖了，這裡感歎一下，為了畫圖，部落客真是殚精竭力啊~

好了，這裡解釋清了排序的穩定性，下面直接上代碼

/***
*選擇排序
*/
for(int i=0;i<arr.length-1;i++){	//這裡i-1的原因是循環到最後一個就不要再與最後一個進行比較
	int min = i;	//假設最小的值為第一個元素
	/**
	*内循環控制每輪比較的次數
	*/
	for(int j=i+1;j<arr.length;j++){	//這裡j+1的原因同上，第一個元素就不要與自己相比
		if(arr[j] < arr[min]){	//獲得該循環中最小的數的索引
			min = j;
		}
	}
	//找到最小值後進行元素交換
	if(min != i){
		int temp = arr[i];
		arr[i] = arr[min];
		arr[min] = temp;
	}
}

/***
*冒泡排序
*/
for(int i=0;i<arr.length-1;i++){
	for(int j=0;j<arr.length-1-i;j++){    //這裡-1-i是為了排除後面已排完序的值，已經排完序的值就不要在比較了
		if(arr[j] > arr[j+1]){
			int temp = arr[i];
			arr[j] = arr[j+1];
			arr[j+1] = temp;
		}
	}
}
           

 最後，按照國際慣例總結一下：

1. 冒泡排序是比較相鄰位置的兩個數，而選擇排序是按順序比較，找最大值或者最小值
2. 冒泡排序每一輪比較後，位置不對都需要換位置，選擇排序每一輪比較都隻需要換一次位置
3. 冒泡排序是通過數去找位置，選擇排序是給定位置去找數

部分文章引用：

直接選擇排序是不穩定的，以及怎樣将它變成穩定的排序。（https://blog.csdn.net/yishengguoke/article/details/87518054）