Python3算法实例 2：排序算法示例+代码

pythonfan.png

1、插入排序

1.1 直接插入

• 原理
  每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。具体方法是第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
• 示例
  待排序数组：{6, 5, 3, 1, 8, 7, 2, 4, 9, 0}
  i=1： 5 {5, 6, 3, 1, 8, 7, 2, 4, 9, 0}
  i=2： 3 {3, 5, 6, 1, 8, 7, 2, 4, 9, 0}
  i=3： 1 {1, 3, 5, 6, 8, 7, 2, 4, 9, 0}
  i=4： 8 {1, 3, 5, 6, 8, 7, 2, 4, 9, 0}
  i=5： 7 {1, 3, 5, 6, 7, 8, 2, 4, 9, 0}
  i=6： 2 {1, 2, 3, 5, 6, 7, 8, 4, 9, 0}
  i=7： 4 {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}
  i=8： 9 {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}
  i=9： 0 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• Python3代码

 # 直接插入排序
 def Insert(listdata):
     for i in range(1, len(listdata)):
         # 设置当前值前一个元素的标识
         j = i - 1
         # 如果当前值小于前一个元素,则将当前值作为一个临时变量存储,将前一个元素后移一位
         if listdata[i] < listdata[j]:
             temp, listdata[i] = listdata[i], listdata[j]
             # 继续往前寻找,如果有比临时变量大的数字,则后移一位,直到找到比临时变量小的元素或者达到列表第一个元素
             j = j - 1
             while j >= 0 and listdata[j] > temp:
                 listdata[j + 1] = listdata[j]
                 j = j - 1
             # 将临时变量赋值给合适位置
             listdata[j + 1] = temp
     return listdata

1.2 希尔

• 原理
  将待排序列划分(根据增量或者步长)为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排。增量的选取会影响算法的时间复杂度。
• 示例
  待排序数组：{6, 5, 3, 1, 8, 7, 2, 4, 9, 0}
  第一次步长h=4，那么数组按照步长可以拆分成4个小数组（[0]6的意思是下标[0]的值为6）
  {[0]6, [4]8, [8]9}
  {[1]5, [5]7, [9]0}
  {[2]3, [6]2}
  {[3]1, [7]4}
  对这4个小数组分别进行插入排序后，4个小数组变成：
  {[0]6, [4]8, [8]9}
  {[1]0, [5]5, [9]7}
  {[2]2, [6]3}
  {[3]1, [7]4}
  合并起来就是：{6, 0, 2, 1, 8, 5, 3, 4, 9, 7}
  第二次步长h=1，那么数组按照步长只有1个数组了{6, 0, 2, 1, 8, 5, 3, 4, 9, 7}
  对这个数组进行一次插入排序后，最终顺序就成为：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• Python3代码

# 希尔排序
def Shell(listdata):
    n = len(listdata)
    # 希尔增量
    gap = int(n / 2)
    while gap > 0:
        # 按增量进行直接插入排序
        for i in range(gap, n):
            j = i
            # 直接插入排序
            while j >= gap and listdata[j - gap] > listdata[j]:
                listdata[j - gap], listdata[j] = listdata[j], listdata[j - gap]
                j -= gap
        # 得到新的增量
        gap = int(gap / 2)
    return listdata

image

2、选择排序

2.1直接选择

• 原理
  从待排序序列中，找到关键字最小的元素；如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；从余下的 N - 1 个元素中，找出关键字最小的元素，重复1，2步，直到排序结束。
• 示例
  待排序数组：{6, 5, 3, 1, 8, 7}
  i=1： {1, 5, 3, 6, 8, 7} 最小值1，交换6和1
  i=2： {1, 3, 5, 6, 8, 7} 最小值3，交换5和3
  i=3： {1, 3, 5, 6, 8, 7} 最小值5，无需交换
  i=4： {1, 3, 5, 6, 8, 7} 最小值6，无需交换
  i=5： {1, 3, 5, 6, 7, 8} 最小值7，交换7和8
  i=6： {1, 3, 5, 6, 7, 8} 最小值8，无需交换，结束排序
• Python3代码

# 直接选择排序
def Select(listdata):
    for i in range(len(listdata) - 1):
        minnum = i
        for j in range(i + 1, len(listdata)):
            if listdata[j] < listdata[minnum]:
                minnum = j
        listdata[i], listdata[minnum] = listdata[minnum], listdata[i]
    return listdata

2.2 堆

• 原理
  堆分为最大堆和最小堆，其实就是完全二叉树。最大堆：父节点的值都不小于子节点的值，最小堆：父节点的值都不大于子节点的值。每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆(升序)或者最小堆(降序)，依次类推，最终得到排序的序列。
  1， 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
  2， 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn)；
  3， 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成；
• 示例
  待排序数组{7, 13, 2, 9, 15}，升序
  1，生成最大堆
  image

2，互换——生成最大堆 重复

image

排序结果{2, 7, 9, 13, 15}

