【学习分享】小白写算法之选择排序篇
- 前言
- 一、什么是选择排序算法
- 二、选择排序算法如何实现
- 三、C语言实现算法
- 四、复杂度计算
- 五、算法稳定性
- 六、小结
前言
简单排序有三种,冒泡排序,插入排序和选择排序。这三种排序的算法算是入门级别的,打好基础再学习更深入的算法。
前两篇文章介绍了冒泡排序和插入排序,本篇学习选择排序。
【学习分享】小白写算法之冒泡排序篇
【学习分享】小白写算法之插入排序篇
一、什么是选择排序算法
选择排序,顾名思义就是每次执行都选择一个最小(或者最大)的数,然后组成一个有序序列。
如下动图演示了选择排序算法的运行过程,比较直观。
二、选择排序算法如何实现
我们以数组{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的相对位置已经发生改变。
所以选择排序是不稳定的。
六、小结
简单算法对于入门来说是很好的学习方法,只要掌握要领,算法也能变得简单易懂~~