首先来看归并排序，也称合并排序。具体操作参考维基百科。

参考代码如下：

def merg_sort(lst):
    if(len(lst) <= 1):  return lst
    left = merg_sort(lst[:len(lst)/2])
    right = merg_sort(lst[len(lst)/2:len(lst)])
    result = []
    while len(left) > 0 and len(right)> 0:
        if( left[0] > right[0]):
            result.append(right.pop(0))
        else:
            result.append(left.pop(0))

    if(len(left)>0): result.extend(merg_sort(left))
    else: result.extend(merg_sort(right))

    return result

print merg_sort([8,7,43,2,5])

稍微有点罗嗦版，不过这样写最能体现整个操作过程：

def merge_sort(list2):
    merge_sort_r(list2, 0, len(list2) -1)

# merge sort recursive (used by merge_sort)
def merge_sort_r(list2, first, last):
    if first < last:
        sred = (first + last)/2
        merge_sort_r(list2, first, sred)
        merge_sort_r(list2, sred + 1, last)
        merge(list2, first, last, sred)

# merge (used by merge_sort_r)
def merge(list2, first, last, sred):
    helper_list = []
    i = first
    j = sred + 1
    while i <= sred and j <= last:
        if list2 [i] <= list2 [j]:
            helper_list.append(list2[i])
            i += 1
        else:
            helper_list.append(list2 [j])
            j += 1
    while i <= sred:
        helper_list.append(list2[i])
        i +=1
    while j <= last:
        helper_list.append(list2[j])
        j += 1
    for k in range(0, last - first + 1):
        list2[first + k] = helper_list [k]

接下来看看快速排序：同样具体操作参考wiki

import random
def quickSort(lst):
	if(len(lst) <= 1):return lst
	greater = []
	less = []
	pivot = lst.pop(random.randint(0,len(lst)-1))
	for item in lst:
		if(item < pivot): less.append(item)
		else: greater.append(item)
	return quickSort(less)+[pivot]+quickSort(greater)

ary=[1,5,14,3,2,45,2,0,01,-1]

或者看个简洁版：

def qsort(L):
   if not L: return []
   return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \
          qsort([x for x in L[1:] if x>=L[0]])

写成一句话：

 def quicksort(a): return a if len(a) <= 1 else quicksort([x for x in a[1:] if x <= a[0]]) + [a[0]] + quicksort([x for x in a[1:] if x > a[0]])

–EOF–

你可能还感兴趣的相关文章: wxPython：动态添加和删除Widget Matplotlib只保存部分区域图像(Subplot) (2) Ubuntu安装Matplotlib (3) Chilkat中的AES加密功能(Python示例) (2) 快速移除Python List中的重复项 (3) python将十六进制字符转为数字