从零开始学Python-day3

reko_3

　　Python--Day3
　　学习要有定位,明确目标地去学习。---leaves
　　python02---list知识
　　一 list的概念
　　列表的概念：列表可以完成大多数集合类的数据结构实现。它支持字符，数字，字符串甚至可以包含列表（所谓嵌套)。
　　list  array  数组 是同一种数据
　　list的优点：
　　可遍历
　　有序的
　　可以切片
　　快速生成list的方法  ： range(数字)   list("字符串")
##列表中可以嵌套任意类型的数据　　
In [4]: arr = ['C',1,2,True,False,[2,3,['js','html']],'python']
　　

　　

　　
##range()快速生成list
　　
In [1]: arr = range(10)
　　
In [2]: arr
　　
Out[2]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
　　

　　
##list()快速生成list
　　
In [7]: arr1 =  list('python')
　　
In [8]: arr1
　　
Out[8]: ['p', 'y', 't', 'h', 'o', 'n']
　　

　　

　　
##可以通过索引获取值
　　
In [5]: arr[5]
　　
Out[5]: [2, 3, ['js', 'html']]
　　

　　
##索引值也能为负值
　　
In [6]: arr[-1]
　　
Out[6]: 'python'
　　

　　
##in  判断元素是否在list中
　　
In [8]: arr1
　　
Out[8]: ['p', 'y', 't', 'h', 'o', 'n']
　　
In [10]: 'x' in arr1
　　
Out[10]: False
　　
In [11]: 'p' in arr1
　　

　　
##小练习  自己实现in的功能
　　
In [14]: result = 0#用来存放判断后的结果
　　
In [15]: for i in arr1 :
　　
    ...:     if 'x' == i:
　　
    ...:         result = "True"
　　
    ...:     result = "False"
　　
    ...: print result
　　
    ...:
　　
    ...:
　　
