栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

HuaPu在学:Python数据结构与算法【排序 & 搜索】

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

HuaPu在学:Python数据结构与算法【排序 & 搜索】


文章目录
  • 前言
  • 一、排序算法的稳定性
    • 1.冒泡排序
    • 2.选择排序
    • 3.插入排序
    • 4.快速排序
    • 5.希尔排序
    • 6.归并排序
  • 二、搜索
    • 二分查找

前言

以下是花圃在学习Python的数据结构与算法的一些要点内容笔记。


一、排序算法的稳定性

排序算法(Sorting aigorithm),之前我们再说数据结构时候,说到顺序表、链表,那么这之中存储的数据是可以按照特定顺序进行排序的,所以我们将这种能够将一串数据进行排序的算法称之为排序算法。

排序算法稳定性是指让原本相等键值的记录维持相对的次序。

1.冒泡排序

冒泡排序(Bubble Sort),是一种最基础的交换排序。之所以叫做冒泡排序,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动。

每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位,第二趟只能将倒数第 2 位上的数归位,依次类推下去。如果有 n 个数进行排序,只需将 n-1 个数归位,也就是要进行 n-1 趟操作。

而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较,将较大的数放后面,比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系,重复此步骤,直到最后一个还没归位的数。

稳定性:稳定

import time

def bubble_sort(lista):
    if len(lista)<=1:
        return lista
    elif len(lista)==2:
        if lista[0]>lista[1]:
            lista[0],lista[1] = lista[1],lista[0]
            return lista
    else:
        for j in range(len(lista)-2):
            for i in range(len(lista)-2-j):
                if lista[i]>lista[i+1]:
                    lista[i],lista[i+1]=lista[i+1],lista[i]
                    pass
                pass
            pass
        return lista
    pass

def bubble_sort_u(lista):
    if len(lista)<=1:
        return lista
    elif len(lista)==2:
        if lista[0]>lista[1]:
            lista[0],lista[1] = lista[1],lista[0]
            return lista
    else:
        for j in range(len(lista)-2):
            count=0
            for i in range(len(lista)-2-j):
                if lista[i]>lista[i+1]:
                    lista[i],lista[i+1]=lista[i+1],lista[i]
                    count+=1
                    pass
                pass
            if count==0:
                return lista
            pass
        return lista
    pass

list1=[]
list2=[13,1]
list3=[55,20,12,88,66,33,44,99,100,40,60,23]
print(bubble_sort(list1))
print(bubble_sort(list2))
print(bubble_sort(list3))

list4=list(range(10000))
start_time1=time.time()
bubble_sort(list4)
end_time1=time.time()
print(end_time1-start_time1)

start_time2=time.time()
bubble_sort_u(list4)
end_time2=time.time()
print(end_time2-start_time2)
[]
[1, 13]
[12, 20, 33, 40, 44, 55, 60, 66, 88, 99, 100, 23]
4.7323689460754395
0.0010275840759277344
2.选择排序

在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾;以此类推,直到所有元素均排序完毕。

稳定性:不稳定

import time

list1=[]
list2=[13,1]
list3=[55,20,12,88,66,33,44,99,100,40,60,23]
list4=list(range(10000))

def choose_sort(lista):
    if len(lista)<=1:
        return lista
    elif len(lista)==2:
        if lista[0]>lista[1]:
            lista[0],lista[1] = lista[1],lista[0]
            return lista
    else:
        for j in range(len(lista)):
            count=0
            for i in range(j+1,len(lista)):
                if lista[j]>lista[i]:
                    lista[j],lista[i]=lista[i],lista[j]
                    count+=1
                    pass
                pass
            if count==0:
                return lista
            pass
        return lista
    pass

start_time1=time.time()
print(["choose_sort"],choose_sort(list3))
end_time1=time.time()
print(end_time1-start_time1)

start_time3=time.time()
choose_sort(list4)
end_time3=time.time()
print(end_time3-start_time3)
print("===========================================================")

def choose_sort_u(lista):
    if len(lista)<=1:
        return lista
    elif len(lista)==2:
        if lista[0]>lista[1]:
            lista[0],lista[1] = lista[1],lista[0]
            return lista
    else:
        for j in range(len(lista)-1):
            min=j
            for i in range(j+1,len(lista)):
                if lista[j]>lista[i]:
                    min=i
                    pass
                pass
            lista[j],lista[min]=lista[min],lista[j]
        return lista
    pass
