【算法】逻辑十分缜密，思路清晰的带大家一次性学会常见的排序算法系列ヾ(≧▽≦*)o。（二）选择排序-蒲公英云

【算法】逻辑十分缜密，思路清晰的带大家一次性学会常见的排序算法系列ヾ(≧▽≦*)o。（二）选择排序

✨前言✨：

算法是一个程序员的内功，能很好的体现程序员的编程思维，通过学习和掌握常见的算法，不仅能提高coding能力，还能更加容易在笔面试中脱颖而出。本专栏将记录博主刷算法题的过程，不定期的会更新一些优质的算法题。如果对大家有帮助，别忘了三连支持哟！

✨前言✨：

✨选择排序的思想✨

?如何进行选择?

?选择的具体方法?

✨具体代码的实现✨

✨时间复杂度的计算✨

✨选择排序的思想✨

顾名思义选择排序的核心思想就是如何进行选择？选择的具体方法是什么？只要明白了以上两点就足够完全理解选择排序。

?如何进行选择?

?：我们先假设有n个元素的乱序数组，要给这个数组排成升序。我们应该如何去做呢？

选择排序的意思是在下标为0~n-1上选择出最小值放在0位置，然后0位置不动，再在1~n-1位置选择出最小值放在1号位置，在2~n-1上选出最小值放在2号位置上，以此类推。和冒泡排序一样的是我们只需要n-1趟就能完成排序。因为如果n-1个数的位置都完全确定了，最后一个数的位置一定也确定了。

?选择的具体方法?

?：上文我们讲了选择排序的具体过程，但并没有讲选择的具体方法是什么，其实选择只需要以下4个步骤就可以了：

1：假设要选择范围内的第一个数为最小值，并记录其下标

2：将选择范围内的每一个数依次看一次

3：每看完一个数都把它与最小值下标所指向的元素比较，若当前数更小，则最小值下标更新成当前数的下标。

4：把选择范围内的每一个元素都进行完操作后，那么最小值下标记录的一定是选择范围内的最小值，把它与选择范围第一个元素进行交换即可。

?： 选择的具体过程可以形象的说成（看比更换）四个字。

讲到这里大家可能还是似懂非懂，毕竟有思路和真正写出代码还有较大的差距，我们接下来便看看代码，请大家结合上述步骤理解代码的逻辑。

✨具体代码的实现✨

void Swap(int arr[], int i, int j)
{
    //因为可能出现自己与自己交换
    //所以并不能使用按位异或操作进行交换
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
void selectionSort(int arr[], int sz)//sz表示元素个数
{
    for (int i = 0; i < sz - 1; i++)//最多跑sz-1趟，控制选择区域的范围
    {
        int minIndex = i;//假设选择区域第一个元素为最小值，minIndex记录最小值下标
        for (int j = i; j < sz; j++)//看操作
        {
            if (arr[j] < arr[minIndex])//比操作
            {
                minIndex = j;//更操作
            }
        }
        Swap(arr, minIndex,i);//换操作
    }
}