O(NLogN)

作者: Rokkia | 来源:发表于2018-03-07 14:23 被阅读69次

    NLogN来源 使用二分法得到LogN,二分完成后对每一层级都只是执行O(N)的操作,于是NLogN

    1. 归并
      归并排序很有意思,归并的过程是一个先拆再合的过程。
      第一步将元素拆分为最小单位(这个过程是一个递归的过程)
      第二步将最小单位排序后合并
      如果下图
    图片来自网络-维基百科.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的使用是精髓。

    1. 快速
      快速排序:
      听说是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
    

    好文: 挖掘算法中的数据结构(三):O(n*logn)排序算法之 快速排序(随机化、二路、三路排序) 及衍生算法

    相关文章

      网友评论

          本文标题:O(NLogN)

          本文链接:https://www.haomeiwen.com/subject/gajexftx.html