[TOC]

搜索

搜索是指从元素集合中找到某个特定元素的算法过程。搜索过程通常返回True或False，分别表示元素是否存在。有时，可以修改搜索过程，使其返回目标元素的位置。

顺序搜索

存储于列表等集合中的数据项彼此存在线性或顺序的关系，每个数据项的位置与其他数据项相关。

在Python列表中，数据项的位置就是它的下标。因为下标是有序的，所以能够顺序访问，由此可以进行顺序搜索。(遍历)

image-20230907164034879

无序列表的顺序搜索

1
2
3
4
5
6
7
8
9
10
def sequentialSearch(iters,item):
    found = False

    for i in iters:
        if i == item:
            # return found := True
            # 海象表达式，它可以在条件语句、循环语句等场景下使用，但不能直接与返回语句结合。
            found = True
            return found
    return found

有序列表的顺序搜索

假设列表中的元素按升序排列。如果存在目标元素，那么它出现在n个位置中任意一个位置的可能性仍然一样大，因此比较次数与在无序列表中相同。

如果不存在目标元素，那么搜索效率就会提高

1
2
3
4
5
6
7
8
9
10
def orderSequentialSearch(iters,item):
    found = False
    for i in iters:
        if i == item:
            found = True
            break
        if i > item:
            break

    return found

二分搜索

有序列表的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binarySearch(iters,item):
    found = False
    front = 0
    after = len(iters) - 1

    while found != True and after>=front:
        middle = (after + front) // 2
        if iters[middle] == item:
            found = True
        elif iters[middle] < item:
            front = middle+1
        else:
            after = middle-1
    return found

有序列表的二分搜索：递归

1
2
3
4
5
6
7
8
9
10
11
def recurBinarySearch(iters,item):
    middle = len(iters)//2
    if iters[middle] == item:
        return True
    elif len(iters) == 1:
        return iters[0] == item
    else:
        if iters[middle] < item:
            return recurBinarySearch(iters[middle:],item)
        else:
            return recurBinarySearch(iters[:middle-1],item)

尽管二分搜索通常优于顺序搜索，但当n较小时，排序引起的额外开销可能并不划算

如果排序一次后能够搜索多次，那么排序的开销不值一提。

排序

冒泡排序

冒泡排序多次遍历列表。它比较相邻的元素，将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。

image-20230910013814329 
1
2
3
4
5
6
7
8
def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                # temp = alist[i]
                # alist[i] = alist[i+1]
                # alist[i+1] = temp
                alist[i],alist[i+1] = alist[i+1],alist[i]

冒泡排序通常被认为是效率最低的排序算法，因为在确定最终的位置前必须交换元素。

短冒泡：如果在一轮遍历中没有发生元素交换，就可以确定列表已经有序。可以修改冒泡排序函数，使其在遇到这种情况时提前终止。

1
2
3
4
5
6
7
8
9
10
def shortBubbleSort(alist):
    exchanges = False
    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]
        passnum -= 1

选择排序

选择排序在冒泡排序的基础上做了改进，每次遍历列表时只做一次交换。要实现这一点，选择排序在每次遍历时寻找最大值，并在遍历完之后将它放到正确位置上。

image-20230910041324949 
1
2
3
4
5
6
7
8
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]

选择排序算法和冒泡排序算法的比较次数相同，所以时间复杂度也是O( 2n )。但是，由于减少了交换次数，因此选择排序算法通常更快。

插入排序

插入排序的时间复杂度也是O(n2)，但原理稍有不同。它在列表较低的一端维护一个有序的子列表，并逐个将每个新元素“插入”这个子列表。

image-20230910034852669 
1
2
3
4
5
6
7
8
9
10
def insertionSort(alist):
    for index in range(1,len(alist)):
        currentValue = alist[index]
        positon = index

        while positon > 0 and alist[positon-1] > currentValue:
            alist[positon] = alist[positon-1]
            positon = positon - 1

        alist[positon] = currentValue

总体来说，交换操作的处理时间大约是移动操作的3倍，因为后者只需进行一次赋值

希尔排序

插入排序对于接近有序的序列和小序列更加高效

所以希尔排序核心就是降大序列分为若干小序列进行排序

希尔排序也称“递减增量排序”，它对插入排序做了改进，将列表分成数个子列表，并对每一个子列表应用插入排序。

如何切分列表是希尔排序的关键——并不是连续切分，而是使用增量i（有时称作步长）选取所有间隔为i的元素组成子列表。

  1. 切分
image-20230910050742016
  1. 子列表排序，多次
image-20230910050840423
  1. 总体插入排序
image-20230910050927563 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:
        for startpoint in range(sublistcount):
            getInsertionSort(alist,startpoint,sublistcount)

        sublistcount = sublistcount//2

def getInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):
        currentValue = alist[i]
        position = i
        for j in range(i-gap,-1,-gap):
            if alist[j] > currentValue:
                alist[j+gap] = alist[j]
                position = position-gap
            else:
                break
        alist[position] = currentValue

归并排序

归并排序，它是递归算法，使用分治策略改进排序算法

每次将一个列表一分为二。如果列表为空或只有一个元素，那么从定义上来说它就是有序的（基本情况）

如果列表不止一个元素，就将列表一分为二，并对两部分都递归调用归并排序。当两部分都有序后，就进行归并这一基本操作

image-20230910133308726 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def mergeSort(alist):
    print("Splitting", alist)
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i = 0
        j = 0
        k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1

        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i += 1
            k += 1

        while j < len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1

    print("Merging",alist)

需要进行logn次拆分，每一次需要进行n次操作，所以一共是nlogn次操作。也就是说，归并排序算法的时间复杂度是O(nlogn)。

mergeSort函数需要额外的空间来存储切片操作得到的两半部分。当列表较大时，使用额外的空间可能会使排序出现问题。

快速排序

快速排序也采用分治策略，但不使用额外的存储空间，代价是算法的效率会有所下降

  1. 首先选出一个基准值：基准值的位置通常被称作分割点，算法在分割点切分列表，以进行对快速排序的子调用。

  2. 分区：通过分割点，将其他元素放到一边——要么大于基准值，要么小于基准值。

    image-20230910194533426
    1. 针对左右两部分递归调用快速排序函数
image-20230910200059540

最坏情况下，分割点不在列表的中部，而是偏向某一端，这会导致切分不均匀。这会导致时间复杂度变为O( 2n )，因为还要加上递归的开销。

可以通过多种选择基准值的方法。尝试使用三数取中法避免切分不均匀，即在选择基准值时考虑列表的头元素、中间元素与尾元素。

总结

  • 不论列表是否有序，顺序搜索算法的时间复杂度都是O(n)。
  • 对于有序列表来说，二分搜索算法在最坏情况下的时间复杂度是O(logn)。
  • 基于散列表的搜索算法可以达到常数阶。
  • 冒泡排序、选择排序和插入排序都是O(n^2)算法。
  • 希尔排序通过给子列表排序，改进了插入排序。它的时间复杂度介于O(n)和O(n^2)之间。
  • 归并排序的时间复杂度是O(nlogn)，但是归并过程需要用到额外的存储空间。
  • 快速排序的时间复杂度是O(nlogn)，但当分割点不靠近列表中部时会降到O( n^2 )。它不需要使用额外的存储空间。