Python语言基础(六)内存结构与排序算法

1038-茹同学

发表文章数:74

热门标签

首页 » Python » 正文

基本顺序表与元素外围顺序表

在程序中,需要将一组相同类型的元素进行管理和使用。其可以抽象为线性表,
根据线性表的实际存储方式,分为两种实现模型:

  • 顺序表:将元素顺序地存放在一块连续的存储区里,元素间的顺序关系由它们的存储顺序自然表示。其索引是固定的,所以这样的查找的复杂度为O(1)
  • 链表:将元素存放在通过链接构造起来的一系列存储块中。其内存不是连续的,如果要查找,需要一个一个的遍历过去,所以这样的存储方式,查找的复杂度为O(n)

列表与元组的实现

列表在Python中由C语言实现,是一个容量大小动态变化的数组,其内部主要由三个部分组成
(1)指针数组,存储了所有列表元素的地址
(2)PyObject_VAR_HEAD Python中所有对象的基础
(3)allocated 允许存放的元素数量。默认为8,每当达到元素的一半时进行4倍的容量放大。
那么既然列表的容量是动态可变的,那必然存在存储容量的扩大。每次在扩大容量时,解释器都会放出一个新的一段内存,迁移数据并释放之前存储元素的内存。

元组的实现与Python类似,只是不允许修改,一旦定义了一段元组不能修改或者添加删除其中的元素。

字典的实现

原理同散列表,这里不再赘述

集合的实现

原理同散列表,与字典不同的是没有value值的存储。Python中默认的有两种集合

  1. set() 可变的,哈希的集合
  2. frozenset() 不可变的,哈希的集合

这两者都是不可重复的。

排序算法之快速排序

(1)取最左边的元素为标杆,从左向右查找比标杆大的元素,从右向左查找比标杆小的元素。如果两个指针没有相遇则交换位置所在的元素。如果相遇则交换相遇点与标杆元素。
(2)至此,相遇点左边的元素都是小于标杆元素的,相遇点右边的元素都是大于标杆元素的。
(3)将标杆左边的数组和右边的数组分别做循环即可

l1 = [15, 4, 10, 8, 20, 30]


def quickSort(l, left, right):
    if left < right:
        k = partition(l, left, right)
        quickSort(l, left, k-1)
        quickSort(l, k+1, right)
    return l


def partition(l: list, left: int, right: int) -> object:
    tmp_num = l[left]
    tmp_left_flag = left
    tmp_right_flag = right
    while tmp_left_flag < tmp_right_flag:
        while l[tmp_left_flag] < tmp_num:
                tmp_left_flag += 1

        while l[tmp_right_flag] > tmp_num:
                tmp_right_flag -= 1

        if tmp_left_flag < tmp_right_flag:
            l[tmp_left_flag], l[tmp_right_flag] = l[tmp_right_flag], l[tmp_left_flag]

        if tmp_left_flag == tmp_right_flag:
            l[tmp_left_flag], tmp_num = tmp_num, l[tmp_left_flag]
            return tmp_left_flag

    return tmp_left_flag


def switch(left, right):
    tmp = left
    left = right
    right = tmp
    return [left, right]


print(quickSort(l1, 0, len(l1) - 1))

标签:

拜师教育学员文章:作者:1038-茹同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python语言基础(六)内存结构与排序算法》 发布于2020-05-20

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录