纯归并排序的复杂度为： O(nlgn)，而纯插入排序的时间复杂度为：O(n^2)。数据量很大的时候采用归并排序但是在n较小的时候插入排序可能运行的会更快点。因此在归并排序中当子问题变得足够小时，采用插入排序来使得递归的叶子变粗可以加快排序速度。那么这个足够小到底怎么去衡量呢？ 请看下面：这么几个我不证明了，比较简单：A，插入排序最坏情况下可以在O(nk)时间内排序每个长度为k的n/k个子列表B，在最坏情况下可在O(nlg(n/k))的...
实例1: >>>L = [2,3,1,4] >>>L.sort() >>>L >>>[1,2,3,4] 实例2: >>>L = [2,3,1,4] >>>L.sort(reverse=True) >>>L >>>[4,3,2,1] 实例3:对第二个关键字排序 >>>L = [(b,6),(a,1),(c,3),(d,4)] >>>L.sort(lambda x,y:cmp(x[1],y[1])) >>>L >>>[(a, 1), (c, 3), (d, 4), (b, 6)] 实例4: 对第二个关键字排序 >>>L = [(b,6),(a,1),(c,3),(d,4)] >>>L.sort(key=lambda x:x[1]) >>>L >>>[(a, 1), (c, 3), (d, 4), (b, 6)] 实例5: 对第二个...
#!/usr/bin/env python#coding=utf-8#ChooseSort.py#user can choose sort style: desc(1) or asc(2)import stdinInputdef chooseSort( sortArray): arrayl=len(sortArray) if(arrayl<1): return for i in xrange(0,arrayl-1): min=i; for j in xrange(i+1,arrayl): if(sortArray[j]<sortArray[min]): min=j sortArray[i],sortArray[min]=sortArray[min],sort...
开始学习python，格式神马的都是浮云，直接上数据结构的算法。毕竟读代码学习最快1 接受输入的py代码，以后的算法的输入import这个文件#!/usr/bin/env python #coding=utf-8 # stdinInput.py intsortArrays=[] def stdinInput():sortArray=raw_input("please input num array that you want sort(use , to split every num) :")sortArrays=sortArray.split(,)for num in sortArrays:intnum=-1try:intnum=int(num)except:print "inp...
python语言中的列表排序方法有三个：reverse反转/倒序排序、sort正序排序、sorted可以获取排序后的列表。在更高级列表排序中，后两中方法还可以加入条件参数进行排序。reverse()方法将列表中元素反转排序，比如下面这样>>> x = [1,5,2,3,4]>>> x.reverse()>>> x[4, 3, 2, 5, 1]reverse列表反转排序：是把原列表中的元素顺序从左至右的重新存放，而不会对列表中的参数进行排序整理。如果需要对列表中的参数进行整理，就需要用到列表...
[Python]代码 def maopao(list):for i in range(0, len(list)):for j in range(len(list) - 1, i - 1, -1):if list[j] < list[j-1]:temp = list[j]list[j] = list[j-1]list[j-1] = temp#printResult(list)def printResult(list):for i in range(0, len(list)):print list[i],printList = [9,1,7,3,8,2,6,4,0] maopao(List) print List
一、插入排序#-*- coding:utf-8 -*- 描述 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。 是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置）， 而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再...
Python 算法 快速排序# -*- coding: utf-8 -*-from random import randint, shuffledef _partition(seq, p, r):"""数组划分，伪码如下：PARTITION(A, p, r)1 x ← A[r] // 作为划分主元2 i ← p-13 for j ← p to r-14 do if A[j] <= x5 then i ← i + 1 // 前划分区域的索引6 exchange A[i] ?A[j] // 小值交换到前面7 exchange A[i+1] ?A[r] // A[r]交换到前区域结尾8 return i + 1T(n) = θ(n)"""x =...
python算法 - python实现冒泡排序冒泡排序的运算原理：比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。实例代码# -*- encoding: utf-8 -*-def bubble_sort(seq, cmp=cmp): """冒泡排序，伪码...
对List进行排序，Python提供了两个方法方法1.用List的内建函数list.sort进行排序list.sort(func=None, key=None, reverse=False) Python实例：>>> list = [2,5,8,9,3] >>> list [2,5,8,9,3] >>> list.sort() >>> list [2, 3, 5, 8, 9] 方法2.用序列类型函数sorted(list)进行排序（从2.4开始）Python实例：>>> list = [2,5,8,9,3] >>> list [2,5,8,9,3] >>> sorted(list) [2, 3, 5, 8, 9] 两种方法的区别：so...
声明本文基于Python2.7语言，给出判断列表是否已排序的多种方法，并在作者的Windows XP主机(Pentium G630 2.7GHz主频2GB内存)上对比和分析其性能表现。一. 问题提出Haskell培训老师提出一个问题：如何判断列表是否已经排序？排序与否实际只是相邻元素间的某种二元关系，即a->a->Bool。所以第一步可以把二元组列表找出来；第二步是把这个函数作用于每个元组，然后用and操作。老师给出的实现代码如下：pair lst = zip lst ( tail lst...
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用。 该方法的基本思想是： 1．先从数列中取出一个数作为基准数。 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。 现在通过一个实例来说明快排。 比如有一个数组：6 2 4 5 3 第一步：选取一个基准数，不要被这个名词吓到了，你可以把它看作是一个比较大小的数，因...
QUICKSORT(A, p, r)是快速排序的子程序，调用划分程序对数组进行划分，然后递归地调用QUICKSORT(A, p, r)，以完成快速排序的过程。快速排序的最差时间复杂度为O(n2)，平时时间复杂度为O(nlgn)。最差时间复杂度的情况为数组基本有序的时候，平均时间复杂度为数组的数值分布较为平均的时候。在平时情况下快速排序跟堆排序的时间复杂度都为O(nlgn)，但是快速排序的常数项较小，所以要优于堆排序。 PARTITION(A, p, r) 代码如下: x ←...
代码如下: #!/usr/bin/python import sys def left_child(node): return node * 2 + 1 def right_child(node): return node * 2 + 2 def parent(node): if (node % 2): return (i - 1) / 2 else: return (i - 2) / 2 def max_heapify(array, i, heap_size): l = left_child(i) r = right_child(i) largest = i if l < heap_size and array[l] > array[i]: largest = l if r < heap_size and array[r] > array[largest]: largest = ...
代码如下:# -*- coding: utf-8 -*- def insertion_sort(A): """插入排序，作为桶排序的子排序""" n = len(A) if n <= 1: return A B = [] # 结果列表 for a in A: i = len(B) while i > 0 and B[i-1] > a: i = i - 1 B.insert(i, a); return B def bucket_sort(A): """桶排序，伪码如下： BUCKET-SORT(A) 1 n ← length[A] // 桶数 2 for i ← 1 to n ...