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]
猜你喜欢
- 本文将介绍 5 种基于 Plotly 的可视化方法,你会发现,原来可视化不仅可用直方图和箱形图,还能做得如此动态好看甚至可交互。那么,Plo
- 本文实例为大家分享了TensorFlow实现卷积神经网络的具体代码,供大家参考,具体内容如下代码(源代码都有详细的注释)和数据集可以在git
- HTML5 越来越引起人们的关注,苹果甚至将 HTML5 视为 Flash 的掘墓人 。然而,作为一种尚未成型的技术,HTML5 对很多人来
- 学习使用存储过程(Stored Procedure),是ASP程序员的必须课之一。所有的大型数据库都支持存储过程,比如Oracle
- 本次小编向大家介绍的是根据用户的需求输入想爬取的内容及页数。主要步骤:1.提示用户输入爬取的内容及页码。2.根据用户输入,获取网址列表。3.
- 二维矩阵的transpose函数:不晓得该怎么起头,直接上干货。transpose()简单来说,就相当于数学中的转置,在矩阵中,转置就是把行
- 高阶函数除了可以接受函数作为参数外,还可以把函数作为结果值返回。看代码:# -*- coding: utf-8 -*-# @File &nb
- Asp中Server.ScriptTimeOut属性需要注意的一点Server.ScriptTimeout 这个属性给定Asp脚
- 本文实例讲述了Python实现批量下载图片的方法。分享给大家供大家参考。具体实现方法如下:#!/usr/bin/env python#-*-
- 1、fit和fit_generator的区别首先Keras中的fit()函数传入的x_train和y_train是被完整的加载进内存的,当然
- SQL Server导出表到EXCEL文件的存储过程:*--数据导出EXCEL导出表中的数据到Excel,包含字段名,文件为真正的Excel
- 一般调试程序的时候都比较倾向print,利用直接打印的方法作出判断,但是print只能打印出结果,对类型无法作出判断。例如:复制代码a =
- 0. 简介上一篇博客简单介绍了GMP模型,这一篇我们介绍一下Go调度器的初始化过程,也就是在main.main函数运行之前所做的事情。1.
- 采集中 或者 在线添加文章中 都可以用到此功能俺自己在baidu上搜索的保存远程图片到本地的代码 感觉比较难用点 而且没有现成的比较全的代码
- PDO::getAvailableDriversPDO::getAvailableDrivers — 返回一个可用驱动的数组(PHP 5 &
- 在我之前写的几篇网站优化的文章中,着墨最多的是减少HTTP请求。通过减少请求数目,你的浏览器必须能对你的网站所有内容成功检索,总的HTTP请
- 在这篇文章中,将向您展示如何使用Python链接目前主流的MongoDB(V3.4.0)数据库,主要使用PyMongo(v3.4.0)和Mo
- 如何用FILESYSTEMOBJECT组件来做一个站内搜索?看看下面我们提供的例子,主要由searchpage.htm和searchresu
- 函数名:FenYe(url,pageCount,recordCount,curPage,cssstyle)  
- 从我们论坛中收集了这段HTML制作页面需要最大化、最小化时可以借鉴参考。最大化效果:<OBJECT id="max