归并排序
-
思想
简单地将原始序列划分成两个子序列，分别对每个子序列递归排序，最后将排好序的子序列合并为一个有序序列
先拆成一个一个的，然后两个合并一起，并排好序
两个两个的合并成四个的时候，需要左边一个指针left指向左边第一个元素，右边一个指针right指向右边第一个元素，两个元素比较，谁小放到左边，然后挪一下指针
-
性质
稳定
时间复杂度：
O（nlogn）
（最优、最坏一样）
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: Caramel
@file: 6.1_merge_sort.py
@time: 2020/02/12
@desc:归并排序
"""
def merge_sort(alist):
n = len(alist)
if n <= 1:
return alist
mid = n // 2
'''采用归并排序后形成的新的列表'''
left_li = merge_sort(alist[:mid])
right_li = merge_sort(alist[mid:])
'''将两个有序的子序列合并成一个整体'''
left_index = 0
right_index = 0
result = []
while left_index < len(left_li) and right_index < len(right_li):
if left_li[left_index] <= right_li[right_index]:
'''等号保证稳定性'''
result.append(left_li[left_index])
left_index += 1
else:
result.append(right_li[right_index])
right_index += 1
result += left_li[left_index:]
result += right_li[right_index:]
return result
if __name__ == '__main__':
il = [15, 15, 65, 16, 86, 10, 63]
print(il)
sorted = merge_sort(il)
print(sorted)
-
执行过程
先是对左边的进行递归，分裂直到剩最后一个元素54，然后执行两个元素[54, 26]的右边递归，得到第一个两个的右边元素26
他们两个执行合并操作，变成[26, 54]。以此类推。
- 执行结束后不是在原有的列表上进行改动，而是在重新生成一个等大的有序列表。虽然时间复杂度降低，但是代价是空间。
排序比较
搜索
-
二分法查找
前提：
数据已是有序的
操作对象支持下标索引
即是有序顺序表
先预处理数据，顺序由小到大排列。取中值，关键码与其比较，若果大于就在大的那一部分找，同理。
计算下标时，用第一个和最后一个的下标计算
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: Caramel
@file: 6.2_binary_search.py
@time: 2020/02/12
@desc:二分查找
"""
def binary_search(alist, item):
'''递归'''
n = len(alist)
if n >= 2:
mid = n//2
if alist[mid] == item:
return True
elif item < alist[mid]:
return binary_search(alist[:mid], item)
else:
return binary_search(alist[mid:], item)
return False
def binary_search_2(alist, item):
'''非递归'''
n = len(alist)
fir = 0
last = n - 1
while fir <= last:
mid = (last + fir) // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
last = mid - 1
else:
fir = mid + 1
return False
if __name__ == '__main__':
li = [10, 15, 15, 16, 63, 65, 86]
print(binary_search(li, 65))
print(binary_search(li, 98))
print(binary_search_2(li, 65))
print(binary_search_2(li, 98))
ASL：
log2（n+1）-1
成功检索：
log2（n+1）向上取整
失败检索：
log2（n+1）向上或者向下取整
时间复杂度：
最坏：
O（logn）
最好：
O（1）