排序算法的python实现

锦小年

发布于 2021-12-08 11:50:37

2890

发布于 2021-12-08 11:50:37

文章被收录于专栏：锦小年的博客锦小年的博客

本文用python实现常用的排序算法，按时间复杂度分为：

时间复杂度为O(n^2)：冒泡排序，选择排序，插入排序。
时间复杂度为O(nlogn)：快速排序，归并排序，堆排序。
时间复杂度为O(n)：计数排序，桶排序，基数排序

1. 时间复杂度为O(n^2)的排序算法

1.1 冒泡排序

基本思想：从左到右遍历数组，比较相邻两个数字的大小，如果前者比后者大，则交换他们的位置（从小到大排列）。一次遍历，使得最大值到最右端。重复n次遍历，则数据为从小到大排列。

def bubble_sort(sort_list=None):
    if not sort_list:
        return None
    list_len = len(sort_list)
    for i in range(list_len):
        for j in range(list_len-i-1):
            if sort_list[j] > sort_list[j+1]:
                sort_list[j],sort_list[j+1] = sort_list[j+1],sort_list[j]
    return sort_list

l_test = [3,1,4,7,8,5,9,0]
bubble_sort_rtn = bubble_sort(l_test)
print(bubble_sort_rtn)
# [0, 1, 3, 4, 5, 7, 8, 9]

1.2插入排序

基本思想：从列表中选择一个元素，与左边的元素进行比较，找到合适的位置插入，保持左边的元素有序。

def insert_sort(sort_list=None):
    if not sort_list:
        return None
    list_len = len(sort_list)
    for i in range(1, list_len):
        temp = sort_list[i]
        j = i-1
        while j >= 0:
            if temp < sort_list[j]:
                sort_list[j+1] = sort_list[j]
            else:
                break
            j -= 1
        sort_list[1+j] = temp
    return sort_list  
l_test = [3,1,4,7,8,5,9,0]
print(insert_sort(l_test)) #[0, 1, 3, 4, 5, 7, 8, 9]

1.3 选择排序

基本思想：遍历待排序的列表中选择出小的元素，并将它与第一个元素互换，然后从第二元素开始再选择最小的元素，与第二个元素互换，以此类推，直到列表有序。（从大到小排则选择最大的元素放在最前面）。

def select_sort(sort_list=None):
    if not sort_list:
        return None
    list_len = len(sort_list)
    for i in range(list_len):
        min_index = i
        for j in range(i,list_len):
            if sort_list[min_index] > sort_list[j]:
                min_index = j
        sort_list[i],sort_list[min_index] = sort_list[min_index],sort_list[i]
    return sort_list
l_test = [3,1,4,7,8,5,9,0]
print(select_sort(l_test)) # [0, 1, 3, 4, 5, 7, 8, 9]

2. 时间复杂度为O(nlogn)的排序算法

2.1 快速排序

在冒泡排序中，每轮循环只能确定一个元素的位置，所以，需要n轮循环才能确定所有元素的位置。而快速排序的思想是：选定一个基准元素，通过一次循环将数组分成两部分，左边比基准元素小，右边比基准元素大（或者相等）。这样一次循环确定了n个元素的相对位置。对左右边的数组迭代进行刚才的操作（分治的思想）。最后组合在一起，就成了有序数组。

def quick_sort(slist:list):

	# 判断边界返回条件
    if not isinstance(slist,list):
        return 
    if len(slist) <= 1:
        return slist
    # 以最中间元素为基准元素
    mid = int(len(slist)/2)
    mid_val = slist[mid]
    slist.pop(mid)
    # 得到基准元素左边的元素
    list_left = [v for v in slist if v < mid_val]
    # 得到基准元素右边的元素
    list_right = [v for v in slist if v >= mid_val]
    # 递归完成并合并
    return quick_sort(list_left) + [mid_val] + quick_sort(list_right)

# test
import random
slist = []
for i in range(50):
    slist.append(random.randint(0,2355))
print(slist)
rlist = quick_sort(slist)
print(rlist)

# 该示例只是为了演示快速排序，不是最优写法，比如： 没有考虑与基准元素相等的元素的位置，运行性能

利用双边循环：

def quick_sort(slist:list)->list:
    if not isinstance(slist,list):
        return
    if len(slist) <= 1:
        return slist
    if len(slist) == 2:
        if slist[0] > slist[1]:
            slist[0],slist[1] = slist[1], slist[0]
        return slist
    slist = slist.copy()
    # 以最中间的元素为基准元素
    mid = int(len(slist)/2)
    mid_val = slist[mid]
    slist.pop(mid)
    # 双边循环
    left, right = 0,len(slist)-1
    while left < right:
        while (left < right and slist[right] > mid_val):
            right -= 1
        while left <= right and slist[left] <= mid_val:
            left += 1
        if left < right:
            slist[left],slist[right] = slist[right],slist[left]
    return quick_sort(slist[:left]) +[mid_val] + quick_sort(slist[left:])
# test
import random
for index in range(100):
    slist = []
    for i in range(100):
        slist.append(random.randint(0,2355))
    rlist = quick_sort(slist)
    slist.sort()
    assert rlist == slist, "not equient"

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021-06-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度