算 法：選擇排序算法
時間復雜度：
- 選擇排序算法概述
- 選擇排序偽代碼
- 選擇排序?qū)崿F(xiàn)
選擇排序算法概述
排序算法有許多渔隶，選擇排序也是其中一種較為簡單的方法绍弟。它的算法過程是是每一趟將當前數(shù)與后面的每一個數(shù)進行比較，若不滿足排序所需順序則交換兩個數(shù)的位置摹芙，這樣第一趟比較結(jié)束后晴弃，第一個數(shù)就是正確順序的數(shù)，第趟排序結(jié)束后或油，第
個位置的數(shù)都為正確的數(shù)寞忿，這個算法也被通俗地成稱為“打擂臺”，第一趟選擇最大（最卸グ丁）的數(shù)腔彰，第二趟選擇出次大（次小）的數(shù)辖佣，一直到完成整個排序過程霹抛。
選擇排序算法描述
- 第
趟“打擂臺”過程從序列第
- 對于每一趟“打擂臺”的選擇過程卷谈，比較正在遍歷的元素與第
- 持續(xù)1-2步驟直到每個位置都當過“擂主”端逼。
選擇排序示例
正在排序的數(shù)加粗表示3，排序后的數(shù)放于中括號內(nèi)[3]污淋，將被交換的數(shù)用斜體表示3
未排序： 5 31 16 9 7 10 3
第一趟：
** 5 ** 31 16 9 7 10 3
[3] 31 16 7 9 10 5
第二趟：
[3] 31 16 9 7 10 5
[3 5] 16 7 9 10 31
第三趟：
[3 5]16 9 7 10 31
[3 5] 9 16 7 10 31
[3 5 7] 16 9 10 31
第四趟：
[3 5 7]16 9 10 31
[3 5 7 9] 16 10 31
第五趟：
[3 5 7 9] 16 10 31
[3 5 7 9 10] 16 31
第六趟：
[3 5 7 9 10] 16 31
[3 5 7 9 10 16] 31
[3 5 7 9 10 16 31]
選擇排序偽代碼
SELECTIONSORT(A)
for i = 1 to A.length - 1
for j = i + 1 to A.length
if A[i] > A[j]
exchange A[j] with A[i]
選擇排序?qū)崿F(xiàn)
C
void selectionSort(arrType* a, int arrLength)
{
int i, j, t;
for (i = 0; i < arrLength - 1; i++) {
for (j = i + 1; j < arrLength; j++) {
if (a[i] > a[j]) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}
Pascal
procedure selectionsort;
var
i, j, t : integer;
begin
for i := 1 to arrLength - 1 do
for j := i + 1 to arrLength do
if a[j] < a[i] then
begin
t := a[i];
a[i] := a[j];
a[j] := t;
end;
end;
參考資料
- 《Free Pascal語言與基礎(chǔ)算法》
本文首發(fā)于個人博客算法 - 選擇排序 | 不存在的貓顶滩， 轉(zhuǎn)載請注明出處
