本专栏内容为：八大排序汇总 通过本专栏的深入学习，你可以了解并掌握八大排序以及相关的排序算法。
💓博主csdn个人主页：小小unicorn
⏩专栏分类：八大排序汇总
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识
前言：
爱炒股票短线的人，总是喜欢不断地买进卖出，想通过价差来实现盈利。但通常这种频繁操作的人，即使失误不多，也会因为操作的手续费和印花税过高而获利很少。
还有一种做股票的人，他们很少出手，只是在不断地观察和判断，等到时机一到，果断买进或卖出。他们因为冷静和沉着，以及交易的次数少，而最终收益颇丰。
冒泡排序的思想就是不断地在交换，通过交换完成最终的排序，这和做股票短线频繁操作的人是类似的。我们可不可以像只有在时机非常明确到来时才出手的股票高手一样，也就是在排序时找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序定位工作呢?这就是选择排序法的初步思想。
选择排序的基本思想是每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列的第个记录。我们这里先介绍的是简单选择排序法。
简单选择排序算法
简单选择排序算法
简单选择排序法(Simple Selection Sort)就是通过n -i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第(1<=i<=n)个记录交换.
注意：排序用到的结构与函数在第一部分：排序的基本概念与分类。我们已经实现。详情请点击：八大排序（一）--------排序的基本概念与分类
我们来看代码:
void Selectsort(SqList*L) { int i, j, min; for (i = 1; i <= L->length; i++) { min = i;/*将当前下标定义为最小值下标 */ for (j = i+1; j <= L->length; j++)/* 循环之后的数据 */ { if (L->r[min] > L->r[j])/* 如果有小于当前最小值的关键字 */ min = j;/* 将此关键字的下标赋值给min */ } if (i != min)/*若min不等于i，说明找到最小值，交换 */ { swap(L, i, min);/*交换L->r[i]与L->r[min]的值 */ } } }
代码应该说不难理解，针对待排序的关键字序列是{9,1,5,8,3,7,4,6,2},对i从1循环到8。
当i=1时，L.r[i]=9，min开始是1，然后与j=2到9比较L.r[min]与L.r[j]的大小，因为j=2时最小，所以min=2。最终交换了L.r[2]与L.r[1]的值。如下图所示，注意，这里比较了8次，却只交换数据操作一次。
当i2时，L.r[i]=9，min开始是2，经过比较后，min=9，交换L.r[min]与L.r[i]的值。如下图所示，这样就找到了第2位置的关键字。
当i=3时，L.r[i]=5，min开始是3，经过比较后，min=5，交换L.r[min]与L.r[i]的值。如下图所示。
之后的数据比较和交换完全雷同，最多经过8次交换，就可完成排序工作。
简单选择排序复杂度分析
从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少,这样也就节约了相应的时间。
分析它的时间复杂度发现，无论最好最差的情况，其比较次数都是一样的多，第i趟排序需要进行n-i次关键字的比较,因而需要比较∑ i = 2 n ( n − i ) = n + n − 1 + . . . + 2 = n ( n − 1 ) / 2 \sum_{i=2}^n (n-i)=n+n-1+...+2=n(n-1)/2∑i=2n(n−i)=n+n−1+...+2=n(n−1)/2次。
而对于交换次数而言，当最好的时候，交换为0次，最差的时候，也就初始降序时，交换次数为n-1次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度依然为O(n2)。
应该说，尽管与冒泡排序同为O(n2)，但简单选择排序的性能上还是要略优于冒泡排序。
