一、快速排序（用得最多）

 

 

1.1 算法思路

  有一个游标Low和游标High，分别指向第一个元素和最后一个元素，先取一个Mid_value = 第一个值，然后Low指向的数据和Mid_value比较一下，如果Low < Mid_value, 那么Low +=1 ， 因为小的值是排在左边的，否则，Low不动，High指向的数据和Mid_value比较一下，如果High < Mid_value， 那么High -= 1, 因为大的值是排在右边的。当High和Low重合的时候，则停止，把Mid_value的值放到这里来。然后，达到目标：Mid_value左边的值都比Mid_value小，右边的值都比Mid_value大，然后对于左边和右边，继续做一样的操作，直到左边/右边只剩下一个数，就停止（递归方式）  

1.2 代码实现：

def quick_sort(alist): """快速排序""" n = len(alist) #mid_value 为第一个数的值 mid_value = alist[0] #游标low从第一个数出发 low = o #游标high从最后一个数出发 high = n-1 while low < high: while low < high and alist[high] >= mid_value: #当high指向的数比mid_value大的时候，high向左移 high -= 1 #左移动的同时，把这个值赋值给low alist[low] = alist[high] while low < high and alist[low] < mid_value: low += 1 alist[high] = alist[low] #从循环退出时，low == high, 把mid_value赋值给low/high alist[low] = mid_value #下面注释掉的两行，如果这样的话，相当于不是对alist整个列表来操作，变成分开来操作了，是操作两个新的列表，为了每次都是对alist操作，所以引入另外两个参数：first、last #quick_sort(alist(:low-1)) #quick_sort(alist(low+1 :))

 

1.3 修改（引入first、last）：

def quick_sort(alist，first,last): """快速排序""" #加入终止条件 if first >= last: return #mid_value 为第一个数的值 mid_value = alist[0] #游标low从第一个数出发 low = first #游标high从最后一个数出发 high = last while low < high: while low < high and alist[high] >= mid_value: #当high指向的数比mid_value大的时候，high向左移 high -= 1 #左移动的同时，把这个值赋值给low alist[low] = alist[high] while low < high and alist[low] < mid_value: low += 1 alist[high] = alist[low] #从循环退出时，low == high, 把mid_value赋值给low/high alist[low] = mid_value #对low左边的列表执行快速排序 quick_sort(alist，first,low-1) #对low右边的列表执行快速排序 quick_sort(alist,low+1,last) if __name__ == "__main__": alist = [54,26,93,17,77,31,44,55,20] quick_sort(alist,0,len(alist)-1) print(alist)

 

1.4 时间复杂度

  最优时间复杂度：O(nlogn)   最坏时间复杂度：O(n^2)   稳定性：不稳定  

二、归并排序

 

 

2.1 算法思路：

  拿上面例子举例，先对半分，每组再对半分，每组再对半分，直到分成每组只有一个值为止。然后开始归并，就是同样的过程反过来来一遍：组成两个为一组，组成四个为一组

  归并的时候有两个游标，一个left，一个right, left指的值和right指的值比较，具体流程如下：  

以这个为例  

比较left指的小还是right指的小，left指的小，所以拿出来，left再右移一位  

比较left指的小还是right指的小，right指的小，所以拿出来，right再左移一位  

最后把77放在最右边  

2.2 代码实现

def merge_sort(alist)： """归并排序""" #以下为拆分 n = len(alist) if n <= 1: return alist mid = n//2 # left 采用归并排序后形成的有序的新的列表 left_li = merge_sort(alist[:num]) # right 采用归并排序后形成的有序的新的列表 right_li = merge_sort(alist[num:]) # 将两个有序的子序列合并为一个新的整体 merge(left,right) #left right两个游标 left_pointer,right_pointer = 0, 0 #用来存放结果 result = [] # left/right游标指导最后一个的时候，循环停止 while left_pointer < len(left_li) and right_pointer < len(right_li): #即上面图片的步骤 if left_li[left_pointer] < right_li[right_pointer]: result.append(left_li[left_pionter]) else: result.append(right_li[right_pointer]) right_pointer += 1 result += left_li(left_pointer) result += right_li(right_pointer) return result if __name__ == "__main__": li = [54,26,93,17,77,31,44,55,20] print(li) sorted_li = merge_sort(li) print(li) print(sorted_li) #以下为合并

 

2.3 时间复杂度

  最优时间复杂度：O(nlogn)   最坏时间复杂度：O(nlogn)   稳定性：稳定

 

三、搜索

  搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的，因为该项目是否存在。 搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找

 

四、二分查找

  二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。  

4.1 代码实现

 

  前提是，已经排序，并且每个数据都相邻存储  

 4.1.1递归版本

def binary_search(alist, item): if len(alist) == 0: return False else: midpoint = len(alist)//2 if alist[midpoint]==item: return True else: if item<alist[midpoint]: return binary_search(alist[:midpoint],item) else: return binary_search(alist[midpoint+1:],item) if __name__ == "__main__": testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,] print(binary_search(testlist, 3)) print(binary_search(testlist, 13))

 

 4.1.2非递归版本（划分查找范围）

def binary_search(alist, item): first = 0 last = len(alist)-1 while first<=last: midpoint = (first + last)/2 if alist[midpoint] == item: return True elif item < alist[midpoint]: last = midpoint-1 else: first = midpoint+1 return False if __name__ == "__main__": testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,] print(binary_search(testlist, 3)) print(binary_search(testlist, 13))

 

4.2 时间复杂度

  最优时间复杂度：O(1)   最坏时间复杂度：O(logn)