O(NLogN)
2018-03-07 本文已影响69人
Rokkia
NLogN来源 使用二分法得到LogN，二分完成后对每一层级都只是执行O(N)的操作，于是NLogN
- 归并
归并排序很有意思，归并的过程是一个先拆再合的过程。
第一步将元素拆分为最小单位(这个过程是一个递归的过程)
第二步将最小单位排序后合并
如果下图
图片来自网络-维基百科.gif
区别: 不能直接操作数组交换
缺点: 需要使用一部分额外的空间来备份元素
醒神:
def merge_sort(arr):
#这里的15可以替换为1试一下
if len(arr) <= 15:
#当<= 的值 > 1时， 需要使用插入排序来节省时间
insert_sort_better(arr)
return arr
middle = int(len(arr) // 2)
left = merge_sort(arr[:middle])
right = merge_sort(arr[middle:])
return __merge(left, right)
#left right is list object
def __merge(left, right):
merged, left, right = deque(), deque(left), deque(right)
#利用queue的特性来控制元素为空的情况，不怕left or right is empty
while left and right:
#使用queue来控制元素的index
#避免了越界问题
merged.append(left.popleft() if left[0] < right[0] else right.popleft())
merged.extend(right if right else left)
return list(merged)
代码来自维基百科，但是做了部分调整，deque的使用是精髓。
- 快速
快速排序:
听说是20世纪很牛的一个算法，那么我们先来夸夸吧
有点:
1.速度快 o(nlogn)的速度
2.并不需要额外的空间
缺点:
不稳定，有各种情况会让其突然的变慢，如：
2.1 重复数个数太多情况
2.2 基本有序情况
图片来自网络维基百科.gif
这个算法首先会需要比较多的index标记
low 记录最低点
high 记录最高点
j 标记分割点
i 标记当前位置
上代码
def _partition(arr, low, high):
temp = arr[low]
j = low
for i in range(low, high):
if arr[i] < temp:
#这里需要使用arr[j+1] 因为j开始点为low
arr[i], arr[j + 1] = arr[j + 1], arr[i]
j += 1
arr[j], arr[low] = arr[low], arr[j]
return j
def QuickSort(arr, low, high):
if low >= high:
return
#通过_partition 返回分割点
p = _partition(arr, low, high)
QuickSort(arr, low, p)
QuickSort(arr, p + 1, high)
问题1:
当数组基本有序的情况下，快速排序的速度会由nlogn降低到n^2级别
原因:
因为每次取值，我们都是去的arr[low]这个位置
解决:
temp 我们取值为arr[low] --> arr[high] 中的任意值
修改代码
def _partition(arr, low, high):
#添加部分
index = random.randint(low, high - 1)
arr[low], arr[index] = arr[index], arr[low]
#其他位置不变
temp = arr[low]
j = low
for i in range(low, high):
if arr[i] < temp:
#这里需要使用arr[j+1] 因为j开始点为low
arr[i], arr[j + 1] = arr[j + 1], arr[i]
j += 1
arr[j], arr[low] = arr[low], arr[j]
return j
问题2:
数组中重复数字过多的时候，速度也会退化
原因:
多次重复也会导致一端特别长，一端特别短，也会退化几乎于n2的速度
解决:
使用二路快速排序 or 三路快速排序
二路排序:
这张图很好的展示了二路排序的过程，i,j 标记着 < v ,> v的两个点，代码十分精彩，连续使用两个while操作十分精彩。
图片来自网络，侵删.gif
代码
def QuickSortRepeat(arr, low, high):
if low >= high:
return
# if high - low <= 15:
# insert_sort_better_lr(arr, low, high)
# return
#通过_partition 返回分割点
p = _partitionrepeat(arr, low, high)
QuickSortRepeat(arr, low, p - 1)
QuickSortRepeat(arr, p + 1, high)
def _partitionrepeat(arr, low, high):
i = low + 1
j = high
temp = arr[low]
while True:
#这里我认为是代码的核心
while i <= high and arr[i] < temp:
i += 1
#很精彩的两个while循环
while j >= low + 1 and arr[j] > temp:
j -= 1
if i > j:
break
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
arr[low], arr[j] = arr[j], arr[low]
return j
然后就是三路排序了
三路是将partition分成了三部分， < > =
注:图片前部分并不三路排序
图片来自网络，侵删.gif
代码:
def QuickSortThree(arr, low, high):
if low >= high:
return
lt, gt = _partitionthree(arr, low, high)
QuickSortThree(arr, low, lt-1)
QuickSortThree(arr, gt, high)
def _partitionthree(arr, low, high):
lt = low
gt = high
i = low + 1
v = arr[low]
while i < gt:
if arr[i] > v:
arr[gt], arr[i] = arr[i], arr[gt]
gt -= 1
elif arr[i] < v:
arr[lt + 1], arr[i] = arr[i], arr[lt + 1]
lt += 1
i += 1
else:
i += 1
arr[lt], arr[low] = arr[low], arr[lt]
return lt, gt
