常用排序算法的python实现

热门标签

GentleCP

发表文章数:52

首页 » 技术杂谈 » Python » 正文
摘要:排序算法相比都不陌生,从时间复杂度高的选择、冒泡、插入排序到较低的归并、快速、堆排序是数据结构与算法...

一、基本排序

1.1 选择排序

  • 原理
    从未排序的元素中选择最小(最大)值放到已排序的元素后面。
  • 实现
    def select_sort(items = [],
                reverse = False):
        '''
        获取一个存储value的列表,经选择排序后返回新的列表
        默认由小到大排序,reverse为True时由大到小排序
        '''
        # 避免影响原始列表
        items_copy = items.copy()
        # 避免重复计算
        length = len(items_copy)
        for i in range(length-1):
            min_index = i
            for j in range(i+1, length):
                if items_copy[j] < items_copy[min_index]:
                    min_index = j
            items_copy[i], items_copy[min_index] = items_copy[min_index], items_copy[i]
        if reverse:
            return list(reversed(items_copy))
        return items_copy

1.2 冒泡排序

  • 原理
    比较相邻元素,较小(较大)者往前移动
  • 实现
    def bubble_sort(items = [],
               reverse = False):
        '''
        获取一个存储value的列表,经冒泡排序后返回新的列表
        默认由小到大排序,reverse为True时由大到小排序
        '''
        # 避免影响原始列表
        items_copy = items.copy()
        # 避免重复计算
        length = len(items_copy)
        for i in range(length-1):
            for j in range(length-1-i):
                if items_copy[j] > items_copy[j+1]:
                    items_copy[j], items_copy[j+1] = items_copy[j+1], items_copy[j]
        if reverse:
            return list(reversed(items_copy))
        return items_copy

1.3 插入排序

  • 原理
    以第一个元素为插入基准,后续元素不断往前插入,若较小(较大),则排在基准元素前列。可参考摸扑克牌时整理手牌的过程。
  • 实现
    def insert_sort(items = [],
               reverse = False):
        '''
        获取一个存储value的列表,经插入排序后返回新的列表
        默认由小到大排序,reverse为True时由大到小排序
        '''
        # 避免影响原始列表
        items_copy = items.copy()
        # 避免重复计算
        length = len(items_copy)
        for i in range(1,length):
            temp = items_copy[i]
            # 待插入下标
            insert_index = i
            for j in range(i-1,-1,-1):
                # 与已插入数据比较,从后向前
                if items_copy[j] > temp:
                    # 大的数后移空出位置
                    items_copy[j+1] = items_copy[j]
                    insert_index = j
                else:
                    break
            items_copy[insert_index] = temp
        if reverse:
            return list(reversed(items_copy))
        return items_copy

二、高级排序

高级排序主要是复杂度较低的常见排序

2.1 归并排序

  • 原理
    归并排序主要有两个步骤分治与合并,分治即将长列表不断均分为短列表,对每个短列表进行排序,合并即将这些分别排序后的列表合并成排序后的长列表。
  • 实现

    def merge_sort(items = [],
              reverse = False):
        '''
        拆分列表进行归并
        '''
        length = len(items)
        if length < 2:
            return items[:]
        mid = length // 2
        left_part = merge_sort(items[:mid])
        right_part = merge_sort(items[mid:])
        if reverse:
            return list(reversed(merge(left_part,right_part)))
        return merge(left_part,right_part)
    def merge(left_part, right_part):
        '''
        将两个列表合并成一个
        '''
        result_list = []
        while left_part and right_part:
            if left_part[0] <= right_part[0]:
                result_list.append(left_part.pop(0))
            else:
                result_list.append(right_part.pop(0))
        # 将剩余数据添加到结果中
        result_list.extend(left_part)
        result_list.extend(right_part)
        return result_list

2.2 快速排序

  • 原理
    快排基于一个中值和两个指针,选定中值后将大于该中值的移到右边,小于该中值的移到左边。
  • 实现
    def quick_sort(items,
              reverse = False):
        '''
        快速排序
        '''
        length = len(items)
        if length <= 1:
            return items
        else:
            mid_item = items[0]
            right_items = [item for item in items[1:] if item > mid_item]
            left_items = [item for item in items[1:] if item <= mid_item]
            if reverse:
                return list(reversed(quick_sort(left_items) + [mid_item] + quick_sort(right_items)))
            return quick_sort(left_items) + [mid_item] + quick_sort(right_items)
标签:

未经本人允许不得转载!作者:GentleCP, 转载或复制请以 超链接形式 并注明出处 求索
原文地址:《常用排序算法的python实现》 发布于2019-07-11

分享到:
赞(1)

评论 抢沙发

评论前必须登录!

  注册



Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
切换注册

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录
切换登录

注册