选择排序
算法思想
选择排序的思想与插入排序其实有异曲同工之处，它们都会对数据进行比较和交换，但是它们也还是有很大的差别：插入排序是两两元素之间进行比较，而选择排序是将最值的元素同其他元素依次进行比较，从而按照最大（或最小）、第二大、第三大这样的顺序进行数组的重组。
它的大致步骤如下：
- 第一次从待排序的数据元素中选出**最小（或最大）**的一个元素，存放在序列的起始(末尾)位置
- 然后选出**次小(或次大)**的一个元素，存放在最大(最小)元素的下一个位置
- 重复这样的步骤直到全部待排序的数据元素排完
图解
请添加图片描述C语言代码分析
代码语言：javascript复制//选择排序
void SelectSort1(int* a, int n);
void SelectSort2(int* a, int n);
//1.只进行最小值或者最大值的交换
void SelectSort1(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)
{
int min = left;//指定目前最小值为第一个元素
for (int i = left 1; i <= right; i )
{
if (a[i] < a[min])//如果有比目前最小值更小的元素，就更新最小值，进行交换
{
min = i;
}
}
if (min != left)//如果最小值不是第一个元素，就进行Swap交换
{
int temp = a[min];
a[min] = a[left];
a[left] = temp;
}
left ;//每完成一次交换，左指针向右移动一位，进行下一次交换
}
}
//2.最小值和最大值同时进行交换，优点是减少了交换次数，在一定程度上提高了效率
void SelectSort2(int* a, int n)//选择排序
{
int left; int right = n - 1;//左右指针
while (left < right)
{
int min = left, max = right;//最小值和最大值的下标
for(int i=left 1;i<=right;i )
{
if (a[i] < a[min])//找最小值
min = i;
if (a[i] > a[max])//找最大值
max = i;
}
if (min != left)
{
//进行一次Swap交换
int temp = a[min];
a[min] = a[left];
a[left] = temp;
}
//如果最大值和最小值相等，说明最大值和最小值是同一个元素，只需要进行一次交换
//如果继续交换max，就会将最小值交换到末尾位置。
if (left = right)
{
right = min;
}
left ;
right--;
}时间复杂度
选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为O(n2)。
稳定性
鉴于选择排序会改变前后元素的相对位置，所以：不稳定
