python基础——15.十大排序算法&九九乘法表

本文主要是介绍python基础——15.十大排序算法&九九乘法表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 九九乘法表

        	for i in range(1, 10):
        	    for j in range(1, i+1):
        		print("{}*{}={}".format(j, i, i*i), end="\t")
        	    print("")
  

• 一句代码写九九乘法表

        print("\n".join([" ".join(["{}*{}={}".format(j, i, format(i*j, "<3d")) for j in range(1, i+1)]) for i in range(1, 10)]))
  

• 冒泡排序

   def bubbleSort(lst):
   
       for i in range(0, len(lst)-1):
   
           result = False
   
           for j in range(0, len(lst)-1-i):
   
               if lst[j] > lst[j+1]:
   
                   lst[j], lst[j+1] = lst[j+1], lst[j]
   
                   result = True
   
           if not result:
               return lst
   
       return lst
   
   print(bubbleSort(lst))
  

算法分析

冒泡排序是一种简单直接暴力的排序算法，为什么说它暴力？因为每一轮比较可能多个元素移动位置，而元素位置的互换是需要消耗资源的，所以这是一种偏慢的排序算法，仅适用于对于含有较少元素的数列进行排序。

稳定性：我们从代码中可以看出只有前一个元素大于后一个元素才可能交换位置，所以相同元素的相对顺序不可能改变，所以它是稳定排序

比较性：因为排序时元素之间需要比较，所以是比较排序

时间复杂度：因为它需要双层循环n*(n-1))，所以平均时间复杂度为O(n^2)

空间复杂度：只需要常数个辅助单元，所以空间复杂度为O(1)，我们把空间复杂度为O(1)的排序成为原地排序（in-place）

记忆方法：想象成气泡，一层一层的往上变大

• 选择排序

   lst = [4, 5, 3, 2, 6, 1, 8, 9]
  
   def SelectionSort(lst):
  
       for i in range(len(lst)-1):
  
           lst_min_index = i
  
           print("第{}个数作为最小数".format(i))
   
           for j in range(i+1, len(lst)):
   
               if lst[j] < lst[lst_min_index]:
   
                   print("第{}个数比第{}个数小".format(j, i))
   
                   lst_min_index = j
   
                   print("第{}个数替换第{}个数作为最小数".format(j, i))
   
           if i != lst_min_index:
  
               print("第{}个数替换第{}个数变为最小数".format(lst_min_index, i))
  
               lst[lst_min_index], lst[i] = lst[i], lst[lst_min_index]
   
       return lst
  
   print(SelectionSort(lst))
  

算法分析

选择排序和冒泡排序很类似，但是选择排序每轮比较只会有一次交换，而冒泡排序会有多次交换，交换次数比冒泡排序少，就减少cpu的消耗，所以在数据量小的时候可以用选择排序，实际适用的场合非常少。

比较性：因为排序时元素之间需要比较，所以是比较排序

稳定性：因为存在任意位置的两个元素交换，比如[5, 8, 5, 2]，第一个5会和2交换位置，所以改变了两个5原来的相对顺序，所以为不稳定排序。

时间复杂度：我们看到选择排序同样是双层循环n*(n-1))，所以时间复杂度也为：O(n^2)

空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)

记忆方法：选择对象要先选最小的，因为嫩，哈哈

• 插入排序

   lst = [5, 4, 3, 2, 6, 1, 8, 9]
   
   
   def insertionSort(lst):
   
       for i in range(1, len(lst)):
   
           # 要插入的数, range从1开始，就是第2个数是要插入的数
   
           current = lst[i]
   
           current_index = i
   
           # 要比较的数是要插入的数的前一个数, 这里就是从0个开始
   
           present_index = i - 1
   
   
           while present_index >= 0 and lst[present_index] > current:
   
               """
               比较的数大于要插入的数,那么把比较的数赋值给下一个数
               
               往前再选择下一个比较的数,第一个循环比较的是第0个数，
               
               前边无数了，present_index - 1 = -1了, 不会再比, 跳出当前循环
               
               """
   
               lst[present_index+1] = lst[present_index]
   
               present_index -= 1
   
           # 这一步要+1的原因是上一步多减了一个1，其实结果是把第1个元素的值赋值给第0个元素了
   
           lst[present_index + 1] = current
   
           # 到这里第1个元素和第0个元素比完了, 要从2个元素开始比了
   
       return lst
   
   
   print(insertionSort(lst))
  

算法分析

插入排序的适用场景：一个新元素需要插入到一组已经是有序的数组中，或者是一组基本有序的数组排序。

比较性：排序时元素之间需要比较，所以为比较排序

稳定性：从代码我们可以看出只有比较元素大于当前元素，比较元素才会往后移动，所以相同元素是不会改变相对顺序

时间复杂度：插入排序同样需要两次循坏一个一个比较，故时间复杂度也为O(n^2)

空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)

记忆方法：想象成在书架中插书：先找到相应位置，将后面的书往后推，再将书插入

• 希尔排序

   def shellSort():
  
   	gap = len(lst) // 2
  
   	while gap > 0:
  
   		for i in range(gap, len(lst)):
  
   			j = i
  
   			current = lst[i]
  
  
   			while j - gap >= 0 and current < lst[j - gap]:
  
   				lst[j] = lst[j-gap]
  
   				j -= gap
  
   			lst[j] = current
  
   		gap //= 2
  
   	return lst
  

算法分析

比较性：排序时元素之间需要比较，所以为比较排序

稳定性：因为希尔排序是间隔的插入，所以存在相同元素相对顺序被打乱，所以是不稳定排序

时间复杂度： 最坏时间复杂度O(n2)平均复杂度为O(n1.3)

空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)

记忆方法：插入排序是每轮都是一小步，希尔排序是先大步后小步，它第一个突破O(n2)的排序算法。联想起阿姆斯特朗登月之后说：这是我个人一小步，却是人类迈出的一大步。

这篇关于python基础——15.十大排序算法&九九乘法表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！