算 法：选择排序算法
时间复杂度：
- 选择排序算法概述
- 选择排序伪代码
- 选择排序实现
选择排序算法概述
排序算法有许多，选择排序也是其中一种较为简单的方法。它的算法过程是是每一趟将当前数与后面的每一个数进行比较，若不满足排序所需顺序则交换两个数的位置，这样第一趟比较结束后，第一个数就是正确顺序的数，第趟排序结束后，第
个位置的数都为正确的数，这个算法也被通俗地成称为“打擂台”，第一趟选择最大（最小）的数，第二趟选择出次大（次小）的数，一直到完成整个排序过程。
选择排序算法描述
- 第
趟“打擂台”过程从序列第
- 对于每一趟“打擂台”的选择过程，比较正在遍历的元素与第
- 持续1-2步骤直到每个位置都当过“擂主”。
选择排序示例
正在排序的数加粗表示3，排序后的数放于中括号内[3]，将被交换的数用斜体表示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]
选择排序实现
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语言与基础算法》
本文首发于个人博客算法 - 选择排序 | 不存在的貓， 转载请注明出处
