2020-11-16 数据结构与算法（5）冒泡、选择、插入、希尔、快速、归并排序及二分法查找

一、排序与搜素

排序算法是一种能将一串数据按照一定顺序进行排列的一种算法

排序算法的稳定性

稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。

二、冒泡排序

重复地遍历要排序的数列，一次比较两个元素。

方法1：正序

def bubble(list):
    n=len(list)
    for j in range(0,n-1): #一共要排序n-1次
        for i in range(0,n-1-j): #每一次排序都有n-2次变换
            if list[i]>list[i+1]:
                list[i],list[i+1]=list[i+1],list[i]
    print(list)


bubble([4,2,1,3,33,34,78,1,4,5,30])

方法2：逆序

def bubble1(list):
    for j in range(len(list)-1,0,-1):
    	count=0
        for i in range (j):
            if list[i] > list[i + 1]:
                list[i], list[i + 1] = list[i + 1], list[i]
                count+=1
        if count==0:
            	return
    print(list)

bubble1([4, 2, 1, 3, 33, 34, 78, 1, 4, 5, 30])

时间复杂度

• 最优时间复杂度： O（n）

• 最坏时间复杂度：O（n**2）

• 稳定性：稳定

三、选择排序

#选择排序
alist=[54,226,93,17,77,31,44,55,20]
#      0   1   2  3 4  5  6  7   8
'''
#第一次选择最小的放第一个
alist=[17,226,93,54,77,31,44,55,20]
#第二次选择第二小的小的放第二个
alist=[17,20,93,54,77,31,44,55,226]

alist=[17,20,31,54,77,93,44,55,226]
'''
def selection_sort(list):
    n=len(list)
    for i in range(n-1): #i产生0，n-2
        min_index=i
        for j in range (i+1,n):
            if list[j]<list[min_index]:
                min_index=j #更新下标
        #需要在循环退出后再进行交换，因为对于每一次的j循环，只有一个最小的元素会被
        #放到i的位置上
        list[i],list[min_index]=list[min_index],list[i]

selection_sort(alist)
print(alist)

时间复杂度

• 最优时间复杂度：O（n**2）

• 最坏时间复杂度：O（n**2）

• 稳定性：不稳定（考虑升序会不稳定）

四、插入算法

自创方法

alist=[54,226,93,17,77,31,44,55,20]

def insert_sort(list):
    n=len(list)
    for i in range (1,n):
        for j in range(i,0,-1):
            if list[j]<list[j-1]:
                list[j],list[j-1]=list[j-1],list[j]
            else:
                break
insert_sort(alist)
print(alist)


#课堂方法
def Insert_Sort(list):
    n=len(list)
    #外层循环从右边的无序序列中取出多少个元素执行这样的过程
    for j in range(1,n):
        #j=[1,2,3,4,...n-1]
        #i代表内层循环的起始值
        i=j
        #执行从右边的无序序列中取出第一个元素，及i位置得元素，然后将其插入到前面的正确位置中。
        while i !=0:
            if list[i]<list[i-1]:
                list[i],list[i-1]=list[i-1],list[i]
                i -= 1
            else:
                break

if __name__=="__main__":
    Insert_Sort(alist)
    print(alist)

时间复杂度

• 最优时间复杂度： O（n）

• 最坏时间复杂度：O（n*2）

• 稳定性，稳定

五、希尔排序

希尔排序是插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法

希尔排序过程

基本思想：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列来进行，最后整个表就只有这一列了。将数组转换至表是为了更好的理解这算法，算法本身还是用数组进行排序。

希尔排序逻辑图

def Shell_sort(list):
    #n=9,gap=4
    n=len(list)
    gap=n//2
    #gap 变化到0之前插入算法执行的次数
    while gap >0:
        #插入算法，与普通的插入算法的区别在于gap步长
        for j in range(gap,n):
        #j=[gap,gap+1,gap+2,gap+3,gap+4,.....gap+5]
            i=j
            while i>0:
                if list[i]<list[i-gap]:
                    list[i],list[i-gap]=list[i-gap],list[i]
                    i-=gap
                else:
                    break
        #缩短gap步长
        gap//=2

