【数据结构】选择排序

大家好，我是苏貝，本篇博客带大家了解选择排序，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

一. 基本思想

每一次从待排序的数据元素中选出最小（或最大或最小和最大）的元素，存放在序列的起始位置（或末尾位置或起始和末尾位置），直到全部待排序的数据元素排完。

下面是从待排序的数据元素中选出最小的元素的动图
在这里插入图片描述

二. 直接选择排序

下面我们用每一次选出最小和最大的元素，放在序列的起始和末尾位置来举例。

首先，因为我们要将最值放入起始和末尾位置，所以我们需要有2个变量来指示这两个位置，用begin和end。
第二：我们知道最值的下标后要将它们的信息存起来，所以用mini和maxi来存储最值的下标
第三：我们要遍历数组，所以需要通过循环

下面是我写的代码，大家能否发现一些问题呢？

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin; i <= end; i++){if (a[i] < a[mini])mini = i;if (a[i] > a[maxi])maxi = i;}Swap(&a[begin], &a[mini]);Swap(&a[end], &a[maxi]);begin++;end--;}
}int main()
{int a[] = { 0,3,1,7,6,8,4,5,9,6,2 };int n = sizeof(a) / sizeof(int);SelectSort(a, n);PrintArray(a, n);return 0;
}

在这里插入图片描述

其实上面代码绝大部分都是正确的，所以上面的数组可以被正确排列
那我们再试试下面的数组呢，这也是正确的吗？

int a[] = { 10,3,1,7,6,8,4,5,9,6,2 };

事实证明：不是

在这里插入图片描述

为什么呢？在这个数组里，第一次排序时，最大值的下标maxi==begin，当交换下标为begin和mini的值后，a[begin]==1而不是 ==10，此时再交换下标为end和maxi的值时，就是1和2交换。所以我们在交换下标为end和maxi的值前，先判断maxi是否 ==begin，等于的话就要将maxi置为mini

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