python基本的排序算法比较_python实现经典排序算法
发布日期:2021-10-27 12:03:57 浏览次数:1 分类:技术文章

本文共 4322 字,大约阅读时间需要 14 分钟。

以下排序算法最终结果都默认为升序排列,实现简单,没有考虑特殊情况,实现仅表达了算法的基本思想。

冒泡排序

内层循环中相邻的元素被依次比较,内层循环第一次结束后会将最大的元素移到序列最右边,第二次结束后会将次大的元素移到最大元素的左边,每次内层循环结束都会将一个元素排好序。

def bubble_sort(arr):

length = len(arr)

for i in range(length):

for j in range(length - i - 1):

if arr[j] > arr[j + 1]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

return arr

选择排序

每次内层循环都会得到一个当前最小的元素,并将其放到合适的位置。内层循环第一次结束后会将最小的元素交换到序列首位,第二次结束后会将第二小的元素交换到序列第二位,每次内层循环结束后都会将一个元素放在正确的顺序位置。

def selection_sort(arr):

length = len(arr)

for i in range(length):

min_index = i

for j in range(i + 1, length):

if arr[j] < arr[min_index]:

min_index = j

arr[i], arr[min_index] = arr[min_index], arr[i]

return arr

插入排序

类比玩扑克牌时理牌的思想,从第一个元素开始,假设它是已经排好序的。然后开始处理第二个元素,如果比第一个元素小,则将其放到第一个元素左边,否则放在其右边,那么现在前两个元素以及排好序了,之后再依次处理剩余的元素。

def insertion_sort(arr):

length = len(arr)

for i in range(1, length):

pre = i - 1

current_value = arr[i]

while pre >= 0 and arr[pre] > current_value:

arr[pre + 1] = arr[pre]

pre -= 1

arr[pre+1] = current_value

return arr

希尔排序

希尔排序就是将插入排序的改进版本。插入排序中每次逐步比较元素,而希尔排序中则是从一个较大的步数开始比较,最后减小到一步。

def shell_sort(arr):

length = len(arr)

gap = length // 2

while gap > 0:

for i in range(gap, length):

pre = i - gap

current_value = arr[i]

while pre >= 0 and arr[pre] > current_value:

arr[pre + gap] = arr[pre]

pre -= gap

arr[pre + gap] = current_value

gap = gap // 2

return arr

归并排序

先将序列前半部分排好序,再将序列后半部分排好序,之后再将这两部分合并得到最终的序列,具体实现为递归地将序列分为两部分,分别排序后再合并。

def merge(left, right):

result = []

while len(left) > 0 and len(right) > 0:

if left[0] < right[0]:

result.append(left.pop(0))

else:

result.append(right.pop(0))

if len(left) > 0:

result.extend(left[:])

if len(right) > 0:

result.extend(right[:])

return result

def merge_sort(arr):

if len(arr) < 2:

return arr

middle = len(arr) // 2

return merge(merge_sort(arr[:middle]), merge_sort(arr[middle:]))

快速排序

取一个元素,将比它小的元素都移到它左侧,将比它大的元素都移到它右侧,并递归地处理它左侧的序列和右侧的序列。

def partition(arr, left=None, right=None):

pivot = left

index = pivot + 1

for i in range(index, right + 1):

if arr[i] < arr[pivot]:

arr[i], arr[index] = arr[index], arr[i]

index += 1

arr[pivot], arr[index - 1] = arr[index - 1], arr[pivot]

return index - 1

def quick_sort(arr, left=None, right=None):

left = 0 if left is None else left

right = len(arr) - 1 if right is None else right

if left < right:

partition_index = partition(arr, left, right)

quick_sort(arr, left, partition_index - 1)

quick_sort(arr, partition_index + 1, right)

return arr

堆排序

首先构建一个最大堆,最大堆的性质是父节点的值总是大于其左右子节点的值,那么此时根节点的值是最大的,则将其移到序列的最右边。之后将堆中当前最后一个叶节点移到根节点上,因为这可能会不符合最大堆的性质,所以会进行调整,将它与其左右子节点中最大的值进行交换,则相当于将叶节点向下移动,交换过后如果还是不符合性质,则继续进行交换,直到符合性质后,此时的根节点的值就是当前堆中的最大值,将其取出放入序列中正确的位置后继续上述流程处理剩下的节点。

global length2

def heapify(arr, i):

left = 2 * i + 1

