python数据结构——(5)查找与排序

2021/7/15 1:05:00

本文主要是介绍python数据结构——(5)查找与排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

查找

  • 顺序查找
    顺序查找,就是从列表List[0]开始,逐个比对item与List[n]的大小,直到找到item。找不到则返回False。

无序表实现代码:

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

有序表实现代码:

# 有序表查找
def orderSeqentialSearch(alist, item):
    pos = 0
    found = False
    stop = False
    
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos += 1
    return found
  • 二分查找
    二分法利用的是有序表的特性。从数据的中间一项分为左、右两个部分,如果item比中间的值大,则在右边的列表;反之,则在左边的列表中。再按相同的方式一直执行程序,知道找到,返回True,否则返回False。

实现代码:

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
            if item > alist[midpoint]:
                first = midpoint+1
                
    return found

从上面的算法规则可以看出,二分法也适合用递归的方式实现:

def binarySearch_re(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_re(alist[: midpoint], item)
            if item > alist[midpoint]:
                return binarySearch_re(alist[midpoint+1:], item)
    

testlist = [1, 34, 54, 32, 54, 78]
print(binarySearch_re(testlist, 54))
print(binarySearch_re(testlist, 22))

排序

经过查找资料,大概可能有八大排序算法,在这里我介绍几种常见的排序算法。

为了方便大家理解,这里为大家找到各类排序算法的动画各类算法动画演示。

  • 冒泡排序
    冒泡排序作为最经典的排序方式之一,实现原理如下:

从列表的第一个元素开始,向右与相邻的元素比较,将大的放在右侧,依次进行,这样在长度为N的列表中,比较N-1次,最大的元素就放在了列表的最右侧,将其左侧的N-1个元素按照相同的方式操作,直到最后比较一次,完成排序算法。

实现代码如下:

def bubbleSort(alist):
    # n-1 趟  n-1~1
    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]

  • 选择排序
    选择排序是在冒泡排序的基础上进行修改的,特点是:每一趟将最大项的位置记录下来,与最后一项进行交换,这样就实现了每趟只作一次交换。

实现代码:

def selectSort(alist):
    for fillsolt in range(len(alist)-1, 0, -1):
        positionOfMax = 0
        for location in range(0, fillsolt+1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        alist[fillsolt], alist[positionOfMax] = alist[positionOfMax], alist[fillsolt]

  • 插入排序
    将数据分成左右两部分,左边永远是排好序的,右边是未排好序的。

算法思路
第一趟:子列表仅包含第一个数据项,然后插入第二个data;
第二趟:再继续将第三个数据项跟前两个数据项比对,并移动比data_3大的数据项空出位置,将data_3插入空位;
最后经过n-1趟对比和插入,子列表扩展到全表,排序完成。

实现代码:

def insertionSort(alist):
    for index in range(1, len(alist)):
        # 新项/插入项
        currentvalue = alist[index]
        position = index
        
        # 比对、移动
        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            position = position -1
            
        # 插入新项    
        alist[position] = currentvalue

  • 归并排序
    归并排序属于递归算法,它将无序表分裂成两半,两半又分别再分成两半,一直进行下去,最后比较剩下的单个元素。

实现代码:

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        
        mergeSort(lefthalf)
        mergeSort(righthalf)
        
        i= j = 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

上述代码可以在c/c++、java等语言直接改写,下面编写python风格的归并排序算法:

# python 风格的归并排序
def merge_sort(lst):
    if len(lst) < 1:
        return lst
    # 分解问题,并递归调用
    middle = len(lst) // 2
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    
    # 合并左右半部,完成排序
    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    
    # 有剩下的放在后边
    merged.extend(right if right else left)
    return merged
  • 快速排序
    实现原理:依据一个“中值”,将列表分成两半:小于中值的一半和大于中值的一半。

在这里注意,需要设置左/右标:

  • 左标:向右走,当比中值大的时候,stop;
  • 右标:向左走,比中值小的时候,stop。此时要交换左右标的data。
  • 当左标移动到右标的右端时,stop。此时右标的位置就是中值。

实现代码:

# 快速排序
def quickSort(alist):
    quickSortHelper(alist, 0, len(alist)-1)
    
def quickSortHelper(alist, first, last):
    if first < last:
        # 分裂
        splitpoint = partition(alist, first, last)
        quickSortHelper(alist, first, splitpoint-1)
        quickSortHelper(alist, splitpoint+1, last)
        
def partition(alist, first, last):
    # 选定“中值”
    pivotvalue = alist[first]
    
    leftmark = first + 1
    rightmark = last
    
    done = False
    while not done:
        # 左标右移
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1
            
        # 右标左移
        while alist[rightmark] >= pivotvalue and rightmark > leftmark:
            rightmark -= 1
            
        # 两标相错就移动结束
        if rightmark < leftmark:
            done = True
        else:
            # 左右标的值互换
            alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]
            
    # 中值就位
    alist[first], alist[rightmark] = alist[rightmark], alist[first]
    
    # 中值点,也是分裂点
    return rightmark
        


这篇关于python数据结构——(5)查找与排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程