alist=[54,226,93,17,77,31,44,55,20]
Shell_sort(alist)
print(alist)
# 最优时间复杂度根据步长序列的不同而不同

六、快速排序

又称为划分交换排序，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据药效，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序数列

步骤

• 从数列中挑出一个元素，成为基准

• 重新排序数列，所有元素比基准小的值摆放在基准前面，所有元素比基准大的值摆在基准后面。在这个分区结束后，该基准就处于数列的中间位置，称为分区操作

• 递归低把小于基准值元素的子数列和大于基准值元组的子数列排序。

时间复杂度分析：

def quick_sort(list,first,last):
    if first>=last:
        return
    mid_value=list[first]
    low=first
    high=last
    while low< high:
        #让high的游标左移
        while low<high and list[high]>=mid_value: #将相等的分割元素放到右边
            high-=1
        #遇到比mid_value小的把其值赋予low所在位置
        list[low]=list[high] #赋值时low位置的值肯定会小于mid_value，所以可以继续执行while语句
        #low+=1
        #low的右边右移
        while low<high and list[low]<mid_value:
            low+=1
        #遇到比mid_value大的把其值赋给high所在位置。
        list[high]=list[low]
        #high-=1
    #从循环退出时，low==high
    list[low]=mid_value
    #对low左边的列表执行快速排序
    quick_sort(list,first,low-1) #不能传递新的列表。
    #对low右边的列表排序
    quick_sort(list,low+1,last)
if __name__=="__main__":
    alist=[54,226,93,17,77,31,44,55,20]
    print(alist)
    quick_sort(alist,0,len(alist)-1)
    print(alist)

时间复杂度的最坏情况

是列表中每第一次元素都只能将列表中其他元素分到一边，且每次都只能分到一边，如此下去，要经历n次遍历且每次遍历数目都为n。即最坏时间复杂度为O（n**2）

七、归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

将数组分解最小后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

def merge_sort(list):
    n=len(list)
    mid=n//2
    if n<=1:
        return list
    #left 采用归并排序后形成的有序的新的列表
    left_li=merge_sort(list[:mid])
    right_li=merge_sort(list[mid:])

    #将两个有序的子序列合并为一个整体。
    #merge(left,right)
    left_pointer,right_pointer=0,0
    result=[]
    while left_pointer<len(left_li) and right_pointer <len(right_li):
        if left_li[left_pointer]<= right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer+=1
        else:
            result.append(right_li[right_pointer])
            right_pointer+=1
    result+=left_li[left_pointer:]
    result+=right_li[right_pointer:]
    return result

if __name__=="__main__":
    li=[54,26,91,17,77,31,44,55,20]
    li1=merge_sort(li)
    print(li1)

归并排序时间复杂度与插入排序复杂度对比

归并排序中每个层级的合并比较时间复杂度都为n，一共合并了log2n次，所以时间复杂度为O（nlogn）。最坏最优情况相同。

稳定性：稳定。

区别是拿到的是一个新的列表，从时间看是小的，但从空间上，占用了额外的内存。

八、搜索

在一个序列中查找某个元素是否存在。

二分法查找

优点：比较次数少，查找速度快。

#递归版本
def binary_search(list,item):
    n=len(list)
    if n>0:
        mid=n//2
        if list[mid]==item:
            return True
        elif list[mid]> item:
             return binary_search(list[0:mid],item) #调用函数自身时也要返回最后的值。
        else:
            return binary_search(list[mid+1:],item)
    return False

if __name__=="__main__":
    li=[1,2,3,4,5,6]
    print(binary_search(li,55))
    print(binary_search(li,3))

#非递归
def binary_search1(list,item):
    n=len(list)
    first=0
    last=n-1
    while first<=last:
        mid=(first+last)//2
        if list[mid]==item:
            return True
        elif item<list[mid]:
            last=mid-1
        else:
            first=mid+1
    return False
if __name__=="__main__":
    li=[1,2,3,4,5,6]
    print(binary_search1(li,55))
    print(binary_search1(li,3))

使用对象：顺序表
时间复杂度

• 最优时间复杂度：O(1)
• 最坏时间复杂度：O(logn)