選擇排序
選擇排序也是利用了“擋板法”這個經典思想。
擋板左邊是已排序區間,右邊是未排序區間,那麼每次的“選擇”是去找右邊未排序區間的最小值,找到之後和擋板後面的第一個值換一下,然後再把擋板往右移動一位,保證排好序的這些元素在擋板的左邊。
比如例子:{5, 2, 0, 1}
我們用一個擋板來分隔數組是否排好序,
用指針 j 來尋找未排序區間的最小值;
![排序算法入門:選擇排序](http://p2.ttnews.xyz/loading.gif)
第一輪 j 最初指向 5,然後遍歷整個未排序區間,最終指向 0,那麼 0 就和擋板後的第一個元素換一下,也就是和 5 交換一下位置,擋板向右移動一位,結束第一輪。
![排序算法入門:選擇排序](http://p2.ttnews.xyz/loading.gif)
第二輪,j 從擋板後的2開始遍歷,最終指向1,然後1和擋板後的第一個元素 2 換一下,擋板向右移動一位,結束第二輪。
第三輪,j 從2開始遍歷,最終指向2,然後和2自己換一下,擋板向右移動一位,結束第三輪。
還剩一個元素,不用遍歷了,就結束了。
選擇排序與之前的插入排序對比來看,要注意兩點:
擋板必須從 0 開始,而不能從 1 開始。雖然在這兩種算法中,擋板的物理意義都是分隔已排序和未排序區間,但是它們的已排序區間裡放的元素的意義不同:
選擇排序是隻能把當前的最小值放進來,而不能放其他的;
插入排序的第一個元素可以為任意值。
所以選擇排序的擋板左邊最開始不能有任何元素。
在外層循環時,
-
選擇排序的最後一輪可以省略,因為只剩下最大的那個元素了;
插入排序的最後一輪不可省略,因為它的位置還沒定呢。
<code>class
Solution
{public
void
selectionSort
(int
[] input) {if
(input ==null
|| input.length <=1
) {return
; }for
(int
i =0
; i < input.length -1
; i++) {int
minValueIndex = i;for
(int
j = i +1
; j < input.length; j++) {if
(input[j] < input[minValueIndex]) { minValueIndex = j; } } swap(input, minValueIndex, i); } }private
void
swap
(int
[] input,int
x,int
y) {int
tmp = input[x]; input[x] = input[y]; input[y] = tmp; } } /<code>
時間複雜度
最內層的 if 語句每執行一次是 O(1) ,那麼要執行多少次呢?
當 i = 0 時,是 n-1 次;
當 i = 1 時,是 n-2 次;
…
最後是 1 次;
所以加起來,總共是:
(n-1) + (n-2) + … + 1 = n*(n-1) / 2 = O(n^2)
是這樣算出來的,而不是一拍腦袋說兩層循環就是 O(n^2).
空間複雜度
這個很簡單,最多的情況是 call swap() 的時候,然後 call stack 上每一層就用了幾個有限的變量,所以是 O(1)。
那自然也是原地排序算法了。
穩定性
這個答案是否定的,選擇排序並沒有穩定性。
因為交換的過程破壞了原有的相對順序,比如: {5, 5, 2, 1, 0} 這個例子,第一次交換是 0 和 第一個 5 交換,於是第一個 5 跑到了數組的最後一位,且再也無翻身之地,所以第一個 5 第二個 5 的相對順序就已經打亂了。