注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

用Python实现常见的排序算法

python 水墨上仙 1895次浏览 已收录 手机上查看

实现了直接插入排序、直接选择排序、冒泡排序、快速排序
来源:http://www.lfyzjck.com

#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))


喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……