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

1411-李同学

发表文章数:148

首页 » 数据结构 » 正文

一、排序与搜素

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

排序算法的稳定性

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

二、冒泡排序

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

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)

  • 稳定性,稳定

五、希尔排序

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

希尔排序过程

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

希尔排序逻辑图

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

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)
# 最优时间复杂度根据步长序列的不同而不同

六、快速排序

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

步骤

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

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

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

2020-11-16 数据结构与算法(5)冒泡、选择、插入、希尔、快速、归并排序及二分法查找
2020-11-16 数据结构与算法(5)冒泡、选择、插入、希尔、快速、归并排序及二分法查找
时间复杂度分析:
2020-11-16 数据结构与算法(5)冒泡、选择、插入、希尔、快速、归并排序及二分法查找

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)

七、归并排序

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

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

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

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)。最坏最优情况相同。

稳定性:稳定。

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

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

八、搜索

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

二分法查找

优点:比较次数少,查找速度快。

#递归版本
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)

未经允许不得转载:作者:1411-李同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《2020-11-16 数据结构与算法(5)冒泡、选择、插入、希尔、快速、归并排序及二分法查找》 发布于2020-11-16

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录