开发者学堂课程【Python 开发基础入门：Python 内置数据结构及排序、冒泡算法】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/556/detail/7659
Python 内置数据结构及排序、冒泡算法
内容介绍：
一、元组 tuple
二、元组的定义初始化
三、元组元素的访问
四、元组查询
五、元组其他操作
六、命名元组 namedtuple
七、练习
八、冒泡法
九 、冒泡法总结
一、 元组 tuple
相对于列表来讲，元组究竟是可变还是不可变，这种数据结构，有好几种，它是不可变的，不可变，可以认为它是只读的，但是这个不可变，需要知道它是什么地方不可变。
元组是使用小括号来表示的，这是 Python 中一个特别的东西，每一种数据结构，它的适用场景。
list 在某些场景下去使用的时候，它是有效率问题，那么 tuple 一样。可以简单的认为，虽然这样不准确，但是可以简单的认为。这是一个只读列表。
便于理解，可以这么简单理解，也就说它是一个只读的，它的那些能跟修改，删除，增加相关的方法全都没有。
一次性创建好，创建好之后，就不允许在里面再添加删除元素，也不允许对当前这个放在里面这个元素，然后进行任何的修改。当然这个元素的修改，其实本质上是用的内存地址。
也就是说只要那个内存地址不变就没有问题，但是提到内存地址，就应该想到是引用类型。
那如果说里面放的是个1或者放的是 abc ，现阶段就理解他放了就是这个东西，放这个单值，所以说这个内容的也不允许改，但是如果里面放一个引用类型，放在内存地址相当放个门牌号码，打开这个门一看变了。
人家在这个房间里想怎么改，怎么改，但是内存地址不改，就相当于对元组来讲，它就没改对，这个例子。就这个很好地符合实践的结果，当然要去追求本质的时候，再加深理解，目前对内存的理解还不够，所以说先不要这么去记。
这样会增加记忆负担，还必须清楚这些所谓的字面常量在内存中是怎么放的，所以现在先这样做，以后在逐步加深。
一个有序的元素组成的集合
使用小括号()表示
元组是不可变对象
Ps：可以简单的认为他是一个只读列表，并且要明白是什么不可变。小括号是元组，中括号是列表。 我们要明白list 的作用。
二、 元组的定义初始化
元组的这个定义方法，一般来讲的话，有下面这几种形式，那这一种
t= (1,)*5 ，它是用一个元组，它用乘法生成了一个新元组，如果它
不生成一个新元组，就相当于它并没有 return，这相当于 return，
就是按照一个 return，就是返回了一个新的。
返回之后才能复制。如果不返回，相当于是 None ，复制出去，就
相当于 t= None。
所以这句话的本质也应该理解，这相当于它用乘法之后，把它里面元
素复多复制了多少，然后组成一个新元组，这个新的元组交给谁？
如果它不能返回一个新的元组的话，那么给 t 的值就是None ，那
就没有意义，那这些东西都一样，凡事能这么写的，一般来讲。右边就不应该写成这样。
定义
tuple() -> empty tuple
tuple(iterable) -> tuple initialized from iterable's items
t = tuple()#工厂方法
t= ()
t = tuple(range(1,7,2)) # iteratable
t= (2,4,6,3,4,2)
t= (1,) # -个元素元组的定义,注意有个逗号
t= (1,)*5 #用一个元组，用乘法生成了一个新的元组
t= (1,2,3)* 6
例如：
1) .输入;
a=print(‘b’)
运行结果：
b
2) .输入;
type(a)
运行结果：
NoneTyple
3) .输入;
a=()
a
运行结果:
()
4) .输入：
a=tuple()
a
运行结果：
（）
Ps:返回值很重要，python中默认返回值为none，一个空值。没有返回的内容。
5）输入：
a=print(‘b’)
print(‘b’)
a=None
运行结果：
B
5) 输入：
lst=[]
lst.append(1).append(2)
输出结果：
无
这种写法是不对的，都是空值
三、元素元组的访问
对于元组来说，正索引负索引所以都会支持，但是因为它是只读的，所以给它里面的某一个格子里面，想给它重新赋值，是不可以的。
如果里面是个引用类型，只能对那个引用类型的那个对象进行修改，不能对元组这一层进行修改，它是只读，它不允许，正索引负索引一样，上下不允许超界，超界会报错误，更准确的叫法应该是叫抛出异常。
支持索引(下标)
正索引:从左至右，从0开始，为列表中每一个元素编号
负索引:从右至左，从-1开始
正负索引不可以超界，否则引发异常 IndexError
元组通过索引访问
tuple[index]，index就是索引，使用中括号访问
t[1]
t[-2]
t[1]= 5
四、 元组查询
元组查询跟 list 是一样的，因为它们的方法都是一模一样的，因为这些方法在这些有序的这个里面，它们都是通用的，因为它也希望它的所有的这些方法，或者称为操作，或者称为API。
这些东西都应该是一样的，这便于大家去记忆，所以它尽量把它设计的是一样的，但既然是一样的，那么来理解它就发现跟列表这块是相似的，也就说它所有的这种时间复杂度都是一个样子的。所以可以把它们认为是一个简化版的 list，只读的 list 。
index(value,[start,[stop])
通过值value，从指定区间查找列表内的元素是否匹配
匹配第一个就立即返回索引
匹配不到，抛出异常ValueError
count(value)
返回列表中匹配value的次数
时间复杂度
index和count方法都是O(n)
随着列表数据规模的增大，而效率下降
len(tuple)
返回元素的个数
Ps：所有时间元素都是一样的
五、 元组其他操作
元组是只读的，所以增、改、删方法都没有
Ps：在某些时候传给客户的数据，只是为了客户去读，或者在内存中大量的存在，就没有增删改。
对于获取的数据，如果不进行增删改，选用元组最为合适。回顾一下学习的 list ，它更多的是 append 等等。
如果有时候要在尾部追加，就算开辟得很好，但是偶尔可能还是要加一些数据进去，就避免不了 append ，append 它本身的时间复杂度就已经很好了。如果后面还有空间，就可以直接加，如果没有它就会开辟空间出来。但是需要考虑的远远不止这一点，还有其他很多情况。
下去之后一定要把习题练好，把一道题当作十道题来练习，要加深印象，并且不能只麻木的练习，还要去思考，要有逻辑思维能力，不然之后写程序很容易出现 BUG ，还要好好调试写好的代码，测试一下，测试之后没有问题再把它放到服务器上去。
六、、 命名元组 namedtuple
命名元组一般是讲完面向对象，自己建立类以后就很少再用它，但是这个有时候会出现在源码中。
帮助文档中，查阅 namedtuple，有使用例程
namedtuple(typename, field_ names, verbose= False, rename=False)
命名元组，返回一个元组的子类，并定义了字段大
field_names可以是空白符或逗号分割的字段的字符串，可以是字段的列表
from collections import namedtuple
Point = namedtuple('_ Point','x';'y'") # Point为返回的类
Ps：Point 是一个标识符，标识符要拿来使用， _ Point 是一个字符串，不能把字符串拿来使用，会报错。也就是说，名字和标识符是两码事，要去创建一个真正的对象出来，要用变量而不是名字，名字相当于是一个代号，标识符是用来指代这个对象，就可以加括号调用。它们不一样，要注意区别。
p = Point(11, 22)
Ps：创建出新的类型
Student = namedtuple( Student', 'name age')
tom = Student("tom', 20)
jerry = Student(jerry', 18)
tom.name
七、练习
依次接收用户输入的3个数，排序后打印（要用以下4种方法完成，为了方便直接使用正整数）
不论是从大到小还是从小到大，只要把这几个数排序出来就就可以，用分支结构 if-else-if。If-else 是基本功，依然有同学写不出来，要求大家上课必须要练习的，这个以后写代码有一个严密的逻辑。
冒泡法使用的最多，而且是面试中问的最多的一种方法，所以必须会写。
转换 int 后，判断大小顺序。使用分支结构完成
使用 max 函数
使用列表的 sort 方法
冒泡法
Ps:必须会分支结构，这是基础。必须要掌握冒泡法，在许多面试中会用到，非常重要。
转换int后，判断大小排序。使用分支结构完成
1).常规方式：
nums = []
out = None
//输3个数
for i in range(3):
nums . append(int(input( '{}: ' .format(i))))
if nums[0] > nums[1]:
if nums[0] > nums[2]:
i3=nums[0]
if nums[1] > nums[2]:
i2=nums[1]
i1=nums[2]
else:
i2=nums[2]
i1=nums[1]
else:
i2=nums[0]
i3=nums[2]
i1=nums[1]
else:#0<1
if nums[0] >nums[2]:
i2=nums[0]
i3=nums[1]
i1=nums[2]
else:#0<2
if nums[0]
i2=nums[1]
i3=nums[2]
i1=nums[0]
else:# 1>2
i2=nums[2]
i3=nums[1]
i1=nums[0]
print(i1,i2,i3)
2).改进
nums = []
out = None
//输3个数
for i in range(3):
nums . append(int(input( '{}: ' .format(i))))
if nums[0] > nums[1]:
if nums[0] > nums[2]:
if nums[1] > nums[2]:
out = [2,1,0]
else:
out = [1,2,0]
else:
out = [1,0,2]
else: # 0<1
if nums[0] > nums[2]:
out = [2,0,1]
else: # 0<2
if nums[1] < nums[2]: #1<2
out = [0,1,2]
else: #1 > 2
out = [0,2,1]
out. reverse()
for i in out:
print(nums[i],end=', '
3.使用max函数
# max min的实现
nums =[]
out = None
for i in range(3):
nums . append(int(input('{}: ' .format(i))))
#此处不能使用for循环，不能一边迭代该列表， 同时删除或者增加该列表
while True:
cur = min(nums)
print(cur)
nums . remove(cur)
if len(nums) == 1:
print(nums[0])
break
4.使用列表的sort方法
#列表sort实现
nums =[]
out = None
for i in range(3):
nums . append(int(input( '{}: ' . format(i))))
nums .sort()
print(nums)
5.冒泡法（运用价值比较高）
num_ list = [
[1，9，8，5，6,7，4，3，2],
[1,2，3，4,5，6，7,8，9]，
[1，2，3，4,5，6，7，9，8]
]
nums = num_list[2]
print (nums)
length = len (nums)
count_swap = 0.
count = 0
# bubble sort
for i in range (length) :
flag = False
for j in range (length-i- 1) :
count += 1
if nums[j] > nums[j+1] :
tmp=nums[j]
nums[j] = nums[j+1]
nums[j+1] = tmp
flag = True # swapped
count_swap+= 1
if not flag:
break
print (nums, count_ swap, count)
八、冒泡法
冒泡法三大排序算法之一，它的效率未必就很高，它很简单，在两分钟内就能写完。要求是五分钟内写完。
冒泡法属于交换排序，它就是两两比较比较谁大谁小，把大的房子最左边，或者放在最右边，总之要将顺序排列出来。两两比较，如果出现大小情况不一致，就将它们交换顺序。
如果满足预期要求，就不调换，在进行下一个比较。举个例子给五位同学按照身高排位置，首先把同学一与同学二作比较。然后就可以分辨出哪一个同学比较高，就把高的这个同学放在右边。
在去比较其他几位同学，然后再将比比出来的这个同学高的同学又换到最右边去，以此类推。两两比较，直到把这五位同学按照身高顺序排列出来为止。
冒泡法
属于交换排序
两两比较大小,交换位置。如同水泡咕嘟咕嘟往上冒
结果分为升序和降序排列
初始情况下，这些数字都是杂乱的，然后需要将它们排列出来。不管是从小到大，还是从大到小，但是必须都把它排列出来。
为了方便起见，从左到右，从小到大。升序排列这里的第一趟就是把最大的数往最右边放，但并不是在里面。
挑两个最大的数，往最右边放。在第一趟中，三个数字是189。然后1与8比较。位置就不用调换。因为大的，已经在右边了。8与9比较时候就可以发现，大的也在右边也可以不用换。9在与它旁边的5作比较。发现5比9小，所以说要把9往右边调。
以此类推，9比他右边的剩余的所有数都要大，所以说9被推到了最右端。第一趟结束，以此类推，比较出后面的数字大小。
Ps：会默认按照一种顺序排列
举例1：
第一种方式:
list=[1,3,2,0]
length =len(lst):
for i in range(length)
for j in range(length -1 -i):
if lst[j] > lst[j+1]:
tmp =lst[j]
lst[j]=lst[j + 1]
lst[j+1] = tmp
#lst[j],lst[j+1]=lst[j+1],lst[j]
print(list)
输出结果:
[0,1,2,3]
第二种方式：
list=[1,3,2,0]
length =len(lst):
for i in range(length)
for j in range(length -1 -i):
if lst[j] > lst[j+1]:
#tmp =lst[j]
#lst[j]=lst[j + 1]
#lst[j+1] = tmp
lst[j],lst[j+1]=lst[j+1],lst[j]
print(list)
输出结果:
[0,1,2,3]
特别强调，右边先计算。算完之后，在分别对应不能先给值，必须要计算完成之后再一一对应给值。
赋值表达式是右边所有的计算完成之后，还能给左边对应。这是基本原则。
举例2：
简单冒泡实现：
num_list=[
[1,9,4,5,7,8,6,2,3]
[1,2,3,4,5,6,7,8,9]
]
nums = num_list[1]
print(nums)
length=len(nums)
count swap = 0
count = 0
#bubble_sort
for i in range(length):
for j in range(length-i-1):
count += 1
if nums[j] >nums[j+1]:
tmp =nums[j]
nums[j] =nums[j+1]
nums[j+1] =tmp
count_swap += 1
print(nums,count-swap,count)
//借助了一个变量的空间就足够
Ps:
1. 必须知道比较多少回，以及交换多少回，比较的时间比较短，交换比较浪费时间，直接用索引去执行，交换越少，效率越高。
2.比较字符串的话，就必须比较他们的阿斯克码，一位一位的比较。
Ps：对于[1,2,3,4,5,6,7,8,9]两两比较没有交换，则表示它已经符合了要求。
第一串代码：
num_list=[
[1, 9, 8,5,6,7,4,3,2],
[1,2,3,4,5,6,7,8,9]
]
nums=num_list[0]
print (nums)
length = len (nums)
f1ag = False
count_swap =0
count =o
#bubble_sort
for i in range ( length) :
for j in range (length-i-1):
count +=1
if nums[j]>nums[j+1]:
tmp = nums[j]
nums[j]= nums[j+1]nums[j+1]=tmp
flag=Txue
#swaPPed
count_swap +=1
if not flag:
break
print(nums,count_swap,count)
第二串代码：
num_list =[
[1,9,8,5,6,7,4,3,2]
[1,3, 4, 5, 6,7,8,9]
[1,2, 3,4, 5,6,7,9,8]
]
nums=num_list[2]
print (nums)
length = len (nums)
count_swap =0
count =o
#bubble sort
for i in range (length):
flag = False
for j in range (length-i-1):
count +=1
if nums [j] >nums[j+1]:
tmp =nums[j]
nums[j] = nums [j+1]
nums[j+1]=tmp
flag=Ture #Swapped
count_swap +=1
if not flag:
break
print (nums,count_swap,count)
Ps：优化实现第一串代码有问题，第二串代码正确。第一串代码的 flag=False 没有被调用。第二串代码中重新定义了。第二串代码的优化在于有一个简便的算法。
例如：
list=[1,3,2,0]
length =len(lst):
for i in range(length)
for j in range(length -1 -i):
if key(lst[j]) > key(lst[j+1]):
#tmp =lst[j]
#lst[j]=lst[j + 1]
#lst[j+1] = tmp
#lst[j],lst[j+1]=lst[j+1],lst[j]
print(list)
输出结果:
[0,1,2,3]
在 jupyter 中操作：
.输入：
print(str)
输出结果：‘str’>
.输入：
type(print(str))
输出结果：
‘str’>
Out[10]:NoneType
升序
n个数从左至右,编号从0开始到n-1，索引0和1的值比较,如果索引0大,则交换两者位置,如果索引1大,则不交换。
继续比较索引1和2的值,将大值放在右侧。直至n-2和n-1比较完，第一轮比较完成。
第二轮从索引|0比较到n-2 ,因为最右侧n-1位置上已经是最大值了。依次类推,每一轮都会减少最右侧的不参与比较,直至剩下最后2个数比较。
降序
和升序相反
九、 冒泡法总结
冒泡法，它是交换排序法中的一种。它也是三种基本算法中最简单的一种。它的整个过程，就跟排大小个相同。
要把前面说的例子以及练习要做深刻理解。写的时候很简单，两层循环加一个交换，两个判断加一个交换。交换的越少，效率就会越高。交换不可避免。
冒泡法需要数据一轮轮比较
可以设定一个标记判断此轮是否有数据交换发生,如果没有发生交换,可以结束排序,如果发生交换，继续下一-轮排序
最差的排序情况是,初始顺序与目标顺序完全相反，遍历次数...-1之 和n(n-1)/2
最好的排序情况是,初始顺序与目标顺序完全相同,遍历次数n-1
时间复杂度0(n2)
n * (n - i -1) =n**2 -ni -n
n*n*n =n**3
空间复杂度
O（1）
print()
if bool (1):
pass
a[1] = 5
n**2 O(n) O(1)
