各种排序算法

#! /usr/bin/env python

#coding=gbk

#时间复杂度 o(n^2)

def insertSort(a, l):

    for i in range(1, l, 1):

        key = a[i];

        j = i-1;

        while j >= 0 and a[j] > key:

            a[j+1] = a[j];

            j=j-1;

        a[j+1] = key

        

    #print "direct insert sort\n",a

    return a;

#时间复杂度 o(n^2)

def binsertSort(a, l):

    for i in range(1, l, 1):

        key = a[i];

        low = 0;

        hight = i-1;

        

        while low <= hight:

            m = (low+hight)/2;

            if key < a[m]: hight = m -1;

            else: low = m + 1;

        

        for j in range(i-1, low-1, -1):

            a[j+1]=a[j]; 

            

        a[hight+1] = key;

    #print "bipartition insert sort\n",a;

    return a;

#时间复杂度 o(n^2)

def shellInsertSort(a, l):

    jump = l/2;

    while jump >= 1:

        j = l-jump;

        for i in range(j):

            if a[i] > a[i+jump]:

                k = a[i];

                a[i] = a[i+jump];

                a[i+jump] = k;

                pass

            pass

        jump = jump/2;

        pass

    #print "shell insert sort \n", a;

    return a;            

#时间复杂度 o(n^2)

def bubbleSort(a, l):

    for i in range(l-1, 0, -1):

        bExit = True;

        for j in range(i):

            if a[j] > a[j+1]: 

                k = a[j];

                a[j] = a[j+1];

                a[j+1] = k;

                bExit = False;

                pass

            pass

        if bExit: break;

        pass

    #print "bubble sort \n", a;

    return a;

#时间复杂度 o(n^2)

def selectSort(a, l):

    for i in range(l):

        j = i;

        for k in range(i, l, 1):

            if a[k] < a[j]: j = k;

        

        if i != j: 

            m = a[i];

            a[i] = a[j];

            a[j] = m;

    return a;

            

#时间复杂度 o(nlogn)

def quickSort(a, low, high):    

    if low < high:

        key = a[high];

        i = low;

        for j in range(low, high, 1):

            if a[j] <= key:

                m = a[i];

                a[i] = a[j];

                a[j] = m;

                i +=1;

        a[high] = a[i];

        a[i] = key;

        

        if i < high: quickSort(a, low, i-1);

        if i > low: quickSort(a, i, high);               

    

    return a;      

#时间复杂度 o(nlogn) 

def quickSort2(a, low, high):

    if low < high:

        i = low;

        j = high;

        key = a[i]

        while i < j:

            

            while i=key: j-=1;

            a[i] = a[j];

            while i

            a[j]=a[i];

        a[j] = key;

        

        if j < high: 

            quickSort2(a, low, j-1);

        if j > low: 

            quickSort2(a, j+1, high);

    

    return a;      

        

        

# max heap

# O(nlogn)

def heapSort(a, l):

    # build heap

    for i in range(1, l, 1):

        x = a[i];

        j = i;

        k = (j-1)/2;

        while k>=0 and a[k] < x:

            a[j] = a[k];

            j = k;

            k = (j-1)/2;

        a[j] = x;

    #print a

    #sort heap

    for i in range(l-1, -1, -1):

        x = a[i]

        max = a[0]

        j = 0;

        k = 2*j+1;

        while k

            if k+1

                k += 1;

            if a[k] <= a[i]: 

                break;

            a[j] = a[k];

            j = k;

            k = 2*j+1;

        a[j] = x;

        a[i] = max;   

    return a;

        

a = [16, 25, 12, 30, 47, 11, 23, 36, 9, 18, 31];    

#a=range(10,0,-1)

#a.sort(None,None,False)

#print a[0]

#insertSort(a[:], len(a))

#binsertSort(a[:], len(a))

#shellInsertSort(a[:], len(a));

#bubbleSort(a, len(a))

#a =  quickSort2(a, 0, len(a)-1);

a = heapSort(a, len(a))

print a

print "over"

#print selectSort(a, len(a))

阅读(905) | 评论(0) | 转发(0) |

0

上一篇：python满足你需要的50个模块

下一篇：归并排序 递归 非递归