黑马程序员技术交流社区

标题: 【郑州校区】 python数据结构与算法（17） [打印本页]

---

作者: 谷粒姐姐    时间: 2018-12-4 15:14
标题: 【郑州校区】 python数据结构与算法（17）
归并排序
归并排序是采⽤分治法的⼀个⾮常典型的应⽤。归并排序的思想就是先递归 分解数组，再合并数组。
将数组分解最⼩之后，然后合并两个有序数组，基本思路是⽐较两个数组的 最前⾯的数，谁⼩就先取谁，取了后相应的指针就往后移⼀位。然后再⽐ 较，直⾄⼀个数组为空，最后把另⼀个数组的剩余部分复制过来即可。
归并排序的分析
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)

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2