选择排序

什么是选择排序？

它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。 以此类推，直到全部待排序的数据元素的个数为零

选择排序动图演示

思路

在未排序序列中找到最小（大）元素，将其与第一个元素交换

在未排序序列中找到最小（大）元素，将其与第二个元素交换

…

代码实现

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int main()
{

    int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int i, j;
    for (i = 0; i < sz - 1; i++)
    {
        int min = i;
        for (j = i + 1; j < sz; j++)
        {
            if (arr[min] > arr[j])
            {
                min = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
        printf("第%d轮：", i+1);
        printArr(arr,sz);
    }

    return 0;
}

int printArr(int arr[], int sz)
{
    int i;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

输出：
第1轮：1 9 8 7 6 5 4 3 2 10
第2轮：1 2 8 7 6 5 4 3 9 10
第3轮：1 2 3 7 6 5 4 8 9 10
第4轮：1 2 3 4 6 5 7 8 9 10
第5轮：1 2 3 4 5 6 7 8 9 10
第6轮：1 2 3 4 5 6 7 8 9 10
第7轮：1 2 3 4 5 6 7 8 9 10
第8轮：1 2 3 4 5 6 7 8 9 10
第9轮：1 2 3 4 5 6 7 8 9 10

写成函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int selectionSort(int arr[], int sz)
{
    int i, j;
    for (i = 0; i < sz - 1; i++)
    {
        int min = i;
        for (j = i + 1; j < sz; j++)
        {
            if (arr[min] > arr[j])
            {
                min = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[min];
        arr[min] = tmp;
    }
    
    return 0;
}