如何深度理解排序算法（一）

对于算法的理解、可以看成解决问题的过程和方式、无论算法是好还是坏，它都是一个独立的个体。在众多算法中，排序算法是经常被用到，或者在以往的生活或者面试当中会被提到的，所以理解和学会排序算法是非常重要的。

还记得上小学的时候，老师会叫我们按照身高高低，进行低的在前高的在后的原则、进行排队放学回家。那么大家思考下，如何排队是最有效的呢？！

首先，我们第一个想到的是什么呢？从第一个学生开始以此与相邻的学生进行比较，如果右边学生的身高大于左边的，就把右边的学生和左边的学生的位置调换，反之不交换位置。他的思维大概是这样的。

根据这个gif动画可以看出、它就像一个泡泡一样慢慢的往上升，这种算法就是冒泡排序，为了便于理解和加深记忆，我们以python代码来模拟下这种思路：

# 冒泡排序
def bubbleSort(sort):
    n = len(sort)
    for i in range(n):  # 获取所有的数组元素
        for j in range(0, n - i - 1):  # 最后 i 个元素已经到位
            if sort[j] > sort[j + 1]:
                sort[j], sort[j + 1] = sort[j + 1], sort[j]

    return sort

if __name__ == "__main__":
    sort = [5, 9, 3, 1, 2, 8, 4, 7, 6]
    print(bubbleSort(sort))

根据以上描述可以看出，每次循环就会以相邻的数组进行比较、如果当前数组大于相邻的数组，就把两个的位置进行交换然后返回结果。

那如果老师不喜欢这种方法呢？那我们可不可以这样做呢？重复从人员当前查找身高最小的，然后行交换位置。

根据这个规律可以看出，每次选择最小值、进行判断然后交换位置，这种算法就是选择排序。

# 选择排序
def selectSort(sort):
    n = len(sort)
    for i in range(n):
        min_num = i
        for j in range(i + 1, n):
            if sort[min_num] > sort[j]:
                min_num = j
        sort[i], sort[min_num] = sort[min_num], sort[i]

    return sort

if __name__ == "__main__":
    sort = [5, 9, 3, 1, 2, 8, 4, 7, 6]
    print(selectSort(sort))

大家可以思考下，可不可以这样做，就像我们玩扑克牌一样，从排好序的牌里去和我们抓的牌进行相比较呢？这样是不是更好呢？这种方式其实就是今天我们所说的插入排序的方法。

根据这个描述可以看出，每次从选择区去和待选择的区域进行比较、然后交换位置。

# 插入排序
def insertSort(sort):
   """
   插入排序
   :param arr: 待排序List
   :return: 插入排序是就地排序(in-place)
   """
   length = len(sort)
   if length <= 1:
       return
   for i in range(1, length):
       key = sort[i]

       j = i - 1

       while j >= 0 and sort[j] > key:
           sort[j + 1] = sort[j]
           j -= 1
       sort[j + 1] = key

   return sort


if __name__ == "__main__":
   sort = [5, 9, 3, 1, 2, 8, 4, 7, 6]
   print(insertSort(sort))

以上三种算法均是排序算法当中常用到的，或者面试中常问的算法；三个算法的时间复杂度都为O(n2),如果要想使时间更短的话，那么大家就要去考虑下其他的算法或者去了解下堆这个概念和分治思想。