入门 | 经典排序算法—插入排序 & 选择排序

vlambda
2020-02-20

入门 | 经典排序算法—插入排序 & 选择排序

导语

排序是我们经常需要面临的一个命题。面对一群杂乱无章的数据，排序后不仅可以使其更具可读性，还能方便我们对其进行下一步的操作——如归类，删除，插入，搜索等。如何优化排序算法一直是计算机科学研究的重要命题。今天，我们一起来学习其中两个经典的排序算法——插入排序和选择排序吧！

插入排序

为了方便，我们接下来用对一组数字排序的过程来说明这两个算法。而事实上，排序的对象可以是任何东西，只要你提前定义好判断“大小” 的标准。

现有一组数据：

12 2 16 30 8 28 4 10 20

我们需要将这些数字从小到大排列。

插入排序的规则是，从左往右依次选择没有排序过的数字，将它放入排好序的列表中恰当的位置。当然，一开始这个所谓“排好序”的列表是空的。

对于上面这组数据，插入排序首先选择数据12，由于一开始的有序列表是空的，所以新数据直接放入有序列表中。

接着，选择数据2，当前有序列表中有数据12，所以需要把2放到12前面，这样，有序列表中的数据就变成了2 12 。这也是所谓的“插入”。

依次进行上述过程，直到原来的列表中无数可选为止。

怎么样？一旦理解这个过程，写起代码来就容易很多了：

L1=[12,2,16,30,8,28,4,10,20]  #原来的无序数组
L2=[]  #有序数组
for i in range(0,len(L1)):
    pos=-1  #记录当前数字恰当的位置
    for j in range(0,len(L2)):
        if(L2[j]>=L1[i]):
            pos=j   #记录第一个大于等于的数字位置
            break
    #开始插入
    if(pos==-1):   #如果pos==-1 说明待插入的数据是最大的
        L2.append(L1[i])  #列表的“append”方法，可以在列表末尾加上数字
        continue;

    L2.append(L2[len(L2)-1])
    for j in range(len(L2)-2,pos-1,-1):#反向遍历，移动位置
        L2[j]=L2[j-1]
    L2[pos]=L1[i]

值得注意的是，由于在计算机内部的存储逻辑中，列表中的数据是“顺序存放” 的，也就是放在一段连续的存储空间中，因此如果要实现插入，就需要把原来的数据“挪开”，给新数据腾出位置。这才有了上述代码的“移动” 过程。

显然，这并不是最优的代码。之前提到的所谓“有序数组”，也只是方便理解而建立的新数组，事实上我们并不需要专门为它开设存储空间，插入排序的过程只用原数组的情况下就能完成。同时，为当前数据遍历寻找恰当的位置的时候，我们是不是也可以同时进行相应的移动呢？这样，最后一个for循环就显得不太有必要了。

具体怎么实现，你自己思考一下吧！

选择排序

选择排序不断遍历未排序的数组，找到当前最小的数字，放入有序数组的末尾。直到所有数据都有序位置

还是上面那组数据，我们先遍历一遍，发现最小的数是2，因此将其加入有序数组末尾，此时有序数组为 2。

接着再遍历，当前最小的数是4，因此将其加入有序数组末尾，所以有序数组为 2 4

以此类推。

看起来比插入排序省事多了！代码如下：

L1=[12,2,16,30,8,28,4,10,20]  #原来的无序数组
L2=[]  #有序数组
flag=1  #标记是否所有数据都排好序了，为1表示还有未排序的数字
isvisted=-1  #标记该数字是否被访问过，若已知数据范围，可以设置数据的边界，即,"不可能出现的数字==访问过的数字"

while(flag!=0):
    flag=0
    mi=-1  #记录最小值
    miid=0
    for i in range(0,len(L1)):
        if( L1[i]!=isvisted and (mi==-1 or mi>L1[i])):
            flag=1   #能进入这一步，说明还有未访问的数字
            mi=L1[i]
            miid=i
    if(flag==0):
        break;
    L2.append(mi)
    L1[miid]=isvisted   #标记访问过的数字

这个代码有个显然的缺陷——如果不知道数据范围，则isvisted的值毫无意义，排序也就无法进行。同插入排序一样，L2数组其实也是没有必要的。事实上，由于总数据量是有限的，因此在原来的数组上，我们可以人为地划定一个有序的下标范围（当然，一开始这个范围是0到0，即空），通过数据之间的交换，使得在这个范围内的所有数据都是有序的。排序的过程中，范围逐渐扩大，直至整个数组。

如下图:

蓝色表示被选择的元素，黄色表示有序的范围。

首先选择出最小的元素2，让它和当前未排序的12交换，有序范围扩大为0到1

接着选择到4, 如法炮制:

和无序的12交换，再选择到8 ......依次类推：

以上就是使用这种思想的排序过程图。不仅节约了空间，还避免了”isvisted“所带来的局限。

思考一下怎么用代码实现吧！

关于效率的讨论

从直观上看，如果不考虑“插入” 带来的数据移动和寻找正确位置需要的遍历，其实插入排序只需要遍历一遍大数组就可以了。而选择排序，假设一共有n个元素，则需要遍历n次，当n很大时，这是无法接受的。但是选择排序的好处是，交换次数最少，所得到的数据一开始就在正确的位置（总在有序段的末端），若交换数据需要的代价更大时，可以考虑选择排序。

自己去尝试实现吧！