摘要：总结排序方法，以及代码示例，主要是回顾排序算法，方便后期忘了查看

• 冒泡排序
  思路：

    俩俩交换，大的放在后面，第一次排序后最大值已在数组末尾。  
    因为俩俩交换，需要n-1趟排序，比如10个数，需要9趟排序     代码实现要点： 
    
    两个for循环，外层循环控制排序的趟数，内层循环控制比较的次数  
    每趟过后，比较的次数都应该要减1     优化：如果一趟排序后也没有交换位置，那么该数组已有序～     代码示例：  
  
    def bubble_sort(alist):
        for j in range(len(alist)-1,0,-1):
            # j表示每次遍历需要比较的次数，是逐渐减小的
            for i in range(j):
                if alist[i] > alist[i+1]:
                    alist[i], alist[i+1] = alist[i+1], alist[i]
      
    li = [54,26,93,17,77,31,44,55,20]
    bubble_sort(li)
    print(li)   最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）     最坏时间复杂度：O(n2)     稳定性：稳定  
  

• 选择排序
  思路：

    找到数组中最大的元素，与数组最后一位元素交换  
    当只有一个数时，则不需要选择了，因此需要n-1趟排序，比如10个数，需要9趟排序  
  

  代码实现要点：

    两个for循环，外层循环控制排序的趟数，内层循环找到当前趟数的最大值，随后与当前趟数组最后的一位元素交换     代码示例：  
      
    def selection_sort(alist):
        n = len(alist)
        # 需要进行n-1次选择操作
        for i in range(n-1):
            # 记录最小位置
            min_index = i
            # 从i+1位置到末尾选择出最小数据
            for j in range(i+1, n):
                if alist[j] < alist[min_index]:
                    min_index = j
            # 如果选择出的数据不在正确位置，进行交换
            if min_index != i:
                alist[i], alist[min_index] = alist[min_index], alist[i]
      
    alist = [54,226,93,17,77,31,44,55,20]
    selection_sort(alist)
    print(alist)
  

• 插入排序 思路：

    将一个元素插入到已有序的数组中，在初始时未知是否存在有序的数据，因此将元素第一个元素看成是有序的
    与有序的数组进行比较，比它大则直接放入，比它小则移动数组元素的位置，找到个合适的位置插入
    当只有一个数时，则不需要插入了，因此需要n-1趟排序，比如10个数，需要9趟排序
  

  代码实现：

    一个for循环内嵌一个while循环实现，外层for循环控制需要排序的趟数，while循环找到合适的插入位置(并且插入的位置不能小于0)
  

  代码示例：

    def insert_sort(alist):
        # 从第二个位置，即下标为1的元素开始向前插入
        for i in range(1, len(alist)):
            # 从第i个元素开始向前比较，如果小于前一个元素，交换位置
            for j in range(i, 0, -1):
                if alist[j] < alist[j-1]:
                    alist[j], alist[j-1] = alist[j-1], alist[j]
      
    alist = [54,26,93,17,77,31,44,55,20]
    insert_sort(alist)
    print(alist)
  

  最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
  最坏时间复杂度：O(n2)
  稳定性：稳定

• 快速排序

  思路：

    在数组中找一个元素(节点)，比它小的放在节点的左边，比它大的放在节点右边。一趟下来，比节点小的在左边，比节点大的在右边。
    不断执行这个操作....
  

  代码实现：

    快速排序用递归比较好写【如果不太熟悉递归的同学可到：递归就这么简单】。支点取中间，使用L和R表示数组的最小和最大位置
      
    不断进行比较，直到找到比支点小(大)的数，随后交换，不断减小范围～
      
    递归L到支点前一个元素(j)(执行相同的操作,同上)
    递归支点后一个元素(i)到R元素(执行相同的操作,同上)
  

• 归并排序 思路：

    将两个已排好序的数组合并成一个有序的数组。
      
    将元素分隔开来，看成是有序的数组，进行比较合并
    不断拆分和合并，直到只有一个元素
  

  代码实现：

    在第一趟排序时实质是两个元素(看成是两个已有序的数组)来进行合并，不断执行这样的操作，最终数组有序
    拆分左边，右边，合并...
  

• 希尔排序

  思路：

    希尔排序实质上就是插入排序的增强版，希尔排序将数组分隔成n组来进行插入排序，**直至该数组宏观上有序，**最后再进行插入排序时就不用移动那么多次位置了～
  

  代码思路：

    希尔增量一般是gap = gap / 2，只是比普通版插入排序多了这么一个for循环罢了，难度并不大