Python算法题

2020-10-27

记录一些学习的算法题。推荐：十大经典排序算法

一、冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序解决了桶排序浪费空间的问题, 但是冒泡排序的效率特别低。
冒泡排序算法的运作如下：

比较相邻的元素。如果前一个比后一个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

def bubbleSort(aList):
    for i in range(len(aList)-1, 0, -1):	# i每次遍历需要比较的次数，是逐渐减小的
        for j in range(i):		# j为列表下标
            if aList[j] > aList[j+1]:
                aList[j], aList[j+1] = aList[j+1], aList[j]
    return aList

li = [54, 26, 93, 17, 77, 31, 44, 55, 20, 26, 5]
print(bubbleSort(li))

二、二分法查找

二分法可以分为三类：二分查找算法、二分排序算法、二分合并算法。
二分查找又被称为折半查找。假设我们有一个列表，要在该列表中查找某一个元素，我们需要先对该列表进行排序（假设是从小到大的排序），然后取这个列表的中值与待查找的元素进行比较，如果该元素等于中值，则查找成功；如果该元素大于中值，则接下来在右边的子表（之前二分出来的两个子表中的右边子表）中继续进行以中值为中心的折半查找；如果该元素小于中值，则在左边的子表中继续进行以中值为中心的折半查找…如此循环，直到查找到目标元素，此时查找成功，或者直到子表再也不能进行二分为止，此时查找不成功。

二分法的前提是输入的列表必须是有序的排布的，不可以是随机分布值的集合。

列表排序可以使用sorted(list)或list.sort()方法解决，假设为升序输出。

二分的查找算法的时间复杂度是O（log n)

def dichotomySearch(num, myList):
    myList = sorted(myList)
    print('排序后列表：', myList)

    first = 0
    last = len(myList) - 1
    while first <= last:
        middle = (first + last) // 2
        if myList[middle] == num:
            return middle
        elif myList[middle] > num:
            last = middle - 1
        elif myList[middle] < num:
            first = middle + 1
    return None

key = 12
list1 = [1, 5, 9, 3, 6, 12, 7, 25, 10]
result = dichotomySearch(key, list1)
if result is not None:
    print('查找的元素是', key, '对应有序列表中序号下标为：', result)
else:
    print('未找到该元素')