False
　　二、list的方法(主要针对数字)
　　len() ====>list长度
　　max() ====>list 最大值
　　min() ====>list最小值
　　del() ====>删除索引值
　　列表可以使用'+'拼接和使用'*'重复
###del 用法 ==直接删除值　　
In [32]: arr
　　
Out[32]: ['C', 1, 2, True, False, [2, 3, ['js', 'html']], 'python']
　　
In [33]: del arr[1]
　　
In [34]: arr
　　
Out[34]: ['C', 2, True, False, [2, 3, ['js', 'html']], 'python']
　　

　　
##list 可以使用+拼接
　　
In [35]: l1 = ['c','d']
　　
In [36]: l2 = ['1',2]
　　
In [37]: l1 + l2
　　
Out[37]: ['c', 'd', '1', 2]
　　

　　
##list 可以使用+拼接
　　
In [35]: l1 = ['c','d']
　　
In [36]: print l1 * 2
　　
Out[37]: ['c', 'd','c','d']
　　

　　
##list修改值 ==>直接修改
　　
In [39]: l1 = ['c','d']
　　
In [40]: l1[1]="hello"
　　
In [41]: l1
　　
Out[41]: ['c', 'hello']
　　三、排序
　　排序：编程世界的游戏规则。
　　各种排序算法的演示动画网址(民族舞蹈讲述排序)：
　　http://www.bilibili.com/video/av4722429/index_5.html
　　各种算法的动画演示(http://www.atool.org/sort.php)
　　3.1 冒泡排序
　　冒泡排序的原理：相邻两个元素挨个对比,如果一个元素比右边大,则交换位置。
　　冒泡排序过程如下：
　　arr = [3 , 5, 1 ,32 , 4]
　　第一次  3和5比 不变       [3 , 5, 1 ,32 , 4]
　　5和1比 交换       [3 ,1 , 5 ,32 , 4]
　　5和32比 不变       [3 ,1 , 5 ,32 , 4]
　　32和4比交换        [3 ,1 , 5 , 4 ,32]
　　第二次    在[3 ,1 , 5 , 4 ,32]基础上
　　3 和1 比较  交换  [1 ,  3 , 5 , 4 ,32]
　　3 和5 比较  不变  [1 ,  3 , 5 , 4 ,32]
　　5 和4 比较  交换  [1 ,  3 , 4 , 5 ,32]
　　第三次  在[1 ,  3 , 4 , 5 ,32] 基础上
　　1和3比较  不变  [1 ,  3 , 4 , 5 ,32]
　　3和4比较  不变  [1 ,  3 , 4 , 5 ,32]
　　第四次  [1 ,  3 , 4 , 5 ,32]
　　1 和 3 比较不变  [1 ,  3 , 4 , 5 ,32]
　　最终的冒泡排序代码如下：
[root@xiaowei 02]# cat maopao.py　　
arr = [33,3 , 5, 1 ,32 , 4]
　　
print arr
　　
length = len(arr)
　　
print length
　　
for j in range(length-1):
　　print "di %s ci xun huan :" %j
　　for i in range(length-1-j):
　　if arr > arr[i+1]:
　　arr,arr[i+1] = arr[i+1],arr
　　print arr
　　
print "The final result is %s" % arr
　　

　　
[root@xiaowei 02]# python maopao.py
　　
[33, 3, 5, 1, 32, 4]
　　
6
　　
di 0 ci xun huan :
　　
[3, 5, 1, 32, 4, 33]
　　
di 1 ci xun huan :
　　
[3, 1, 5, 4, 32, 33]
　　
di 2 ci xun huan :
　　
[1, 3, 4, 5, 32, 33]
　　
di 3 ci xun huan :
　　
[1, 3, 4, 5, 32, 33]
　　
di 4 ci xun huan :
　　
[1, 3, 4, 5, 32, 33]
　　
The final result is [1, 3, 4, 5, 32, 33]
　　
[root@xiaowei 02]#
　　3.2 选择排序
　　选择排序原理：拿一个元素分别与剩下的元素对比,选出最小或最大的
###选择排序实现代码如下：　　
[root@xiaowei 02]# cat xuanze.py
　　
arr = [3 , 5, 1 ,32 , 4]
　　
print "The   sorted  arr  is   : %s" % arr
　　
l = len(arr)
　　
print l
　　
for i in range( l-1 ):
　　print "di  %s ci xuanze paixu " %i
　　#jiang a qu chu lai  fen bie yu  houbian bijiao
　　for j in range(i+1,l):
　　if arr > arr[j]:
　　arr ,arr[j] = arr[j],arr
　　print arr
　　
print "*" * 40
　　
print arr
　　
[root@xiaowei 02]# python xuanze.py
　　
The   sorted  arr  is   : [3, 5, 1, 32, 4]
　　
5
　　
di  0 ci xuanze paixu
　　
[1, 5, 3, 32, 4]
　　
di  1 ci xuanze paixu
　　
[1, 3, 5, 32, 4]
　　
di  2 ci xuanze paixu
　　
[1, 3, 4, 32, 5]
　　
di  3 ci xuanze paixu
　　
[1, 3, 4, 5, 32]
　　
****************************************
　　
[1, 3, 4, 5, 32]
　　
[root@xiaowei 02]#
　　3.3 算法扩展
　　算法的复杂度： 算法两方面：1复杂度 2.稳定性
　　复杂度分为时间复杂度和空间复杂度
　　冒泡排序==>复杂度o（n^2）  稳定性高
　　希尔排序           ===>复杂度  不知道。目前还无法算出来
　　3.4 插入排序
　　插入排序的原理：是通过构建有序序列,对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
　　插入排序图解：

　　小知识：如何利用range()使list倒序：
In [13]: for i in range(3,0,-1):　　
    ...:     print i
　　
    ...:
　　
    ...:
　　
3
　　
2
　　
1
　　插入排序代码(加深理解)
[root@xiaowei 02]# cat test.py　　
def InsertSort(mylist):
　　
    size = len(mylist)
　　
    i = 1
　　
    for i in range(1, size):
　　print "===================================di %s ci xun huan ======================="  % i
　　print "mylist=== mylist[i-1] : %s == %s"  %(mylist,mylist[i-1])
　　
        if mylist < mylist[i - 1]:
　　
            tmp = mylist
　　
            j = i - 1
　　print "****j : %s" %j
　　
            mylist[j + 1] = mylist[j]
　　

　　
            j = j - 1
　　
            while j >= 0 and mylist[j] > tmp:
　　
                 mylist[j + 1] = mylist[j]
　　
                 j = j - 1
　　
            mylist[j + 1] = tmp
　　
#mylist0 = [12, 11, 13, 1, 2, 4, 3]
　　
mylist0 = [6 , 5 , 3 , 1 , 8 , 7 , 2 , 4]
　　
InsertSort(mylist0)
　　
print(mylist0)
　　
[root@xiaowei 02]# python test.py
　　
===================================di 1 ci xun huan =======================
　　
mylist=== mylist[i-1] : 5 == 6
　　
****j : 0
　　
===================================di 2 ci xun huan =======================
　　
mylist=== mylist[i-1] : 3 == 6
　　
****j : 1
　　
===================================di 3 ci xun huan =======================
　　
mylist=== mylist[i-1] : 1 == 6
　　
****j : 2
　　
===================================di 4 ci xun huan =======================
　　
mylist=== mylist[i-1] : 8 == 6
　　
===================================di 5 ci xun huan =======================
　　
mylist=== mylist[i-1] : 7 == 8
　　
****j : 4
　　
===================================di 6 ci xun huan =======================
　　
mylist=== mylist[i-1] : 2 == 8
　　
****j : 5
　　
===================================di 7 ci xun huan =======================
　　
mylist=== mylist[i-1] : 4 == 8
　　
****j : 6
　　
[1, 2, 3, 4, 5, 6, 7, 8]
　　
[root@xiaowei 02]#
　　四、list的切片
　　list的切片：切片功能强大,可读性差。主要用于获取连续数据
　　切片的原则：起点按照切片方向上的找到终点
list的具体切片小例子：　　

　　
Out[49]:arr =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
　　
In [50]: arr[:4]
　　
Out[50]: [0, 1, 2, 3]
　　

　　
In [51]: arr[6:]
　　
Out[51]: [6, 7, 8, 9]
　　

　　
In [52]: arr[::2]
　　
Out[52]: [0, 2, 4, 6, 8]
　　

　　
In [53]: arr[::-1]
　　
Out[53]: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
　　

　　
切片可以删除list元素
　　
In [54]: arr[1:4] = ['a']
　　
In [55]: arr
　　
Out[55]: [0, 'a', 4, 5, 6, 7, 8, 9]
　　

　　
##增加元素
　　
In [56]: arr[1:1] = ['1','2','3']
　　
In [57]: arr
　　
Out[57]: [0, '1', '2', '3', 'a', 4, 5, 6, 7, 8, 9]
　　五、list的其他常用方法
　　append()        追加元素
　　count()       统计list中某个元素出现的次数
　　extend()      没有返回值,修改原数组
　　index()       没有返回值,查找某个元素的索引
　　insert(1,'value')  在index出插入值value
　　pop()       弹出,默认弹出最后一个值,返回
　　remove()      remove(value)删除具体值
　　reverse()       反向list
list 其他常用方法的举例　　

　　
##append举例
　　
In [60]: arr = [0, 1, 2]
　　
In [61]: arr.append('!')
　　
In [62]: arr
　　
Out[62]: [0, 1, 2, '!']
　　

　　
##count的使用
　　
In [63]: arr = [1,2,1,3]
　　
In [64]: arr.count(1)
　　
Out[64]: 2
　　

　　
##extend的使用
　　
In [65]: arr1 =  list('python')
　　
In [66]: arr2 = range(2)
　　
In [67]: arr1.extend(arr2)
　　
In [68]: arr1
　　
Out[68]: ['p', 'y', 't', 'h', 'o', 'n', 0, 1]
　　

　　
##index的使用
　　
In [68]: arr1
　　
Out[68]: ['p', 'y', 't', 'h', 'o', 'n', 0, 1]
　　
In [70]: arr1.index(0)
　　
Out[70]: 6
　　
In [71]: arr1.index('p')
　　
Out[71]: 0
　　

　　
##insert的用法
　　
In [73]: arr2
　　
Out[73]: [0, 1]
　　
In [74]: arr2.insert(1,'hello')
　　
In [75]: arr2
　　
Out[75]: [0, 'hello', 1]
　　

　　
###pop()默认删除最后一个,也可以提供一个索引值弹出指定元素
　　
In [75]: arr2
　　
Out[75]: [0, 'hello', 1]
　　
In [76]: arr2.pop()
　　
Out[76]: 1
　　
In [77]: arr2.pop(0)
　　
Out[77]: 0
　　
In [78]: arr2
　　
Out[78]: ['hello']
　　六、队列和桟
　　队列:  先入先出  ===>append()和pop(0)
　　桟 :   先入后出  ===>append()和pop()
　　小练习：
　　#采用持续队列,让用户输入东西：
　　如果用户输入的是add
　　再让用户输入一件事情(吃饭)
　　如果用户输入的是do
　　把之前输入的值打印出来。
　　如果没事情可做,就打印nothing
　　如果输入的是其他值,则终止循环
具体代码如下：==>对应先入后出的思想　　
[root@xiaowei 02]# cat 01.py
　　
store = []
　　
while True:
　　x = raw_input("qing shu ru action: ")
　　if x == "add":
　　y = raw_input("qing shu ru thing: ")
　　store.append(y)
　　print store
　　elif x == "do":
　　print "****do "
　　print len(store)
　　if len(store) != 0:
　　print store.pop()    ##先入后出思想。
　　##先入先出思想。pop(0)
　　else:
　　print "nothing"
　　else :
　　print "The final result is %s" %store
　　break
　　

　　
###执行代码过程如下：
　　
[root@xiaowei 02]# python 01.py
　　
qing shu ru action: add
　　
qing shu ru thing: 111
　　
['111']
　　
qing shu ru action: add
　　
qing shu ru thing: 222
　　
['111', '222']
　　
qing shu ru action: do
　　
****do
　　
2
　　
222
　　
qing shu ru action:
　　
The final result is ['111']
　　七、数组、链表
　　数组  1,2,3,4,5
　　优点： 根据索引寻找比较快,从最后追加也特别快.命中CPU缓存概率比较大
　　缺点:插入很慢, 删除也很慢。(插入的话,后边元素要依次往后移)
　　链表：1 ---> 2  ----> 3 ---->4 --->5
　　链表的查找很慢,插入很快,删除也很快。尾部追加也很快
　　哈希表  d = {"name": "hello"}  复杂度  O(1)
　　复杂度为O(1),可以通过具体的值来建立关系(python的dict)
　　本身没有顺序,查找,删除,修改都很快key ===>var1
　　FNV哈希
　　MD5哈希
　　一致性哈希
　　八‘list与dict的区别
　　list 和dict的区别
　　相同：都可以存储复杂的数据结构,可以嵌套列表、字典等
　　不同：
　　list是有序的,通过index索引值来获取元素,赋值。删除,增加值
　　dict是无序的,key-value的键值对。通过key来获取value的值。
　　延伸
　　dict 和 json的区别
　　dict是Python中具体的数据结构
　　json：是一种数据交换格式(标准)json数据
　　九、练习：
###练习1 ：数组去重：　　
###小练习：[1,2,3,4,2,12,3,3,2,13,21,2,333,4]
　　
In [84]: arr = [1,2,3,4,2,12,3,3,2,13,21,2,333,4]
　　
In [86]: arr_1= []
　　
In [87]: for i in arr:
　　
    ...:     if i in arr_1:
　　
    ...:         pass
　　
    ...:     else:
　　
    ...:         arr_1.append(i)
　　
    ...: print arr_1
　　
    ...:
　　
[1, 2, 3, 4, 12, 13, 21, 333]
　　

　　
###小练习2
　　
###arr1 = [1,2,3,4,2,12,3,3,2,13,21,2,333,4]
　　
###arr2 = [2,1,4,32,452,21,14,333]
　　
###求arr1和arr2的交集
　　
In [92]: arr1 = [1,2,3,4,2,12,3,3,2,13,21,2,333,4]
　　
In [93]: arr2 = [2,1,4,32,452,21,14,333]
　　
In [94]: arr_r = []
　　
In [95]: for i in arr1:
　　
    ...:     if (i in arr2) and (i not in arr_r):
　　
    ...:         arr_r.append(i)
　　
    ...: print arr_r
　　
    ...:
　　
[1, 2, 4, 21, 333]
　　十、二分思想找到range(100000)中任意一个数字
二分思想：一个排好的list中,找到指定数字。　　
arr = range(10000)
　　

　　
x = raw_input("qing shuru yi ge shuzi ")
　　
start = 0
　　
end = len(arr)-1
　　
count = 0
　　
while True :
　　
        count += 1
　　
        half = ( start + end )/2
　　
        if int(x) > arr[half]:
　　
                start = half
　　
        elif int(x) < arr[half]:
　　
                end = half
　　
        else :
　　
                print "The index value is %s" %half
　　
                break
　　
print "Total found  %s times " %count