二分查找
????????二分查找只適用于有序的數(shù)組（list）,每次查找的數(shù)據(jù)規(guī)模都為原來規(guī)模的一半，直到找到為止霉祸。其時間復(fù)雜度為O(logN)下面。
????????假設(shè)有一個包含1024個元素的列表，需要從中找到某個元素蚓曼。對比于簡單查找（遍歷元素）亲澡，二分查找最大只需查找10次就可以找到該元素，而簡單查找最糟糕情況纫版，則需要1023次才能找到床绪。
下面是二分查找的算法代碼：
def sel(lists, item):
? ? low_index = 0
? ? high_index = len(lists) - 1
? ? while low_index <= high_index:
? ? ? ? mid_index = (low_index + high_index) // 2
? ? ? ? if lists[mid_index] == item:
? ? ? ? ? ? return mid_index, count
? ? ? ? if lists[mid_index] < item:
? ? ? ? ? ? low_index = mid_index + 1
? ? ? ? else:
? ? ? ? ? ? high_index = mid_index -1
? ? return "Nothing"
nl = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
sel(nl, 16)
排序算法
1）冒泡排序
? ? ? ? 逐次比較相鄰的元素，并做交換其弊，直到排序完成癞己。排序效率不高。
算法代碼：
import random
l1 = [random.randrange(11) for i in range(10)]
print("orient num:{}".format(l1))
length = len(l1)
for i in range(length):
? ? for j in range(length - 1):
? ? ? ? if l1[j] > l1[j + 1]:
? ? ? ? ? ? l1[j], l1[j + 1] = l1[j + 1], l1[j]
print(l1)
2）選擇排序
2.1 簡單選擇排序（一元選擇排序）
????????通過假設(shè)0號索引元素為最大值梭伐，之后對剩下的元素逐一比較痹雅，將最大值的索引賦予一個臨時變量。最后判斷假設(shè)最大值的索引是否改變糊识，若改變則將最大值交換绩社。
算法代碼：
import random
l1 = [random.randrange(11) for i in range(10)]
print("orient num:{}".format(l1))
length = len(l1)
for i in range(length):
? ? tmp_index = i
? ? for j in range(i+1, length):
? ? ? ? if l1[j] > l1[tmp_index]:
? ? ? ? ? ? tmp_index = j
? ? if tmp_index != i:
? ? ? ? l1[i], l1[tmp_index] = l1[tmp_index], l1[i]
print(l1)
2.2 二元選擇排序
? ? 在一元選擇排序基礎(chǔ)上的改進摔蓝，二元選擇排序是分別固定最大值與最小值到兩端。這樣排序效率更高愉耙。
算法代碼：
import random
l = list(range(10))
random.shuffle(l)
length = len(l)
for i in range(length//2):
????count += 1
????maxindex = i
????minindex = -i-1
????minorigin = minindex
????for j in range(i+1, length-i):
????????if l[minindex] > l[-j-1]:
????????????minindex = -j-1
????????if l[maxindex] < l[j]:
????????????maxindex = j
????if i != maxindex:
????????l[maxindex], l[i] = l[i], l[maxindex]
????????if (i == minindex) or (i == length + minindex):
????????????minindex = maxindex
????????switch += 1
????if minorigin != minindex:
????????l[minindex], l[minorigin] = l[minorigin], l[minindex]
????????switch += 1
print(l)
print(count, switch)
3）插入排序
? ? ? ? 將待排序?qū)ο蠓譃閮蓚€部分處理贮尉，分別是已排序區(qū)與未排序區(qū)。取未排序元素與已排序的元素作比較朴沿，如果未排序元素小于已排序的元素猜谚，則將其插入到已排序之后。
????????插入排序并不適合用在數(shù)據(jù)規(guī)模很大的對象上赌渣，隨著已排序部分的規(guī)模逐漸增大魏铅，其插入一個元素的效率不高（如果使用list），因為索引會逐個調(diào)整坚芜。而且當(dāng)內(nèi)存空間中有大量碎片且需要連續(xù)內(nèi)存空間時览芳，可能會將數(shù)據(jù)整體遷移到其他連續(xù)內(nèi)存區(qū)域。
? ? ? ? 此外货岭，通過二分查找可以稍微優(yōu)惠查找效率路操。
算法代碼：
import random
l = list(range(18))
random.shuffle(l)
zero = [0]
nl = zero + l
print(nl)
length = len(nl)
for i in range(2, length):
? ? nl[0] = nl[i]
? ? # print("count:{} {}".format(i-1, nl))
? ? while i:
? ? ? ? if nl[0] < nl[i-1]:
? ? ? ? ? ? # print(nl[i-1],nl[i], end="\t")
? ? ? ? ? ? nl[i],?nl[i-1] = nl[i-1],?nl[0]
? ? ? ? ? ? # print(nl[i-1],nl[i], end="\t")
? ? ? ? i -= 1
print(nl[1:])
