排序算法——选择排序

发表于 更新于 分类于 ， ， ，

简介

选择排序(Selection sort)不断从乱序数列(后半部分)中选择最小(最大)值放入有序数列(前半部分)中，无论数据初始排列如何，其时间复杂度恒为\(O(n^2)\).好处是不占额外的空间复杂度。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {57, 65, 54, 30, 45, 7, 6, 26, 35, 96};
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        for (int i : arr) {
            System.out.println(i);
        }

    }
}
[out]:
6
7
26
30
35
45
54
57
65
96

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def selection_sort(arr):
    for i in range(len(arr) - 1):  # 可len(arr)
        for j in range(i + 1, len(arr)):  # 可i
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]
    return arr


if __name__ == '__main__':
    a = [18, 59, 41, 54, 14, 16, 79, 91, 88, 6]
    out = selection_sort(a)
    print(out)

[out]:
    [6, 14, 16, 18, 41, 54, 59, 79, 88, 91]