前段时间为准备百度面试恶补的东西,虽然最后还是被刷了,还是把那几天的“战利品”放点上来,算法一直是自己比较薄弱的地方,以后还要更加努力啊。
下面用Python实现了几个常用的排序,如快速排序,选择排序,以及二路并归排序等等。
#encoding=utf-8 import random from copy import copydef 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]
本文向大家介绍js实现常用排序算法,包括了js实现常用排序算法的使用技巧和注意事项,需要的朋友参考一下 本文为大家分享了js实现常用排序算法,具体内容如下 1.冒泡排序 2.选择排序 3.插入排序 4.希尔排序 5.归并排序 6.快速排序 总结:算法效率比较: 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持呐喊教程。
本文向大家介绍python实现bucket排序算法实例分析,包括了python实现bucket排序算法实例分析的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了python实现bucket排序算法。分享给大家供大家参考。具体实现方法如下: 希望本文所述对大家的Python程序设计有所帮助。
本文向大家介绍Python实现的堆排序算法示例,包括了Python实现的堆排序算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现的堆排序算法。分享给大家供大家参考,具体如下: 堆排序的思想: 堆是一种数据结构,可以将堆看作一棵完全二叉树,这棵二叉树满足,任何一个非叶节点的值都不大于(或不小于)其左右孩子节点的值。 将一个无序序列调整为一个堆,就可以找出这个序列的最大值
本文向大家介绍Python实现的桶排序算法示例,包括了Python实现的桶排序算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现的桶排序算法。分享给大家供大家参考,具体如下: 桶排序也叫计数排序,简单来说,就是将数据集里面所有元素按顺序列举出来,然后统计元素出现的次数。最后按顺序输出数据集里面的元素。 但是桶排序非常浪费空间, 比如需要排序的范围在0~2000之间,
本文向大家介绍Python实现的选择排序算法示例,包括了Python实现的选择排序算法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现的选择排序算法。分享给大家供大家参考,具体如下: 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
本文向大家介绍python实现八大排序算法(1),包括了python实现八大排序算法(1)的使用技巧和注意事项,需要的朋友参考一下 排序 排序是计算机内经常进行的一种操作,其目的是将一组”无序”的记录序列调整为”有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能完全在内存中完成,需要访问