【学习分享】小白写算法之选择排序篇

前言

简单排序有三种，冒泡排序，插入排序和选择排序。这三种排序的算法算是入门级别的，打好基础再学习更深入的算法。
前两篇文章介绍了冒泡排序和插入排序，本篇学习选择排序。
【学习分享】小白写算法之冒泡排序篇
【学习分享】小白写算法之插入排序篇

一、什么是选择排序算法

选择排序，顾名思义就是每次执行都选择一个最小（或者最大）的数，然后组成一个有序序列。

如下动图演示了选择排序算法的运行过程，比较直观。

二、选择排序算法如何实现

我们以数组{6,5,3,2,6,1}为例，每一轮所要做的事就是取出无序序列中的最小值，然后和第i轮的值进行互换，然后循环直到成为有序序列。

每一轮怎么找出最小值呢？以第2轮找2为例。

总结一下规律：
1、在第i轮需要实现将第i个数和最小数进行互换。
2、查找最小数，需要从j=i+1开始找到最后一个数。
互换的算法我们已经接触很多次了。那么实现起来就比较简单了。

三、C语言实现算法

void selectsort(int arr[],int n)   //选择排序算法
{
    int i,j,min_idx,temp;
    for(i=0;i<n-1;i++)
        {
            min_idx=i;             //标记最小值为第min_idx位，先设定为第i位为最小值。
            for(j=i+1;j<n;j++)      //从i+1开始遍历查找最小值。
		        {
                if(arr[j]<arr[min_idx])
                        min_idx = j;
		        }
            if(i!=min_idx)             //如果i不是最小位，那么第i位和第min_idx位进行互
                {
                    temp = arr[i];
                    arr[i] = arr[min_idx];
                    arr[min_idx] = temp;
                }
        }
}

加入打印后用gcc编译，结果符合预期。

四、复杂度计算

时间复杂度
跟冒泡排序和插入排序相似，时间复杂度嵌套了两次n，所以选择排序算法时间复杂度是O(n^2).

空间复杂度计算
四个临时变量i,j,min_idx,temp，所以只需要一个元素的辅助空间即可，空间复杂度为O(1)。

五、算法稳定性

算法稳定性要看相同元素是否会互换，从例子中可以看到，最小值互换后，两个6的相对位置已经发生改变。

所以选择排序是不稳定的。

六、小结

简单算法对于入门来说是很好的学习方法，只要掌握要领，算法也能变得简单易懂~~