算法-选择排序

发表于 分类于

算 法：选择排序算法
时间复杂度：$O(n^2)$

  • 选择排序算法概述
  • 选择排序伪代码
  • 选择排序实现

选择排序算法概述

排序算法有许多，选择排序也是其中一种较为简单的方法。它的算法过程是是每一趟将当前数与后面的每一个数进行比较，若不满足排序所需顺序则交换两个数的位置，这样第一趟比较结束后，第一个数就是正确顺序的数，第$i$趟排序结束后，第$i$个位置的数都为正确的数，这个算法也被通俗地成称为“打擂台”，第一趟选择最大（最小）的数，第二趟选择出次大（次小）的数，一直到完成整个排序过程。

选择排序算法描述

  1. 第$i$趟“打擂台”过程从序列第$i$个元素开始遍历至尾部；
  2. 对于每一趟“打擂台”的选择过程，比较正在遍历的元素与第$i$个元素的大小关系，不满足，则交换两者位置；
  3. 持续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)

1
2
3
4
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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语言与基础算法》