Python实现的几个常用排序算法实例
作者:junjie 时间:2021-08-13 07:42:54
前段时间为准备百度面试恶补的东西,虽然最后还是被刷了,还是把那几天的“战利品”放点上来,算法一直是自己比较薄弱的地方,以后还要更加努力啊。
下面用Python实现了几个常用的排序,如快速排序,选择排序,以及二路并归排序等等。
#encoding=utf-8
import random
from copy import copy
def directInsertSort(seq):
""" 直接插入排序 """
size = len(seq)
for i in range(1,size):
tmp, j = seq[i], i
while j > 0 and tmp < seq[j-1]:
seq[j], j = seq[j-1], j-1
seq[j] = tmp
return seq
def directSelectSort(seq):
""" 直接选择排序 """
size = len(seq)
for i in range(0,size - 1):
k = i;j = i+1
while j < size:
if seq[j] < seq[k]:
k = j
j += 1
seq[i],seq[k] = seq[k],seq[i]
return seq
def bubbleSort(seq):
"""冒泡排序"""
size = len(seq)
for i in range(1,size):
for j in range(0,size-i):
if seq[j+1] < seq[j]:
seq[j+1],seq[j] = seq[j],seq[j+1]
return seq
def _divide(seq, low, high):
"""快速排序划分函数"""
tmp = seq[low]
while low != high:
while low < high and seq[high] >= tmp: high -= 1
if low < high:
seq[low] = seq[high]
low += 1
while low < high and seq[low] <= tmp: low += 1
if low < high:
seq[high] = seq[low]
high -= 1
seq[low] = tmp
return low
def _quickSort(seq, low, high):
"""快速排序辅助函数"""
if low >= high: return
mid = _divide(seq, low, high)
_quickSort(seq, low, mid - 1)
_quickSort(seq, mid + 1, high)
def quickSort(seq):
"""快速排序包裹函数"""
size = len(seq)
_quickSort(seq, 0, size - 1)
return seq
def merge(seq, left, mid, right):
tmp = []
i, j = left, mid
while i < mid and j <= right:
if seq[i] < seq[j]:
tmp.append(seq[i])
i += 1
else:
tmp.append(seq[j])
j += 1
if i < mid: tmp.extend(seq[i:])
if j <= right: tmp.extend(seq[j:])
seq[left:right+1] = tmp[0:right-left+1]
def _mergeSort(seq, left, right):
if left == right:
return
else:
mid = (left + right) / 2
_mergeSort(seq, left, mid)
_mergeSort(seq, mid + 1, right)
merge(seq, left, mid+1, right)
#二路并归排序
def mergeSort(seq):
size = len(seq)
_mergeSort(seq, 0, size - 1)
return seq
if __name__ == '__main__':
s = [random.randint(0,100) for i in range(0,20)]
print s
print "\n"
print directSelectSort(copy(s))
print directInsertSort(copy(s))
print bubbleSort(copy(s))
print quickSort(copy(s))
print mergeSort(copy(s))
运行结果如下:
E:\python_project\practice>sorting.py
[10, 47, 56, 76, 64, 84, 26, 8, 47, 51, 88, 81, 32, 95, 91, 29, 28, 69, 61, 45]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
[8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
简化ADO数据库操作的控件(带分页功能)
form的submit方法和submit事件(onsubmit)
PHP面向对象程序设计继承用法简单示例
PJBlog3优化——301定向跳转解决重复内容的问题
使用Python处理KNN分类算法的实现代码
![](https://img.aspxhome.com/file/2023/4/63244_0s.png)
Python smtplib实现发送邮件功能
Python爬虫爬取博客实现可视化过程解析
![](https://img.aspxhome.com/file/2023/6/85186_0s.png)
Go语言使用Gob传输数据
Python3使用requests发闪存的方法
用1行Python代码识别身份证信息实例
![](https://img.aspxhome.com/file/2023/8/87898_0s.jpg)
Python实现的爬虫刷回复功能示例
![](https://img.aspxhome.com/file/2023/3/87943_0s.jpg)
Python多线程编程之多线程加锁操作示例
关于IDEA git 只有Commit没有Push的问题
![](https://img.aspxhome.com/file/2023/7/63437_0s.png)
ASP中正则表达式的应用
Div+CSS网页布局对SEO的影响漫谈
Oracle批量查询、删除、更新使用BULK COLLECT提高效率
解读ASP.NET 5 & MVC6系列教程(6):Middleware详解
基于Python pyecharts实现多种图例代码解析
![](https://img.aspxhome.com/file/2023/9/75939_0s.png)
使用Python脚本将绝对url替换为相对url的教程
Linux下安装Memcached服务器和客户端与PHP使用示例
![](https://img.aspxhome.com/file/2023/8/85818_0s.png)