Python Chapter 10: 列表 Part3

标签：hex   inter   0.12   window   运行   return   效率   pack   oop   

10.10 查找列表

）线性查找

线性查找顺序地将关键字key与列表中的每一个元素进行比较，直到找到某个匹配元素时返回其下标，亦或在找不到时返回-1。代码如下：

# The function for finding a key in a list
def linearSearch(lst, key):
    for i in range(len(lst)):
        if lst[i] == key:
            return i

    return -1

若关键字存在，线性查找在找到关键字前平均需要查找一半的元素，其运行时间与列表中的元素个数成正比（时间复杂度为O(n)?）。这样的效率十分低下。

）二分查找

在保证关键字是升序排序的基础上，使用二分查找效率很高。其核心在于若关键字比中间的元素大，则仅在中间元素右边寻找，即更新low = mid + 1；若关键字比中间元素小，则仅在中间元素左边寻找，所以更新high = mid - 1；若关键字与中间元素一样大，则找到结果mid。不断循环，若最后有high > mid，则表示找不到关键字元素，则返回-low-1标记关键字应当被放置的位置。代码如下：

# Use binary search to find key in the list
def binarySearch(lst, key):
    low = 0
    high = len(lst) - 1

    while high >= low:
        mid = (low + high) // 2
        if key 

此算法的时间复杂度为O(logn)，比起线性查找高效很多，但前提是保证列表中的元素已经有序。

10.11 排序列表

）选择排序

选择排序的核心思想是，在每一次循环中找列表中最小元素与当前的第一个元素交换位置，然后再对剩余列表往复此操作，从而达到使列表中元素升序排列的目的。代码如下：

# The function for sorting elements in ascending order
def selectionSort(lst):
    for i in range(len(lst)-1):
        currentMin = lst[i]
        currentMinIndex = i

        for j in range(i + 1, len(lst)):
            if lst[j] 

选择排序的平均时间复杂度为O(n2)

） 插入排序

插入排序的核心思想是，在每一次循环中将一个新的元素插入到已经排好序的列表中，再对剩余元素往复此操作，从而达到使列表中元素升序排列的目的。代码如下：

# The function for sorting elements in ascending order
def insertionSort(lst):
    for i in range(1, len(lst)):
        currentElement = lst[i]
        k = i - 1
        while k >= 0 and lst[k] > currentElement:
            lst[k+1] = lst[k]
            k -= 1
        lst[k+1] = currentElement

此算法的时间复杂度亦为O(n2)，但其并不是每次都几乎遍历整个列表，因此在常数上会比选择排序略小。
排序的算法还有冒泡排序、快速排序、堆排序等等，这里仅举例实现。

10.12 实例学习：弹球

在屏幕上使一系列弹球运动，并通过按钮使增加一个弹球或减少一个弹球，弹球以列表的形式储存，代码如下：

from tkinter import *
from random import randint

def getRandomColor():
    color = "#"
    for j in range(6):
        color += toHexChar(randint(0,15))
    return color

def toHexChar(hexValue):
    if 0  self.width or ball.x  self.height or ball.y 

Python Chapter 10: 列表 Part3

标签：hex   inter   0.12   window   运行   return   效率   pack   oop   

原文地址：https://www.cnblogs.com/fsbblogs/p/9742280.html