选择排序

Simple Selection Sort

思路

. 从无序序列中选择关键特征最小的记录，放到有序序列的最后面或当前无序序列的第一个位置

. 重复操作直到无序序列只有1个时，排序结束

. 需要1个哨兵记录当前最小位置，并不断更新

. 每一趟先找到最小的索引，最后再交换；不需要每次都交换

. 更多信息，请访问 哔哩哔哩-选择排序、Selection Sort

已知待排序序列{8,6,9,2,3,7}，给出简单选择排序过程

简单排序过程

	最小数据	8 6 9 2 3 7
第1轮交换	2	2 6 9 8 3 7
第2轮交换	3	2 3 9 8 6 7
第3轮交换	6	2 3 6 8 9 7
第4轮交换	7	2 3 6 7 9 8
第5轮交换	8	2 3 6 7 8 9

已知待排序序列{49, 38, 65, 97, 49*, 13, 27, 76}，给出简单选择排序过程

简单排序过程

	0	1	2	3	4	5	6	7
初始	49	38	65	97	49*	13	27	76
0	49	38	65	97	49*	13	27	76
	13	38	65	97	49*	49	27	76
1	13	38	65	97	49*	49	27	76
	13	27	65	97	49*	49	38	76
2	13	27	65	97	49*	49	38	76
	13	27	38	97	49*	49	65	76
3	13	27	38	97	49*	49	65	76
	13	27	38	49*	97	49	65	76
4	13	27	38	49*	97	49	65	76
	13	27	38	49*	49	97	65	76
5	13	27	38	49*	49	97	65	76
	13	27	38	49*	49	65	97	76
6	13	27	38	49*	49	65	97	76
	13	27	38	49*	49	65	76	97

设一组待排序的关键字序列为{12,5,16,21,10,3}，用简单选择排序法按关键字从小到大进行排序，写出每趟排序结束后关键字序列的状态

简单排序过程

	0	1	2	3	4	5
初始	12	5	16	21	10	3
0	12	5	16	21	10	3
1	3	5	16	21	10	12
2	3	5	16	21	10	12
3	3	5	10	21	16	12
4	3	5	10	12	16	21
5	3	5	10	12	16	21

#include <stdio.h>
void dis(int arr[], int len);
void selectionSort(int arr[], int len);
int main()
{
    int arr[] = {1, 23, 4, 69, 25, 9};
    int len=sizeof(arr)/sizeof(arr[0]);
    dis(arr, len);
    selectionSort(arr, len);
    return 0;
}

void selectionSort(int arr[], int len)
{
    int i, j, min;
    for (i = 0; i < len - 1; i++)
    {
        int minInd = i;
        for (j = i + 1; j < len; j++)
        {
            if (arr[j] < arr[minInd])
            {
                minInd = j;
            }
        }
        // swap
        //改进：如果没有变化，不应该交换
        min = arr[minInd];
        arr[minInd] = arr[i];
        arr[i] = min;

        printf("第%d次排序 ",i);
        dis(arr, len);
      }
}

void dis(int arr[], int len)
{
    int i;
    for (i = 0; i < len; i++)
    {
        printf("%d\t", arr[i]);
    }
    printf("\n");
}

特点

. 稳定

. 可用于链式存储

. 比直接插入排序快

. 时间复杂度：O(n²)

. 空间复杂度：O(1)，需要1个哨兵