对排序算法的一些总结（python版本）

只写了几个，还有一些没有完成的。

新手同学可以从if __name__='__main__':后面开始看。

暂时只完成了以下几个：
#print "快排序列：",(sort.Quicksort(list))

#归并排序
#print "归并序列：",sort.Merge_sort(list, 0, len(list)-1)

#选择排序
#print "选择序列：",(sort.Selectsort(list))

#插入排序
#print "插入序列：",(sort.Insertsort(list))

#冒泡法
#print "冒泡序列：",(sort.Bubblesort(list))

#桶排序
#数据为0-1的随机小数，桶排序适合：已知范围的序列排序，！大数据，牺牲空间换时间:最好O（n），最差O(n+c),是稳定
#items = [random() for _ in xrange(10000)]
#print "桶序列：",sort.bucket_sort(items)
 

#coding=utf-8
import sys

from random import random
from timeit import Timer

class Sort_method(object):
    '''
    不管插入还是选择都基于这样一个规律：数组分为两段，前段有序，后段无序。
    '''
    def __init__(self):
        pass
    
    def Quicksort(self,nums):
        if len(nums)<=1:#为空或只有一个元素时，返回它自身
            return nums #递归的中断条件
        small,big=[],[]
        flag = nums.pop()#去除最右边的元素做标杆
        for i in nums:
            if ii :
                if nums[j]=0 and nums[j]>key:
                nums[j+1]=nums[j]
                j-=1
            nums[j+1]=key       #在适当位置插入元素
        return nums  
    
    def Merge(self ,nums, first, middle, last):  
    # 切片边界,左闭右开并且是了0为开始  
        lnums = nums[first:middle+1]   
        rnums = nums[middle+1:last+1]  
        lnums.append(sys.maxint)  
        rnums.append(sys.maxint)  
        l = 0  
        r = 0  
        for i in range(first, last+1):  
            if lnums[l] < rnums[r]:  
                nums[i] = lnums[l]  
                l+=1  
            else:  
                nums[i] = rnums[r]  
                r+=1       
    def Merge_sort(self, nums, first, last):  
        ''''' merge sort 
        merge_sort函数中传递的是下标，不是元素个数 
        '''  
        if first < last:  
            middle = (first + last)/2  
            self.Merge_sort(nums, first, middle)  
            self.Merge_sort(nums, middle+1, last)  
            self.Merge(nums, first, middle,last) 
        return nums
    
    def insertion_sort(self,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(self,A):
        """桶排序，伪码如下：
        BUCKET-SORT(A)
        1  n ← length[A] // 桶数
        2  for i ← 1 to n
        3    do insert A[i] into list B[floor(nA[i])] // 将n个数分布到各个桶中
        4  for i ← 0 to n-1
        5    do sort list B[i] with insertion sort // 对各个桶中的数进行排序
        6  concatenate the lists B[0],B[1],...,B[n-1] together in order // 依次串联各桶中的元素
        桶排序假设输入由一个随机过程产生，该过程将元素均匀地分布在区间[0,1)上。
        """
        n = len(A)
        buckets = [[] for _ in xrange(n)] # n个空桶
        for a in A:
            buckets[int(n * a)].append(a)
        B = []
        for b in buckets:
            B.extend(self.insertion_sort(b))
        return B

if __name__=="__main__":
    sort = Sort_method()
    list = [3,5,1,6,9,0,7,3,2,6]
    print "原始序列：",list
    #调用快排
    #print "快排序列：",(sort.Quicksort(list))
    
    #快排改进
    
    #归并排序
    #print "归并序列：",sort.Merge_sort(list, 0, len(list)-1)
    
    #选择排序
    #print "选择序列：",(sort.Selectsort(list))
    
    #插入排序
    #print "插入序列：",(sort.Insertsort(list))
    
    #冒泡法
    #print "冒泡序列：",(sort.Bubblesort(list))       
        
    #桶排序
    #数据为0-1的随机小数，桶排序适合：已知范围的序列排序，！大数据，牺牲空间换时间:最好O（n），最差O(n+c),是稳定
    #items = [random() for _ in xrange(10000)]
    #print "桶序列：",sort.bucket_sort(items)
    
    #堆排序