算法 时间复杂度, 空间复杂度, 冒泡排序**, 选择排序, 插入算法, 快速排序**

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法 时间复杂度, 空间复杂度, 冒泡排序**, 选择排序, 插入算法, 快速排序**，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2082字，纯文字阅读大概需要3分钟。

内容图文

 时间复杂度

 小结:

 

空间复杂度

 

冒泡排序

 

### 冒泡排序 (************)
### 时间复杂度：最差的情况：O(n^2)  最好的情况：O(n)   空间复杂度:O(1)  并没有开辟新的储存空间
def bubble_sort(li):
    for i in range(len(li)-1):
        flag = True   #用于优化
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                flag = False
        if flag:
            return

li = [7,5,4,6,3,8,2,9,1]
bubble_sort(li)
print(li)

 

选择排序

### 选择排序
### 时间复杂度是：O(n^2)
def select_sort(li):
    for i in range(len(li)):
        minLoc = i
        for j in range(i+1, len(li)):
            if li[minLoc] > li[j]:
                li[minLoc], li[j] = li[j], li[minLoc]

 

插入算法

### 插入排序
### 时间复杂度是：O(n^2)
def insert_sort(li):

    for i in range(1, len(li)):  ### i=2
        tmp = li[i] ## tmp=li[2]=4
        j = i - 1  ### j = 1 li[1]=7

        while j >= 0 and li[j] > tmp:
            li[j+1] = li[j]  ### [5,7,7,6,3,8,2,9,1]  ==> [5,5,7,6,3,8,2,9,1]
            j = j - 1   ### j = 0  j= -1

        li[j+1] = tmp

优化空间: 应用二分查找来寻找插入点

 

小结:

 

 

快速排序

# 快排
##### 时间复杂度是：O(nlogn)
def partition(li, left, right):  #### O(n)
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:
            right = right - 1
        li[left] = li[right]
        while left < right and li[left] <= tmp:
            left = left + 1
        li[right] = li[left]

    li[left] = tmp
    return left

def quick_sort(li, left, right):

    if left < right:
        mid = partition(li, left, right)  ### 归位函数

        quick_sort(li, left, mid-1)     #### O(logn)
        quick_sort(li, mid+1, right)

li = [7,5,4,6,3,8,2,9,1]
quick_sort(li,0,len(li)-1)
print(li)

 

上述4中方法时间比较

import time,random

start = time.time()
li = [random.randint(0,100000) for i in range(10000)]
bubble_sort(li)
print('bubble_sort:',time.time()-start) # 8.805101871490479

start = time.time()
li = [random.randint(0,100000) for i in range(10000)]
select_sort(li)
print('select_sort',time.time()-start)  # 4.129027366638184

start = time.time()
li = [random.randint(0,100000) for i in range(10000)]
insert_sort(li)
print('insert_sort',time.time()-start)  # 3.236048460006714

start = time.time()
li = [random.randint(0,100000) for i in range(10000)]
quick_sort(li,0,len(li)-1)
print('quick_sort',time.time()-start)   # 0.029005050659179688

 

内容总结

以上是互联网集市为您收集整理的算法 时间复杂度, 空间复杂度, 冒泡排序**, 选择排序, 插入算法, 快速排序**全部内容，希望文章能够帮你解决算法 时间复杂度, 空间复杂度, 冒泡排序**, 选择排序, 插入算法, 快速排序**所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---