start_time2=time.time()
print(["choose_sort_u"],choose_sort_u(list3))
end_time2=time.time()
print(end_time2-start_time2)

start_time4=time.time()
choose_sort(list4)
end_time4=time.time()
print(end_time4-start_time4)
['choose_sort'] [12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
0.0
0.000997304916381836
===========================================================
['choose_sort_u'] [12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
0.0
0.0029985904693603516
3.插入排序

(1.从第一个元素开始,该元素可以认为已经被排序
(2.取下一个元素tem,从已排序的元素序列从后往前扫描
(3.如果该元素大于tem,则将该元素移到下一位
(4.重复步骤(3,直到找到已排序元素中小于等于tem的元素
(5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置
(6.重复步骤(2~(5

稳定性:稳定

import time

list1=[]
list2=[13,1]
list3=[55,20,12,88,66,33,44,99,100,40,60,23]
list4=list(range(10000))

def insert_sort(lista):
    if len(lista)<=1:
        return lista
    elif len(lista)==2:
        if lista[0]>lista[1]:
            lista[0],lista[1] = lista[1],lista[0]
            return lista
    else:
        for i in range(1,len(lista)):
            for j in range(i):
                if lista[i]lista[1]:
            lista[0],lista[1] = lista[1],lista[0]
            return lista
    else:
        for i in range(1,len(lista)):
            while i>0:
                if lista[i] 
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
4.825546503067017
0.0009644031524658203
4.快速排序

def quick_sort(lista,first,last):

    if first>=last:
        return
    mid_value=lista[first]
    low=first
    high=last

    while low=mid_value:
            high-=1
            pass
        lista[low]=lista[high]

        while low 
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
5.希尔排序

希尔排序(Shell Sort)实际上是对插入排序的改进。
1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…
2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。

稳定性:不稳定

import time

def Shell_sort_u(lista):
    if len(lista) <= 1:
        return lista
    elif len(lista) == 2:
        if lista[0] > lista[1]:
            lista[0], lista[1] = lista[1], lista[0]
            return lista
    else:
        gap=len(lista)//2
        while gap>=1:
            for i in range(gap, len(lista)):
                while i>0:
                    if lista[i] 
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
0.01695561408996582
***************************
[1, 1, 2, 3, 9, 10, 11, 19, 20, 32, 41, 47, 49, 55, 66, 70, 73, 78, 81, 100, 121, 586]
6.归并排序

def merge_sort(lista):
    mid_value=len(lista)//2
    if len(lista)<=1:
        return lista
    left_li=merge_sort(lista[:mid_value])
    right_li=merge_sort(lista[mid_value:])
    left_pointer,right_pointer=0,0
    result=[]
    while left_pointer 
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]

稳定性:稳定

二、搜索 二分查找

首先对于一个普通的序列去查找某个元素或者搜索某个元素是否存在,我们不用所谓的二分查找也可以做到,无非是从头到尾去查找,但我们联想日常翻书的情景,我们发现,我们在一开始都是先翻一半,判断目的章节在该部分的哪一个位置,前或者后,然后依次再去把该部分进行折半。

二分查找就类似这样的过程,那么显然要求我的序列要是有序的,在之前学的顺序表是可以操作的,而且要支持索引。


递归版本:

def binary_search(lista,item):
    if len(lista)>0:
        mid_value=len(lista)//2
        if lista[mid_value]==item:
            return True
        elif lista[mid_value]>item:
            return binary_search(lista[:mid_value],item)
            pass
        else:
            return binary_search(lista[mid_value+1:],item)
            pass
    return False



if __name__=="__main__":
    list3_1=[55,20,12,88,66,33,44,99,100,40,60,23]
    print(merge_sort(list3_1))
    print(binary_search(merge_sort(list3_1),100))
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
True

非递归版本:

def binary_search_u(lista,item):
    first=0
    last=len(lista)-1
    while first<=last:
        mid_value=(first+last)//2
        if lista[mid_value]==item:
            return True
        elif lista[mid_value]>item:
            last=mid_value-1
            pass
        else:
            first=mid_value+1
            pass
        pass
    return False

if __name__=="__main__":
    list3_1=[55,20,12,88,66,33,44,99,100,40,60,23]
    print(merge_sort(list3_1))
    print(binary_search(merge_sort(list3_1),100))
    print(binary_search_u(merge_sort(list3_1),100))
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
True
True
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/889678.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号