《数据结构与算法》——选择排序

撰写时间：2020.5.28

                                  《数据结构与算法》——选择排序

选择排序算法，选择排序的基本思想是每一趟从代排序的记录中选出关键字最小的记录,按顺序放到已排好序的子序列中。比喻我们要从小到大排，那么这个关键字最小的记录就跟第一个记录交换 第二趟选出次小的跟第二个交换直到全部记录排序完毕,选择排序有两种直接选择排序和堆排序，下面讲选择排序。
下面看一下相应的代码,r是待排序的数列，n是n个长度，那么我们的i是我们已排好序的我们要选择的那个下标,

这时我们首先把i给过k，

k是做什么用的呢，这个地方可以看到这一个循环j是从i的下一个开始不管排序到什么位置，j一都是没排好序的,从下一个位置开始,然后一直到最后一个元素，然后如果这后边这个元素比r［k］要小，这时就说明k不在指向最小的，

k总是要当等于前最小数的下标，所以这个循环里面的判断就可以，如果r［k］一旦比r［k］大，马上修改K为小的数的下标，所以保证K都是当前最小关键字的记录的位置,如果r［k］与r［j］不相等就进行交换，这个时候就能找到他的，意思是直接选择到相应的排序位置，这就是直接选择排序，一共要进行n-1趟。在这个之前选的排序中,也是需要移动次数比较少的算法，排序树不能太多的，否则就比较复杂，他仍然是O（n²）的时间复杂度，刚才我们也看了直接选择排序是不稳定的。