学习笔记:数据结构与算法Python版[搜索和排序-上]

顺序查找

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

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

无序列表的顺序搜索代码——复杂度O(n)

def sequentialSearch(alist,item):
    pos=0
    found=False
    
    while pos<len(alist) and not found:
        if alist[pos]==item:
            found=True
        else:
            pos=pos+1
            
    return found
testlist=[1,2,32,6,14,19,13,44]
print(sequentialSearch(testlist,14))

有序列表的顺序搜索—— 复杂度O(n)

def sequentialSearch(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=pos+1
            
    return found
testlist=[1,2,3,4,14,19,20,44]
print(sequentialSearch(testlist,14))

二分查找

二分搜索与顺序查找不同它不是从第一个元素开始搜索列表，而是从中间元素着手。

如果这个元素就是目标元素，那就立即停止搜索；如果不是，则可以利用列表有序的特性，排除一半元素。

如果目标元素比中间大，就可以直接排除列表的左半部分和中间的元素。这时因为，如果列表包含目标元素，它必定位于右半部分。

eg:

有序列表的二分搜索

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[midponit]:
                last=midpoint-1
            else:
                first=midpoint+1
                
    return found
testlist=[1,2,3,4,14,19,20,44]
print(binarySearch(testlist,14))

二分搜索的递归版本——算法复杂度O(logn)

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)
                
    return found
testlist=[1,2,3,4,14,19,20,44]
print(binarySearch(testlist,14))

二分搜索算法分析

在进行二分搜索时，每一次比较都将待考虑元素减半。假设列表共有n个元素，第一次比较后剩下 2/n个元素，第二次4/n 第三次 8/那一次类推。。。。

排序

冒泡排序

冒泡排序多次遍历列表,它比较相邻的元素，将不和顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。本质上，每个元素通过"冒泡"找到自己所属的位置

时间复杂度O(n2)

冒泡排序第一趟

代码:

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 = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

python允许同时赋值例如执行 a,b=b,a 相当于同时执行两条赋值语句

temp=alist[j]
arr[j]=arr[j+1]
arr[j+1]=temp

修改后:

arr[j],arr[j+1]=arr[j+1],arr[j]

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

升级版短冒泡排序

选择排序

选择排序在冒泡排序的基础上做了改进，每次遍历列表时只做一次交换。要实现这一点,选择排序

在每次遍历时寻找最大值，并在遍历完之后将它放到正确位置上。

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。

所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤:

1.首先在末尾排序序列中找到最小(大)元素，存放排序序列的起始位置。

2.再从剩余未排序元素中继续寻找最小(大)元素，然后放到自己已排序序列的末尾。

3.重复第二布，知道所有元素均排序完。

代码

def selectionSort(arr):
    for i in range(len(arr)-1):
        minIndex=i
        for j in range(i+1,len(arr)):
           if arr[j]<arr[minIndex]:
               minIndex=j        
        if i!=minIndex:
            arr[i],arr[minIndex]=arr[minIndex],arr[i]
    return arr
 
alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

插入排序

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

1.插入排序的比对主要用来寻找"新项"的插入位置

2.最差情况时没糖都与子列表中所有项进行比对，总比对次数与冒泡排序相同，数量级仍是O(n2)

3.最好情况，列表已经排好序的时候，每趟仅需一次比对，总次数是O(n)

算法步骤

1.第一趟，子列表仅包含第一个数据项,将第二个数据项作为"新项"插入到子列表的核实位置中，这样已排序的子列表就包含了2个数据项。

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

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

排序思路

算法代码

def insertionSort(alist):
    for index in range(1,len(alist)):
        #将当前值存到currentvalue中
        currentvalue=alist[index]
        #将当前下标存到position中 这个就是下标指针
        position=index
        
        #循环判断当前下标大于0 和当前数据是否小于前一位数据
        while position>0 and alist[position-1]>currentvalue:
            #如果小于则:
            #将前一位数据赋值给当前数据所在的位置
            alist[position]=alist[position-1]
            #给下标指针-1
            position=position-1
            
        alist[position]=currentvalue
        
alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

算法分析

最坏的情况下比较次数时前n-1个整数之和对应的时间复杂度时O(n²)

希尔排序

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

算法步骤

这个列表有9个元素。如果增量为3，就有3个子列表

每个都可以应用插入排序。尽管列表仍然不完全有序，但通过给子列表排序，我们已经让元素离它们的最终位置更近了

