列表查找：从列表中查找指定元素
输入：列表、待查找元素
输出：元素下标或未查找到元素
version 1 顺序查找：从列表中的第一个元素开始，顺序进行搜索，直到找到为止，复杂度为O(n)
version 2 二分查找：从有序列表中，通过待查值与中间值比较，以减半的方式进行查找，复杂度为O(logn)
list = [1,2,3,4,5,6,7,8,9]
element = 7
def ord_sear(list,element):
for i in range(0,len(list)):
if list[i] == element:
print('list[{0}]={1}'.format(i,element))
return i
else:
print('not found')
def bin_sear(list,element):
low = 0
high = len(list)-1
while low<=high:
mid = (low+high)//2
if element == list[mid]:
print('list[{0}]={1}'.format(mid,element))
return mid
elif element > list[mid]:
low =mid +1
else:
high =mid -1
return None
i = ord_sear(list,element)
j = bin_sear(list,element)
二分查找虽然在时间复杂度上优于顺序查找，但是有比较苛刻的条件，即列表必须为有序的。
列表排序：
列表排序是编程中一个最基本的方法，应用场景非常广泛，比如各大音乐、阅读、电影、应用榜单等，虽然python为我们提供了许多排序的函数，但我们那排序来作为算法的练习再好不过。
首先介绍的是最简单的三种排序方式：1 冒泡排序 2 选择排序 3 插入排序
冒泡排序：列表中每相邻两个如果顺序不是我们预期的大小排列，则交换。时间复杂度O(n^2)
list = [3,1,5,7,8,6,2,0,4,9]
def bubble(list):
high = len(list)-1 #定一个最高位
for j in range(high,0,-1):
exchange = False #交换的标志，如果提前排好序可在完整遍历前结束
for i in range(0,j):
if list[i]>list[i+1]: #如果比下一位大
list[i],list[i+1] = list[i+1],list[i] #交换位置
exchange = True #设置交换标志
if exchange == False:
return list # return list #返回列表
print(bubble(list))
选择排序：一趟遍历选择最小的数放在第一位，再进行下一次遍历直到最后一个元素。复杂度依然为O(n^2)
list = [3, 1, 5, 7, 8, 6, 2, 0, 4, 9]
def choice(list):
for i in range(0,len(list)):
min_loc = i
for j in range(i+1,len(list)):
if list[min_loc]>list[j]: #最小值遍历比较
min_loc = j
list[i],list[min_loc] = list[min_loc],list[i]
return list
print(choice(list))
插入排序：将列表分为有序区和无序区，最开始的有序区只有一个元素，每次从无序区选择一个元素按大小插到有序区中
list = [3,1,5,7,8,6,2,0,4,9]
def cut(list):
for i in range(1,len(list)):
temp = list[i]
for j in range(i-1,-1,-1): #从有序区最大值开始遍历 （i-1,起始范围 第一个-1代表索引，列表最后一个元素，规定范围 第二个-1代表方向，此处反向以1为单位取）
if list[j]>temp: #如果待插入值小于有序区的值
list[j+1] = list[j] #向后挪一位
list[j] = temp #将temp放进去
return list
print(cut(list))
def QuickSort(arr, firstIndex, lastIndex):
if firstIndex < lastIndex:
divIndex = Partition(arr, firstIndex, lastIndex)
QuickSort(arr, firstIndex, divIndex)
QuickSort(arr, divIndex + 1, lastIndex)
else:
return
def Partition(arr, firstIndex, lastIndex):
i = firstIndex - 1
for j in range(firstIndex, lastIndex):
if arr[j] <= arr[lastIndex]:
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[lastIndex] = arr[lastIndex], arr[i + 1]
return i
arr = [1, 4, 7, 1, 5, 5, 3, 85, 34, 75, 23, 75, 2, 0]
print("initial array:
", arr)
QuickSort(arr, 0, len(arr) - 1)
print("result array:
", arr)