归并排序
归并排序是采⽤分治法的⼀个⾮常典型的应⽤。归并排序的思想就是先递归 分解数组，再合并数组。
将数组分解最⼩之后，然后合并两个有序数组，基本思路是⽐较两个数组的 最前⾯的数，谁⼩就先取谁，取了后相应的指针就往后移⼀位。然后再⽐ 较，直⾄⼀个数组为空，最后把另⼀个数组的剩余部分复制过来即可。
归并排序的分析
6 5 3 1 8 7 2 4
[AppleScript] 纯文本查看 复制代码 def merge_sort(alist): if len(alist) <= 1: return alist # ⼆分分解 num = len(alist)/2 left = merge_sort(alist[:num]) right = merge_sort(alist[num:]) # 合并 return merge(left,right)
def merge(left, right): '''合并操作，将两个有序数组left[]和right[]合并成⼀个⼤的有序数组' ''
[AppleScript] 纯文本查看 复制代码 #left与right的下标指针 l, r = 0, 0 result = [] while l<len(left) and r<len(right): if left[l] < right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += left[l:] result += right[r:] return result
alist = [54,26,93,17,77,31,44,55,20] sorted_alist = mergeSort(alist) print(sorted_alist)
时间复杂度
最优时间复杂度：O(nlogn) 最坏时间复杂度：O(nlogn) 稳定性：稳定
常⻅排序算法效率⽐较
搜索
搜索是在⼀个项⽬集合中找到⼀个特定项⽬的算法过程。搜索通常的答案是 真的或假的，因为该项⽬是否存在。 搜索的⼏种常⻅⽅法：顺序查找、⼆分 法查找、⼆叉树查找、哈希查找
⼆分法查找
⼆分查找⼜称折半查找，优点是⽐较次数少，查找速度快，平均性能好；其 缺点是要求待查表为有序表，且插⼊删除困难。因此，折半查找⽅法适⽤于 不经常变动⽽查找频繁的有序列表。⾸先，假设表中元素是按升序排列，将 表中间位置记录的关键字与查找关键字⽐较，如果两者相等，则查找成功； 否则利⽤中间位置记录将表分成前、后两个⼦表，如果中间位置记录的关键 字⼤于查找关键字，则进⼀步查找前⼀⼦表，否则进⼀步查找后⼀⼦表。重 复以上过程，直到找到满⾜条件的记录，使查找成功，或直到⼦表不存在为 ⽌，此时查找不成功。
⼆分法查找实现
（⾮递归实现）
[AppleScript] 纯文本查看 复制代码 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 testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,] print(binary_search(testlist, 3)) print(binary_search(testlist, 13))
（递归实现）
[AppleScript] 纯文本查看 复制代码 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)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,] print(binary_search(testlist, 3)) print(binary_search(testlist, 13))
时间复杂度
最优时间复杂度：O(1) 最坏时间复杂度：O(logn)
|
|
收藏
淘帖
踩
