基本数据结构和算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了基本数据结构和算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2704字，纯文字阅读大概需要4分钟。

内容图文

一、数据结构

开发中。。。

 

二、算法

2.1 冒泡排序

# 如果冒泡排序中执行一趟而没有交换，则列表已经是有序状态，可以直接结束算法。

def BubbleSort(li):
    for i in range(len(li)):
        flag = True
        for j in range(len(li) - i - 1):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                flag = False
        if flag == True:
            return None
li = [random.randint(0, 100) for i in range(10)]
BubbleSort(li)
print(li)

# 时间复杂度是： O(n^2)
# 空间复杂度是： O(1)

2.2 选择排序

# 一趟遍历记录最小的数，放到第一个位置；
# 再一趟遍历记录剩余列表中最小的数，继续放置；

def SeleteSort(li):
    for i in range(len(li)):
        minLoc = i
        for j in range(i + 1, len(li)):
            if li[j] < li[minLoc]:
                li[j], li[minLoc] = li[minLoc], li[j]
li = [random.randint(0, 100) for j in range(10)]
SeleteSort(li)
print(li)

# 时间复杂度是：O(n^2)
# 空间复杂度是：O(1)

2.3 插入排序

# 列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
# 每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。

def InsertSort(li):
    for i in range(len(li)):
        tmp = li[i]
        j = i - 1
        while j >= 0 and li[j] > tmp:
            li[j + 1] = li[j]
            j = j - 1
        li[j + 1] = tmp
li = [random.randint(0, 100) for k in range(10)]
InsertSort(li)
print(li)

# 时间复杂度：O(n^2)
# 空间复杂度；O(1)

2.4 快速排序

# 取一个元素p（第一个元素），使元素p归位；
# 列表被p分成两部分，左边都比p小，右边都比p大；
# 递归完成排序。

# 归位函数：使归位元素左边的都比归位元素小，右边的都大。
def partition(li, left, right):
    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)
        Quick_Sort(li, mid + 1, right)


li = [random.randint(0, 100) for l in range(10)]
Quick_Sort(li, 0, len(li) - 1)
print(li)

# 时间复杂度：O(nlogn)

2.5 归并排序

# 分解：将列表越分越小，直至分成一个元素。
# 一个元素是有序的。
# 合并：将两个有序列表归并，列表越来越大。

def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high:
if li[i] <= li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1

li[low:high + 1] = ltmp


def mergeSort(li, low, high):
if low < high:
mid = (low+high) // 2
mergeSort(li, low, mid)
mergeSort(li, mid + 1, high)
merge(li, low, mid, high)


li = [random.randint(0, 100) for m in range(10)]
mergeSort(li, 0, len(li) - 1)
print(li)

# 时间复杂度：O(nlogn)
# 空间复杂度：O(n)

2.6 计数排序

def countSort(li):
    count = [0 for x in range(max(li) + 1)]

    for i in li:
        count[i] += 1
    li.clear()
    for n ,num in enumerate(count):
        for x in range(num):
            li.append(n)


li = [random.randint(0, 100) for n in range(10)]
countSort(li)
print(li)

 

内容总结

以上是互联网集市为您收集整理的基本数据结构和算法全部内容，希望文章能够帮你解决基本数据结构和算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

---