整体概述
本篇文章主要涉及：
- 搜索算法：顺序搜索和二分搜索；
- 排序算法：冒泡排序、选择排序、插入排序、希尔（谢尔）排序、归并排序、快速排序
我将把算法的原理和优劣写出，方便大家在用的时候可以针对不同情况因地制宜的选择合适的算法。
搜索算法
1.顺序搜索（无序列表）
原理：
- 从列表的第一个元素开始，沿着列表的默认顺序逐个查看。默认顺序为：0,1,2,3,4,…
- 如果在列表中的某个位置找到了要搜索的元素，则返回True；如果搜索完整个列表没有找到要搜索的元素，则返回False
代码：
def sequentialSearch(alist,item):
found=False
index=0 #列表索引
while index<len(alist) and not found:
if alist[index]==item:
found=True
else:
index+=1
return found
分析：
- 要确定一个元素不在列表内，要对整个列表进行搜索，一共搜索n次
- 该搜索算法最好的情况是只搜索1次，最坏的情况是搜索n次，所以该算法的时间复杂度为O(n)
2.顺序搜索（有序列表）
原理：
- 从列表的第一个元素开始，沿着列表的默认顺序逐个查看。默认顺序为：0,1,2,3,4,…
- 如果在列表中的某个位置找到了要搜索的元素，则返回True；如果搜索完整个列表没有找到要搜索的元素，则返回False
- 与无序列表不同的是：在搜索过程中，如果列表的某项大于要搜索的元素时，直接返回False，因为该项后的元素都大于要搜索的元素
代码：
def orderedsequentialSearch(alist,item):
stop=False
found=False
index=0
while index<len(alist) and not found and not stop:
if alist[index]==item:
found=True
else:
if alist[index]>item:
stop=True
else:
index+=1
return found
分析：
- 最好情况1次就可以成功，最坏的情况需要n次，所以算法复杂度为O(n)
- 当列表中不存在目标元素时，有序排列元素才会提高顺序搜索的效率。也就是说，列表不存在目标元素时，利用有序列的特性，当到达大于目标元素的位置时，可以不用执行列表位置的搜索。
3.二分搜索（有序列表）
原理：
-
从列表的中间位置开始搜索
-
搜索规则：
- 如果中间位置元素大于要搜索的元素，则直接舍去列表的右半部分，只考虑列表的左半部分
- 如果中间位置元素小于要搜索的元素，则直接舍去列表的左半部分，只考虑列表的右半部分
- 如果中间位置元素等于要搜索的元素，则直接返回True
-
当只考虑列表的左（右）半部分时，不断重复第2步的步骤，直到中间位置超出列表（递归调用）
代码：
def binarySearch(alist,item):
found=False
first=0
last=len(alist)-1
while not found and first<=last:
midpoint=(first+last)//2
if alist[midpoint]==item:
found=True
else:
if alist[midpoint]>item:
last=midpoint-1
else:
first=midpoint+1
return found
分析：
- 第一次比较之后剩下 n 2 \frac{n}{2} 2n个元素，第二次比较之后剩下 n 4 \frac{n}{4} 4n，…，第i次比较之后剩下 n 2 i \frac{n}{2^i} 2in个元素，所以算法复杂度为：O(logn)
- 二分搜索通常优于顺序搜索
- 当列表的长度过大或过小时，要将列表转换成有序列表可能会引起不必要的浪费，所以这时候选取顺序搜索可能会更好
附加：递归调用版本的代码
def binarySearch(alist,item):
if len(alist)==0:
return False
else:
midpoint=len(alist)//2
if alist[midpoint]==item:
return True
else:
if alist[midpoint]>item:
return binarySearch(alist[:midpoint],item)
else:
return binarySearch(alist[midpoint+1:],item)
排序算法
1.冒泡排序
原理：
- 比较相邻的两个元素，将不合适的位置进行交换，所以该算法的交换次数比较多
- 第一次遍历将列表的最大值放在最后一个位置，第二次遍历将第二大的值放在倒数第二个位置，循环往复，达到排序的目的
代码：
def bubbleSort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp=alist[i+1]
alist[i+1]=alist[i]
alist[i]=temp
分析：
- 遍历的次数为n-1,n-2,…,1和每个遍历的比较个数为n-1,n-2,…,1，所以该算法的复杂度为 O ( n 2 ) O(n^2) O(n2)
- 冒泡算法被认为是效率最低的排序算法，因为在确定最终的位置之前要不断的交换位置。
- 如果列表只需要进行几次遍历就可以有序，那么此时选择冒泡算法是最合适的。只需要判断列表是否还有需要交换的地方，如果没有，说明列表有序，则直接可以中断程序，返回列表，提高效率。
对于上述第3步，通过列表是否有序而减少计算步骤的算法，称之为短冒泡，代码如下：
def ShotbubbleSort(alist):
exchange=True
passnum=len(alist)-1
while passnum>0 and exchange:
exchange=False
for i in range(passnum):
if alist[i]>alist[i+1]:
exchange=True
temp=alist[i]
alist[i]=alist[i+1]
alist[i+1]=temp
passnum-=1
2.选择排序
原理：
- 选择排序是冒泡排序的改进版本。之前的冒泡排序在每次遍历的时候都要进行多次交换已达到将该次遍历的最大值放置到列表末尾的目的，而选择排序中只需要进行一次交换，即直接将该次遍历最大值放置到列表末尾。
代码：
def selectSort(alist):
for passnum in range(len(alist)-1,0,-1):
max_index=0
for i in range(1,passnum+1):
if alist[i]>alist[max_index]:
max_index=i
temp=alist[max_index]
alist[max_index]=alist[passnum]
alist[passnum]=temp
分析：
- 由于减少了交换次数，所以一般选择排序比冒泡算法更快
- 虽然交换次数减少了，但是遍历次数和比较次数没有发生变换，所以选择排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
3.插入排序
原理：
- 将列表中前k个元素排好序后，将列表中的第k+1个元素插入到有序的前k个元素组成的子列表的合适位置，使现在的k+1个元素组成有序表。
代码：
def insertionSort(alist):
for index in range(1,len(alist)): #进行比较的索引值：1,..,n-1
currentvalue=alist[index]
position=index
while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position-=1
alist[position]=currentvalue
分析：
- 遍历次数是n，比较次数是n，所以算法复杂度为 O ( n 2 ) O(n^2) O(n2)
- 在基准测试中，交换所花的时间是移动的3倍，所以插入排序算法的性能非常不错，平常使用排序算法可以优先考虑
4.希尔排序
原理：
- 通常我们选取 n 2 、 n 4 、 n 8 \frac{n}{2}、\frac{n}{4}、\frac{n}{8} 2n、4n、8n…对列表进行划分，然后将每次划分的子列表进行插入排序。当最后划分的长度为1时，实际上就是对现在的列表进行插入排序，不过由于经过前面步骤，目前的插入排序的效率非常高。
- 我们也可以采取
2
k
−
1
2^k-1
2k−1的划分列表的方法，此时时间复杂度更低。
代码：
def shellSort(alist):
sublistcount=len(alist)//2 #子列表的长度
while sublistcount>0:
for startpoint in range(sublistcount):
insertsort(alist,startpoint,sublistcount)
sublistcount=sublistcount//2
def insertsort(alist,start,gap):
for index in range(start+gap,len(alist),gap):
currentvalue=alist[index]
position=index
while position>0 and alist[position-gap]>alist[position]:
alist[position]=alist[position-gap]
position-=gap
alist[position]=currentvalue
分析：
- 乍看之下，希尔排序的复杂度要比插入排序大，因为当分割的长度为1时，要进行一次完整的插入排序。但是因为之前对子列表的预处理，所以最后一步的插入排序效率非常高，甚至说只需要几步就可完成，所以希尔排序的时间复杂度介于 O ( n ) 和 O ( n 2 ) O(n)和O(n^2) O(n)和O(n2)之间。
- 上述提到的使用增量 2 k − 1 2^k-1 2k−1的情况时，算法的复杂度为 O ( n 3 2 ) O(n^{\frac{3}{2}}) O(n23)
5.归并排序
原理：
- 排序的两个过程：拆分和合并
- 拆分：·将列表从中间一分为二，分为两个子列表。之后这两个子列表再各自从中间一分为二，不断重复，直到最后子列表的长度为1.此时默认子列表有序。其实也好理解，列表长度为1，说明列表中只有一个元素，肯定是有序的。
- 合并：当子列表的长度为1时，需要执行合并操作。也就是将最后得到的两个长度为1的列表排序，之后再将排好的长度为2的列表与另一个长度为2的列表排序。不断扩大列表的长度，直到将整个列表排好序。
代码：
def mergeSort(alist):
print('split:',alist)
if len(alist)>1:
mid=len(alist)//2
lefthalf=alist[:mid]
righthalf=alist[mid:]
mergeSort(lefthalf) #左半部分列表拆分
mergeSort(righthalf) #右半部分列表拆分
i=j=k=0
while i<len(lefthalf) and j<len(righthalf):
if lefthalf[i]<righthalf[j]:
alist[k]=lefthalf[i]
i+=1
else:
alist[k]=righthalf[j]
j+=1
k+=1
while i<len(lefthalf):
alist[k]=lefthalf[i]
i+=1
k+=1
while j<len(righthalf):
alist[k]=righthalf[j]
j+=1
k+=1
print('merge:',alist)
分析：
- 需要logn次拆分，每次拆分需要进行n次操作，所以该算法的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
- 由于该算法在切分的时候需要存储切分下来的列表，所以通常需要的存储空间比较大，甚至有时候会比一般的排序算法需要的存储空间大一倍。
6.快速排序
原理：
- 排序原理
- 首先找到一个基准点，也称分割点，用来帮助分割列表。分割点的选取一般使用三数取中法，即选取列表的首、中、尾三数中的中位数作为分割点
- 进行分区操作，使得列表的左边都是小于分割点的元素，列表的右边都是大于分割点的元素
- 将列表分成小于分割点和大于分割点的两个子列表，重复1,2步，即再次使用快速排序
- 直到分割的子列表的长度小于0，结束
代码：
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
splitpoint=partition(alist,first,last)
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)
def partition(alist,first,last):
pivotvalue=alist[first]
leftmark=first+1
rightmark=last
do=False
while not do:
while rightmark>=leftmark and alist[leftmark]<=pivotvalue:
leftmark+=1
while rightmark>=leftmark and alist[rightmark]>=pivotvalue:
rightmark-=1
if rightmark<leftmark:
do=True
else:
temp=alist[leftmark]
alist[leftmark]=alist[rightmark]
alist[rightmark]=temp
temp=alist[rightmark]
alist[rightmark]=alist[first]
alist[first]=temp
return rightmark
分析：
- 对于一个长度为n的列表，如果每次分割都发生在列表的中部，则会切分logn次。而每次切分都要进行n次比较，所以算法的复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
- 重要一点是，快速排序不会像归并排序那样需要额外的空间，所以有能力的话，建议大家使用快速排序。
总结
个人认为，所有的算法都有各自的优点和缺点，针对不同的情况应该选取不同的算法，即使是最简单、最笨的算法也有其独特的用处，就像生活中的每个人一样，总会存在这样一个领域，你在里面可以发光发热。
扫一扫
480
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
