常用排序算法的python实现

比眉伴天荒 2021-12-10 15:02 356阅读 0赞

### 文章目录 ###

*  前言
 *  一、基本排序
 *   *  1.1 选择排序
     *  1.2 冒泡排序
     *  1.3 插入排序
 *  二、高级排序
 *   *  2.1 归并排序
     *  2.2 快速排序

# 前言 #

> 我的个人网站：https://www.gentlecp.com

排序算法想必都不陌生，从时间复杂度高的选择、冒泡、插入排序到较低的归并、快速、堆排序是数据结构与算法课程中经常讲的几种排序算法，本文采用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
    
    if __name__ == '__main__':
        items = [4, 3.6, 2, 8.5, 10.5]
        new_items = select_sort(items)
        new_reversed_items = select_sort(items, reverse=True)
        print(new_items)
        print(new_reversed_items)

## 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
    
    if __name__ == '__main__':
        items = [4, 3.6, 2, 8.5, 10.5]
        new_items = bubble_sort(items)
        new_reversed_items = bubble_sort(items, reverse=True)
        print(new_items)
        print(new_reversed_items)

## 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
    
    
    if __name__ == '__main__':
        items = [4, 3.6, 2, 8.5, 10.5]
        new_items = insert_sort(items)
        new_reversed_items = insert_sort(items, reverse=True)
        print(new_items)
        print(new_reversed_items)

# 二、高级排序 #

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

## 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
    
    if __name__ == '__main__':
        items = [4, 3.6, 2, 8.5, 10.5]
        new_items = merge_sort(items)
        new_reversed_items = merge_sort(items, reverse=True)
        print(new_items)
        print(new_reversed_items)

## 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)
    
    
    if __name__ == '__main__':
        items = [4, 3.6, 2, 8.5, 10.5]
        new_items = quick_sort(items)
        new_reversed_items = quick_sort(items, reverse = True)
        print(new_items)
        print(new_reversed_items)