有了之前的子列表排序，因此移动次数已经减少了，本利只需要再移动4次

算法代码

def shellSort(alist):
    #计算步长 每个n/2个来分成若干份
    sublistcount=len(alist)//2
 
 
    #如果步长大于0则执行
    while sublistcount > 0:
        #循环排序每组元素
        for startposition in range(sublistcount):
            #执行插入排序 alist是数据 startposition是开始下标 sublistcount是步长
            gapInsertionSort(alist,startposition,sublistcount)
            
        print("After increments of size",sublistcount,"The list is",alist)
        
        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
 
alist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)

算法分析

介于O(n)和O(n2)之

归并排序

归并排序，采用的是分治策略，他是一个递归算法，每次将一个列表一分为二。

如果有列表为空或只有一个元素，那么从定义上来说它就是有序的(基本情况)、如果列表不知一个元素，就将列表一分为二。

并对两部分都递归调用归并排序。

算法步骤

结束条件是数据表中仅有1个数据项，自然是排好序的

缩小规模:将数据表分裂成相等的凉拌，规模减为原来的二分之一；

调用自身:将两半分别调用自身排序，然后将分别排好序的两半进行归并，得到排好序的数据表

算法代码

#将数组元素递归分成两半
#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=j=k=0
#        
#        #将数组元素进行比较归并
#        #判断左边和右边是否有数据
#        while i<len(lefthalf) and j<len(righthalf):
#            #如果左边的数据小于右边的数据则 将左边数据赋值给alist[k] 否则将右边的赋值给
#            #不管是谁谁的自身下标移动+1
#            print(alist[k])
#            if lefthalf[i]<righthalf[j]:
#                alist[k]=lefthalf[i]
#                i=i+1
#            else:
#                alist[k]=righthalf[j]
#                j=j+1
#            k=k+1
#        print('alist:',alist)
#  
#            
#        while i<len(lefthalf):
#            alist[k]=lefthalf[i]
#            i=i+1
#            k=k+1
#        
#        while j<len(righthalf):
#            alist[k]=righthalf[j]
#            j=j+1
#            k=k+1
#    
#   
#alista = [54,26,93,17,77,31,44,55,20]
#mergeSort(alista)
#print(alista)

算法复杂度

分裂过程 O(log n)

归并过程 O(n)

总的时间复杂度O(nlog n)

注意:这个算法额外使用了1倍的存储空间用于归并

快速排序

快速排序算法思路是依据一个 “中值”数据项来把数据表分为两半:小于中值的一般和大于中值的一般，然后每部分分别进行快速排序(递归)

如果希望这两班拥有相等的数量的数据项，则应该找到数据表的"中位数"

但找中卫书余姚计算开销！要想没有开销，只能随意找一个数来充当"中值" 比如第一个数

快速排序的递归算法递归三要素

1.基本结束条件:数据表仅有1个数据项，自然是拍好序的

2.缩小规模:根据"中值"，将数据表分为两半，最好情况时相等规模的两半

3.调用自身:将两半分别调动自身进行排序(排序基本操作在分裂过程中)

分裂数据表的目标:找到“中值”的位置

分裂数据表的手段

设置左右标(left/rightmark)

坐标向右移动，右标向左移动

继续移动知道左标一道右标的右侧，停止移动

这时右标所指的位置就是"中值"应处的位置

将中值这个位置交换

分裂完成，做颁布比值小，又半步比中值打

示例代码

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=leftmark+1
            
        #如果当前位置的值大于等于中值 和右标位置大于等于左标
        #向左移动右标
        while alist[rightmark]>=pivotvalue and rightmark >=leftmark:
            rightmark=rightmark-1
            
        #如果右标位置小于左标位置 则说明两个标相交了 则结束 否则进行左右标值交换
        if rightmark<leftmark:
            done =True
        else:
            temp=alist[leftmark]
            alist[leftmark]=alist[rightmark]
            alist[rightmark]=temp
 
 
    #中值交换
    temp =alist[first]
    alist[first]=alist[rightmark]
    alist[rightmark]=temp
    return rightmark
 

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)
        
alista = [54,26,93,17,77,31,44,55,20]
quickSort(alista)
print(alista)

算法分析

O(n)

学习笔记:数据结构与算法Python版[搜索和排序-上]

顺序查找

二分查找

排序

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序

总结

相关推荐