基础算法--排序算法

排序算法包括：

插入排序（insert sort）
快速排序（quick sort）
快速选择（quick select）

 堆排序(heap select)

 

http://stackoverflow.com/questions/1034846/finding-nth-item-of-unsorted-list-without-sorting-the-list/1036240#1036240
http://en.wikipedia.org/wiki/Quick_select

 

下面是我写的一些丑陋代码

 

def insert_sort(target,obj):
    if target[0]==None:
        target[0]=obj
        return target

    for i in xrange(len(target)):                       
        if obj>target[i] and (obj<target[i+1] or target[i+1]==None) :
            j = i+1
            k = len(target)-1
            while k>j:
                target[k] = target[k-1]
                k=k-1
            target[j] = obj
            break
    return target

target = [None for x in range(10)]

for x in [1,17,14,3,19,7,2,4,10]:
    print insert_sort(target,x)

 

 

参考：

程序员编程艺术：第三章、寻找最小的k个数

十三个经典算法研究与总结、目录+索引