拒绝懒惰的家

需求:

讨论一些常见算法的实现.

讨论:

1.插入排序

原理:找到适合的位置i,然后将i之后的元素后移,将元素放在i位置

def InsertSort(array):
    n=len(array)
    for j in xrange(1,n):
        key=array[j]
        i=j-1
        while i>=0 and array[i]>key:
            array[i+1]=array[i]
            i-=1
        array[i+1]=key
    return array
if __name__ == '__main__':
    print InsertSort([5,4,7,8,9,3,6,1,2,0])

2.归并排序

原理:首先将元素递归分组,确保每一组的元素是排序好的,然后将这些组合并即可.

def MergeSort(array,left,right):
    if left < right:
        middle = (left + right) >> 1
        MergeSort(array,left,middle)
        MergeSort(array,middle+1,right)
        Merge(array,left,middle,right)
    return array
def Merge(array,left,middle,right):
    L=array[left:middle+1]
    L+=[65535]
    R=array[middle+1:right+1]
    R+=[65535]
    i=j=0
    for k in xrange(left,right+1):
        try:
            if L[i]<=R[j]:
                array[k]=L[i]
                i+=1
            else:
                array[k]=R[j]
                j+=1
        except:
            print 'i=%d,j=%d'%(i,j)
if __name__ == '__main__':
    print MergeSort([5,4,7,8,9,3,6,1,2,0],0,9)

其中加入两个边界值,当到边界值时,表示一组已经复制完毕.

3.堆排序

原理:建立最大堆,然后将root(最大)元素和堆的最后一个元素互换(最小)即可.然后减少堆的大小,循环执行.

heapSize = 0
def MaxHeapify(array,i):
    global heapSize
    l=(i+1 << 1) - 1
    r=(i+1) << 1
    largest=0
    if l<heapSize and array[l] > array[i]:
        largest = l
    else:
        largest = i
    if r<heapSize and array[r] > array[largest]:
        largest = r
    if largest != i:
        tmp = array[i]
        array[i] = array[largest]
        array[largest] = tmp
        MaxHeapify(array,largest)

def BuildMaxHeap(array):
    global heapSize
    heapSize= len(array)
    for i in xrange(heapSize>>1,-1,-1):
        MaxHeapify(array,i)

def HeapSort(array):
    global heapSize
    BuildMaxHeap(array)
    for i in xrange(len(array)-1,0,-1):
        tmp = array[0]
        array[0] = array[i]
        array[i] = tmp
        heapSize-=1
        MaxHeapify(array,0)
    return array
if __name__ == '__main__':
    print HeapSort([5,4,7,8,9,3,6,1,2,0])

4.快速排序

原理:利用分执法的优点,进行交换排序.在元素多的情况下,快速排序的表现最好.

def QuickSort(array,left,right):
    if left < right:
        middle = Partition(array,left,right)
        QuickSort(array,left,middle-1)
        QuickSort(array,middle+1,right)
    return array
       
def Partition(array,left,right):
    x = array[right]
    i = left - 1
    for j in xrange(left,right):
        if array[j] <= x:
            i+=1
            tmp = array[i]
            array[i] = array[j]
            array[j] = tmp
    i+=1
    tmp = array[i]
    array[i] = array[right]
    array[right] = tmp
    return i
if __name__ == '__main__':
    print QuickSort([5,4,7,8,9,3,6,1,2,0],0,9)

5.给出一个生成随机序列的方法,我就是用这个方法测试的.

def ArrayGenerator(n):
    array = range(0,n)
    from random import randint
    for i in xrange(0,n):
        p = randint(i,n-1)
        tmp = array[i]
        array[i] = array[p]
        array[p] = tmp
    return array