• Python3代码

 # 堆排序
 def adjust_heap(lists, i, size):
     lchild = 2 * i + 1
     rchild = 2 * i + 2
     max = i
     if i < size / 2:
         if lchild < size and lists[lchild] > lists[max]:
             max = lchild
         if rchild < size and lists[rchild] > lists[max]:
             max = rchild
         if max != i:
             lists[max], lists[i] = lists[i], lists[max]
             adjust_heap(lists, max, size)
 
 # 创建堆
 def build_heap(lists, size):
     for i in range(0, (int(size/2)))[::-1]:
         adjust_heap(lists, i, size)
 
 # 堆排序
 def Heap(lists):
     size = len(lists)
     build_heap(lists, size)
     for i in range(0, size)[::-1]:
         lists[0], lists[i] = lists[i], lists[0]
         adjust_heap(lists, 0, i)
     return lists

image

3、交换排序

3.1 冒泡

• 原理
  临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样遍历过一次数组后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束排序。
• 示例
  待排序数组{8，6，9，3}，升序
  第一次遍历(外循环)

第1次两两比较8 > 6，需要交换(内循环)：交换前状态{8，6，9，3}交换后状态{6，8，9，3}
第2次两两比较8 < 9，不需要交换(内循环)：状态{6，8，9，3}
第3次两两比较9 > 3，需要交换(内循环)：交换前状态{6，8，9，3}交换后状态{6，8，3，9}
结束比较

第二次遍历(外循环)

第1次两两比较6 < 8，不需要交换(内循环)：状态{6，8，3，9}
第2次两两比较8 > 3，需要交换(内循环)：交换前状态{6，8，3，9}交换后状态{6，3，8，9}
结束比较

第三次遍历(外循环)

第1次两两比较6 > 3，需要交换(内循环)：交换前状态{6，3，8，9}交换后状态{3，6，8，9}
结束比较

第四次遍历(外循环)

无交换，结束内循环

结束外循环遍历，排序结束

• Python3代码

# 冒泡排序
def Bubble(listdata):
    for i in range(len(listdata) - 1):  # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(listdata) - i - 1):  # ｊ为列表下标
            if listdata[j] > listdata[j + 1]:
                listdata[j], listdata[j + 1] = listdata[j + 1], listdata[j]
    return listdata

3. 2 快速

• 原理
  先从数列中取出一个数作为基准数，分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边，再对左右区间重复第二步，直到各区间只有一个数。
• 示例
  待排序数组：{4, 5, 3, 1, 7, 6, 2}
  第1次：

基准数=6，首先，用两个变量 i 和 j 从数组两边开始向中间扫描，i 向右走，j 往左走；
i 往右走，直到遇见不小于基准数的值停止移动 5。 j 向左走，直到遇见不大于基准数的值停止移动 2，交换两个值的位置 {4, 2, 3, 1, 7, 6, 5}；
i，j继续移动，i停在1，j和i相遇，停止移动，1和基准数互换位置，{1, 2, 3, 4, 7, 6, 5}；

第2次：

待排序数组： {1, 2, 3} 基准数1；{7, 6, 5} 基准数7。重复上面操作

• Python3代码

# 快速排序
def Quick(listdata):
    if len(listdata) == 0:
        return []
    pivots = [x for x in listdata if x == listdata[0]]
    lesser = Quick([x for x in listdata if x < listdata[0]])
    greater = Quick([x for x in listdata if x > listdata[0]])
    return lesser + pivots + greater

image

4、归并排序

4. 1 归并

• 原理
  该算法采用经典的分治(divide-and-conquer)策略，将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。
• 示例
  待排序数组：{4, 5, 3, 1, 7, 6, 2, 9}

分

image

治

image

• Python3代码

 # 归并排序
 def Merge(listdata):
     n = len(listdata)
 
     if n == 1:
         return listdata
     mid = n // 2
 
     # 对分割的左半部分进行归并排序
     leftdata = Merge(listdata[:mid])
     # 对分割的右半部分进行归并排序
     rightdata = Merge(listdata[mid:])

     # 对排序之后的两部分进行合并
     # 定义两个游标
     left, right = 0, 0
 
     merge_result_li = []
     left_n = len(leftdata)
     right_n = len(rightdata)
 
     while left < left_n and right < right_n:
         if leftdata[left] <= rightdata[right]:
             merge_result_li.append(leftdata[left])
             left += 1
         else:
             merge_result_li.append(rightdata[right])
             right += 1
 
     merge_result_li += leftdata[left:]
     merge_result_li += rightdata[right:]

     # 将合并后的结果返回
     return merge_result_li

image

5、分配排序

5. 1 基数

• 原理
  基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：分配，先从个位开始，根据个位值(0-9)分别放到0至9号桶中（比如53,个位为3，则放入3号桶中)；收集，再将放置在0至9号桶中的数据按顺序放到数组中。从最低位到最高位重复分配与收集过程。

• 示例
  待排序数组：{4561, 349, 78, 12, 201, 9, 3208}
  

  image

• Python3代码

# 基数排序
def Radix(listdata):
    k = len(str(max(listdata)))  # k获取最大位数
    for k in range(k):  # 遍历位数，从低到高
        s = [[] for i in range(10)]  # 生成存放数的十个桶
        for i in listdata:  # 遍历元素
            s[i // (10 ** k) % 10].append(i)  # 分配
        listdata = [a for b in s for a in b]  # 收集
    return listdata

image

不同算法之间的对比：

pythonfan.png

点击获得生成上面图片的代码

image image

扫描下方二维码或者微信公众号直接搜索”Python范儿“，关注微信公众号pythonfan， 获取更多实例和代码。

pythonfan.jpg