right = 2 * i + 2

largest = i

if left < length2 and arr[left] > arr[largest]:

largest = left

if right < length2 and arr[right] > arr[largest]:

largest = right

if largest != i:

arr[i], arr[largest] = arr[largest], arr[i]

heapify(arr, largest)

def build_max_heap(arr):

for i in range(len(arr) // 2, -1, -1):

heapify(arr, i)

def heap_sort(arr):

global length2

length2 = len(arr)

build_max_heap(arr)

for i in range(len(arr) - 1, 0, -1):

arr[0], arr[i] = arr[i], arr[0]

length2 -= 1

heapify(arr, 0)

return arr

计数排序

将序列中的元素按照其值放入相应的桶中,之后再按照桶的顺序取出即可,计数排序不需要比较操作。

def counting_sort(arr):

max_value = max(arr)

buckets = [0] * (max_value + 1)

index = 0

length = len(arr)

for i in range(length):

buckets[arr[i]] += 1

for j in range(max_value + 1):

while buckets[j] > 0:

arr[index] = j

index += 1

buckets[j] -= 1

return arr

桶排序

类别计数排序,构造很多桶,但每个桶中能放入值在特定范围内的元素,将序列中的元素按照要求放入各个桶中,再将每个桶中的元素进行排序,最后按照桶的顺序和各个桶中元素的顺序得到最终序列。

def bucket_sort(arr):

bucket_size = 5

max_value = max(arr)

min_value = min(arr)

bucket_num = (max_value - min_value) // bucket_size + 1

buckets = {i: [] for i in range(bucket_num)}

for i in range(len(arr)):

buckets[(arr[i] - min_value) // bucket_size].append(arr[i])

result = []

for i in range(bucket_num):

insertion_sort(buckets[i])

result.extend(buckets[i])

return result

基数排序

按照元素值的特定位进行排序,从低位到高位分别进行排序。

def radix_sort(arr):

max_value = max(arr)

max_digit = len(str(max_value))

dev = 1

mod = 10

result = arr[:]

for i in range(max_digit):

buckets = {i: [] for i in range(mod)}

for k in range(len(result)):

key = (result[k] % mod) // dev

buckets[key].append(result[k])

result = []

for j in range(mod):

result.extend(buckets[j])

dev *= 10

mod *= 10

return result

转载地址:https://blog.csdn.net/weixin_34620658/article/details/114423040 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:java中init()_详解java代码中init method和destroy method的三种使用方式
下一篇:python中write刷新_Python中的sys.stdout.write实现打印刷新功能

发表评论

最新留言

很好
[***.229.124.182]2024年03月20日 11时11分19秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

c语言case中途跳出,break语句在switch结构语句中的作用是终止某个case,并跳出switch结构语句。... 2019-04-21
C语言编写程序计算高考倒计时天数,基于51单片机LCD12864大字符校时万年历带高考倒计时程序... 2019-04-21
普职融通信息技术课本C语言,“三步走”扎实推进“普职融通”办学新模式 2019-04-21
Android多个签名,【Android】Android批量重签名 2019-04-21
html unicode编码转换,JS实现的Unicode编码转换操作示例 2019-04-21
html页面角落放动漫人物,L2Dwidget.js L2D网页动画人物添加 2019-04-21
html图片水平居中,CSS制作图片水平垂直居中 2019-04-21
php写模糊搜索api接口,php通过sphinxapi接口实现全文搜索 2019-04-21
oracle安装出现2932,【案例】Oracle报错ORA-19815 fast_recovery_area无剩余空间解决办法... 2019-04-21
form表单属性名相同java_form表单提交时候有多个相同name 的input如何处理? 2019-04-21
java图片加气泡文字_图片加气泡文字 2019-04-21
java总结i o流_14.java总结I/O流 2019-04-21
java和历转为西历_日期转西暦,和暦 2019-04-21
java 远程 yarn jar_再论Yarn Client和Yarn cluster 2019-04-21
java单元测试断言_单元测试+断言 2019-04-21
java 创建压缩包_用Java创建ZIP压缩文件 2019-04-21
java typedarray_TintTypedArray.java 2019-04-21
java字符字面量_java – 字符串字面量的行为是令人困惑的 2019-04-21
php判断数组的值是否为空,PHP判断数组是否为空的常用方法(五种方法) 2019-04-21
php 读数据库,PHP数据库 2019-04-21