Python八大排序实现方法

前言

大家早好、午好、晚好吖 ❤ ~欢迎光临本文章

如果有什么疑惑/资料需要的可以点击文章末尾名片

1.基数排序

基数排序的基本思想是先将数字按照个位数上数字的大小进行排序，

排序之后再将已经排过序的数字再按照十位数上数字的大小进行排序，依次推类

# 统计这个列表中数字最大的数字有几位
def radix_sort_nums(nums):max = nums[0]for i in nums:if max < i:max = itimes = 0while max > 0:max = int(max/10)times += 1return times# 每个数字各个位置的数字大小，比如（123,1）则是3，（123,2）则是2
def get_num(num,n):return (int(num/(10**(n-1)))) % 10# 主程序
def radix_sort(nums):count = 10*[None]	# 定义的数组，用于存放当前位数的元素个数bucket = len(nums)*[None]	# 用于暂时存放排序结果# 分别从个位/十位/百位开始循环for pos in range(1, radix_sort_nums(nums)+1):# 每次排序完都要清空各个位数存放的数据统计for i in range(10):count[i] = 0for i in range(len(nums)):# 获得0到9每个位数的个数j = get_num(nums[i], pos)count[j] = count[j]+1# 获得相对应位数的边界值for i in range(1, 10):count[i] = count[i] + count[i-1]for i in range(len(nums)-1, -1, -1):# 求出相应位数的数字j = get_num(nums[i], pos)#将元素按相应位数的上数字的大小排序bucket[count[j]-1] = nums[i]#让相应位数上数字相等的元素不会放在同一位置而被替代count[j] = count[j]-1# 将暂时存储在bucket的元素数据返回到nums中for i in range(0, len(nums)):nums[i] = bucket[i]return numsprint(radix_sort([45, 32, 8, 33, 12, 22, 19, 97]))

2.归并排序

归并排序其实是将原数列分为很多个小数列将其排序，在小数列排序完之后，

再将各个小数列进行排序，最后得到一个全部有序的数列

# 归并排序
'''
学习中遇到问题没人解答？小编创建了一个Python学习交流QQ群：702813599
寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！
'''
# 这个函数主要目的是为了实现合并并排序
def mergearray(nums, first, mid, last, temp):# i, j分别是第一个组数的第一个位置，第二组数的第一个位置i, j, k = first, mid+1, 0# 当俩边数组都存在数的时候，依次比较对应位置的大小while i <= mid and j <= last:if nums[i] <= nums[j]:temp[k] = nums[i]i = i+1k = k+1else:temp[k] = nums[j]j = j+1k = k+1# 第一组数还有多的数的情况while i <= mid:temp[k] = nums[i]i = i+1k = k+1# 第二组数还有多的情况while (j <= last):temp[k] = nums[j]j = j+1k = k+1# 将排列过的数组赋予nums（开始的时候只是部分有序，随着递归最后变成全部有序）for i in range(k):nums[first+i] = temp[i]# 分组，利用递归
def merge_sort(nums,first,last,temp):if first < last:mid = int((first + last) / 2)# 分出第一组数merge_sort(nums, first, mid, temp)# 分出第二组数merge_sort(nums, mid+1, last, temp)# 合并并排序mergearray(nums, first, mid, last, temp)def merge_sort_array(nums):# 创建一个和想要排序数列相同数量的空列表temp = len(nums)*[None]# 利用递归进行排序merge_sort(nums, 0, len(nums)-1, temp)print(merge_sort_array([45, 32, 8, 33, 12, 22, 19, 97]))

3.堆排序

堆排序利用了二叉树的结构，使子节点的值一直小于根节点

