二分查找
二分查找只适用于有序的数组（list）,每次查找的数据规模都为原来规模的一半，直到找到为止。其时间复杂度为O(logN)。
假设有一个包含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 简单选择排序（一元选择排序）
通过假设0号索引元素为最大值，之后对剩下的元素逐一比较，将最大值的索引赋予一个临时变量。最后判断假设最大值的索引是否改变，若改变则将最大值交换。
算法代码：
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 二元选择排序
在一元选择排序基础上的改进，二元选择排序是分别固定最大值与最小值到两端。这样排序效率更高。
算法代码：
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）插入排序
将待排序对象分为两个部分处理，分别是已排序区与未排序区。取未排序元素与已排序的元素作比较，如果未排序元素小于已排序的元素，则将其插入到已排序之后。
插入排序并不适合用在数据规模很大的对象上，随着已排序部分的规模逐渐增大，其插入一个元素的效率不高（如果使用list），因为索引会逐个调整。而且当内存空间中有大量碎片且需要连续内存空间时，可能会将数据整体迁移到其他连续内存区域。
此外，通过二分查找可以稍微优惠查找效率。
算法代码：
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:])
网友评论