算法-选择排序

发表于 分类于

算 法：选择排序算法 时间复杂度：\(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语言与基础算法》