def big_endian(arr, start, end):root = startchild = root * 2 + 1  # 左孩子while child <= end:# 孩子比最后一个节点还大，也就意味着最后一个叶子节点了，就得跳出去一次循环，已经调整完毕if child + 1 <= end and arr[child] < arr[child + 1]:# 为了始终让其跟子元素的较大值比较，如果右边大就左换右，左边大的话就默认child += 1if arr[root] < arr[child]:# 父节点小于子节点直接交换位置，同时坐标也得换，这样下次循环可以准确判断：是否为最底层，# 是不是调整完毕arr[root], arr[child] = arr[child], arr[root]root = childchild = root * 2 + 1else:break'''
学习中遇到问题没人解答？小编创建了一个Python学习交流QQ群：702813599
寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！
'''
def heap_sort(nums):  # 无序区大根堆排序first = len(nums) // 2 - 1for start in range(first, -1, -1):# 从下到上，从左到右对每个节点进行调整，循环得到非叶子节点big_endian(nums, start, len(nums) - 1)  # 去调整所有的节点for end in range(len(nums) - 1, 0, -1):nums[0], nums[end] = nums[end], nums[0]  # 顶部尾部互换位置big_endian(nums, 0, end - 1)  # 重新调整子节点的顺序，从顶开始调整return numsprint(heap_sort([3, 1, 4, 9, 6, 7, 5, 8, 2, 10]))

4.简单选择排序

简单选择排序的方法则是将所选值与剩下值中比他小的值进行比较

比如选取第一个值，往后找到比他小的值就与其对调，对调后的值再接下去进行比较，直至找到最小的值，随后再第二个值……直至循环到倒数第二个值.

def select_sort(nums):# 遍历所有的值for i in range(len(nums)):# 当前位置初始值min = nums[i]# 与比他后面的值进行比较，小则互换for j in range(i+1, len(nums)):if nums[j] < min:nums[j], min = min, nums[j]# 将值返回数列nums[i] = minreturn numsprint(select_sort([45, 32, 8, 33, 12, 22, 19, 97]))

5.直接插入排序

首先遍历所有元素，随后从第一个数开始将数列从后往前遍历，

如果后面的数小于前面的数，则互换位置，依次推类，直到遍历完成

# 直接插入排序
def insert_sort(nums):for i in range(len(nums)-1):for j in range(i, -1, -1):if nums[j] > nums[j+1]:nums[j], nums[j + 1] = nums[j + 1], nums[j]return numsprint(insert_sort([45, 32, 8, 33, 12, 22, 19, 97]))

6.希尔排序

希尔排序其实就相当于对直接插入排序的升级版，每次都选取一半的长度，

随后利用直接插入法进行排序，从而更快的获得结果

def insert_shell(nums):# 初始化l值，此处利用序列长度的一半为其赋值l = int(len(nums)/2)# 第一层循环：依次改变l值对列表进行分组while l >= 1:# 下面：利用直接插入排序的思想对分组数据进行排序for i in range(len(nums) - 1):for j in range(i, -1, -1):if nums[j] > nums[j + 1]:nums[j], nums[j + 1] = nums[j + 1], nums[j]# while循环条件折半l = int(l/2)return nums

7.快速排序

快速排序首先得选取一个基准值，这个代码用第一个数作为基准值，

将比基准值小的值放到左边，比基准值大的值放到右边，

随后再将左边后右边按照上述方法进行排序，直到完全正确为止

# 实现快速排序方法的函数
def quick_sort_num(nums,start,end):if start < end:# 定义基准值为第一个数i, j, pivot = start, end, nums[start]while i < j:# 将基准数右边的数中比基准数小的放到左边while i < j and nums[j] >= pivot:j = j-1if i < j:nums[i] = nums[j]i = i+1# 将基准数左边的数中比基准数大的数放到右边while i < j and nums[i] < pivot:i = i+1if i < j:nums[j] = nums[i]j = j-1nums[i] = pivot# 分别将基准数左边的数列和右边的数列进行递归quick_sort_num(nums, start, i-1)quick_sort_num(nums, i+1, end)return nums
'''
学习中遇到问题没人解答？小编创建了一个Python学习交流QQ群：702813599
寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！
'''
# 快速排序主体函数
def quick_sort(nums):start = 0end = len(nums)-1nums = quick_sort_num(nums, start, end)return numsprint(quick_sort([45, 32, 8, 33, 12, 22, 19, 97]))

8.冒泡排序

冒泡排序是最简单的排序，依次将左右俩个元素进行比较，

每次比较完最后的一个数必定是最大的，依次推类，直到全部元素都比较玩

def bubble_sort(nums):# 交换的轮数for i in range(len(nums) - 1):# 每一轮交换for j in range(len(nums) - i - 1):# 比较值，并根据大小进行互换if nums[j] > nums[j + 1]:nums[j], nums[j + 1] = nums[j + 1], nums[j]return numsprint(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))

9.时间测试

我们先创建一个列表，列表中有10000条数据，随后用相同的数据进行测试

import random
lis = []
for i in range(10000):i = random.randint(0,500)lis.append(i)print(lis)

创出来的数据就不进行展示了。。

随后我们进行测试：

冒泡排序法：11.535502672195435直接插入排序法：12.057243585586548希尔排序法：86.3020749092102（大概是我的方法不大好吧，我差点以为他排不出来了）基数排序法：0.051932334899902344（老大哥就是牛皮）归并排序法：0.08577108383178711（233）快速排序：0.04795527458190918堆排序：0.09175491333007812

根据自己的测试，基数排序，归并排序，快速排序，和堆排序速度很快，

感觉随着代码量的增长时间增长很慢，其余的几个则不尽如人意了