介绍

选择排序是一种简单直观的算法>排序算法，其基本思想是：从待排序的数据元素中，每次选择最小（或最大）的元素，将其与序列的起始位置交换，然后继续对剩余的元素进行排序，知道整个序列排序完成。

算法步骤

1、从待排序的序列中选择一个最小的元素，将其与序列第一个位置交换。

2、在剩余未排序的元素中继续选择最小的元素，放到已排序序列的末尾。

3、重复上述步骤，知道所有元素排序完成

优缺点

优点：

• 简单易懂：选择算法>排序算法简单直观，易于实现和理解
• 适用于小规模数据集：在小规模数据集上表现良好
• 部分有序数据集优化：在部分有序的数据集上可以进行优化
• 内存要求低：适用于对内存要求严格的场景
• 不敏感的数据集顺序：适用于对数据集的顺序不敏感的情况

缺点：

• 效率低：时间复杂度为,不适合大规模数据集
• 多次交换：需要进行多次交换操作
• 不稳定性：选择排序是不稳定的排序方法。相同的元素在排序后的相对位置可能会改

代码

#include <stdio.h>void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void SelectSort(int* a, int n)
{int begin = 0;while (begin < n - 1){int min = begin;for (int i = begin + 1; i < n; i++){if (a[i] < a[min]){min = i;}}Swap(&a[begin], &a[min]);begin++;}
}int main()
{int a[] = { 9,1,2,5,7,4,6,3 };int sz = sizeof(a) / sizeof(int);SelectSort(a, sz);Print(a, sz);return 0;
}

优化

每次循环只取一个最小值效率太慢，可以同时去最小值和最大值。

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int min = begin;int max = begin;for (int i = begin + 1; i <= end; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[begin], &a[min]);if (begin == max)max = min;Swap(&a[end], &a[max]);begin++;end--;}
}