python数据结构教程 Day8

本节重点

1. 查找
2. 排序（部分）

一、查找

1、顺序查找

条件：

• 数据项保存在如列表这样的集合中， 我们会称这些数据项具有线性或者顺序关系。
• 通过下标，我们就可以按照顺序来访问和 查找数据项。

查找过程：

先从列表的第1个数据项开始，按照下标增长的顺序，逐个比对数据项，如果到最后一个都未发现要查找的项，那么查找失败，时间复杂度为O(n)。

# 无序表顺序查找
def sequentialSearch(alist, item):
    '''
    顺序查找
    '''
    position = 0
    found = False
    while position < len(alist) and not found:
        if alist[position] == item:
            found = True
        else:
            position = position + 1
    return found

# 有序表顺序查找
def sequential_Search_OrderList(alist,target):
    pos = 0
    found = False
    for item in alist:
        if item > target:
            return found
        elif item == target:
            return True

注意：有序表与无序表相比，只是在数据项不存在的时候，有序表的查找能节省一些比对次数，但并不改变其数量级，仍然是O(n)。

我们能不能继续降低这个时间复杂度？

2、二分查找

考虑有序表的情况，因为有序表的结构更容易让我们进行优化。

如果列表中间的项匹配查找项，则查找结束
如果不匹配，那么就有两种情况：
    if 列表中间项比查找项大:
        那么查找项只可能出现在前半部分
    if 列表中间项比查找项小:
        那么查找项只可能出现在后半部分
继续采用上面的方法查找

无论如何，我们都会将比对范围缩小到原来的一半：n/2。

实现：

def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found

二分查找也是应用了分治思想的一种方法，每次在左或右半部分进行查找。

由于是分治法，自然也可以用递归进行实现：

def binarySearch(alist, item):
    if len(alist) == 0: # 基本结束条件
        return False
    else:
        midpoint = len(alist) // 2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch(alist[:midpoint], item)
            else:
                return binarySearch(alist[midpoint+1:], item)

但本算法中除了比对，还有一个因素需要注意到：binarySearch(alist[:midpoint],item)。这个递归调用使用了列表切片，而切片操作的复杂度是O(k)，这样会使整个算法的时间复杂度稍有增加；当然，我们采用切片是为了程序可读性更好，实际上也可以不切片，而只是传入起始和结束的索引值即可，这样就不会有切片的时间开销了。根据比对的次数，得出二分查找的复杂度O(log n)

看上去二分查找比顺序查找效率高，但是这是在有序表的基础上得出的结论，排序本身的时间复杂度没有被考虑，它又是怎么样的呢？

二、排序

1、冒泡排序

算法思路：

对无序表进行多趟比较交换，每趟包括了多次两两相邻比较，并将逆序的数据项互换位置，最终能将本趟的最大项就位，经过n-1趟比较交换，实现整表排序。

第1趟比较交换，共有n-1对相邻数据进行比较 。一旦经过最大项，则最大项会一路交换到达最后 一项。

第2趟比较交换时，最大项已经就位，需要排序的数据减少为n-1，共有n-2对相邻数据进行比较。

直到第n-1趟完成后，最小项一定在列表 首位，就无需再处理了。

def bubbleSort(alist):
    for passnum in range(len(alist) - 1,0,-1):
        for i in range(passnum):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i] #python支持直接交换

比对操作的时间复杂度是O(n²)，交换次数的时间复杂度也为O(n²)。

缺点与优势：

必须要经过多次比对和交换，其中大部分的操作是无效的。但有一点优势，就是无需任何额外的存储空间开销。

性能改进：

通过监测每趟比对是否发生过交换 ，可以提前确定排序是否完成。如果某趟比对没有发生任何交换，说明列表已经排好序，可以提前结束算法。

def shortbubbleSort(alist):
    exchanges = True
    passnum = len(alist) - 1
    while passnum > 0 and exchanges:
        exchanges = False
        for i in range(passnum):
            if alist[i] < alist[i+1]:
                exchanges = True
                alist[i], alist[i + 1] = alist[i + 1], alist[i] #python支持直接交换
        passnum = passnum - 1

2、选择排序

算法思路：

选择排序对冒泡排序进行了改进，保留了 其基本的多趟比对思路，每趟都使当前最大项就位。但选择排序对交换进行了削减，相比起冒泡排序进行多次交换，每趟仅进行1次交换，记录最大项的所在位置，最后再跟本趟最后一项交换。

算法性能：

比对次数不变，还是O(n²)，交换次数则减少为O(n)。

实现：

def selectionSort(alist):
    for fillslot in range(len(alist) - 1,0 ,-1):
        positionOfMax = 0
        for location in range(1,fillslot+1): # 找最大值的范围在慢慢向前缩短，因为最大值已经在上一轮固定在对应位置
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        alist[fillslot],alist[positionOfMax] = alist[positionOfMax], alist[fillslot] # 找到最大值之后，直接交换

3、插入排序

算法思路：

插入排序维持一个已排好序的子列表，其位置始终在列表的前部，然后逐步扩大这个子列表直到全表。

第1趟，子列表仅包含第1个数据项，将第2个数据项作为“新项”插入到子列表的合适位置中，这样已排序的子列表就包含了2个数据项。

第2趟，再继续将第3个数据项跟前2个数据项比对，并向后移动比自身大的数据项，空出位置来，以便加入到子列表中。

经过n-1趟比对和插入，子列表扩展到全表，排序完成。

算法性能：

总比对次数与冒泡排序相同，数量级仍是O(n²)，只有最好的情况下为O(n)。由于移动操作仅包含1次赋值，是交换操作的1/3，所以插入排序性能会较好一些。

4、希尔排序：

算法思路：

谢尔排序以插入排序作为基础，对无序表进行“间隔”划分子列表，每个子列表都执行插入排序。这样做的依据是注意到插入排序的比对次数，在最好的情况下是O(n)，这种情况发生在列表已是有序的情况下，实际上，列表越接近有序，插入排序的比对次数就越少。

随着子列表的数量越来越少，无序表的整体越来越接近有序，从而减少整体排序的比对次数。最后一趟是标准的插入排序，但由于前面几趟已经将列表处理到接近有序，这一趟仅需少数几次移动即可完成。

子列表的间隔一般从n/2开始，每趟倍增：n/4, n/8……直到1

实现：

def shellSort(alist):
    sublistcount = len(alist)//2 # 间隔设定
    while sublistcount > 0:
        for startposition in range(sublistcount): # 子列表排序
            gapInsertionSort(alist,startposition,sublistcount)
        sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap): # 对子列表执行的是插入排序
    for i in range(start+gap,len(alist),gap):
        currentvalue = alist[i]
        position = i
        while position>=gap and alist[position-gap]>currentvalue: # 后移大于目标值的元素
            alist[position] = alist[position - gap]
            position = position - gap
        alist[position] = currentvalue

算法性能：

对谢尔排序的详尽分析比较复杂，大致说是介于O(n)和O(n2)之间。如果将间隔保持在2k-1(1、3、5、7、15、31等等），谢尔排序的时间复杂度约为O(n^3/2)