python排序(冒泡， 快速)

之前用java时学习的一些基础算法，今天在python上也研究下。

1. 冒泡排序

算法步骤：

　　50   30   70  90 10

　　1）50 跟 30 比不用交换。

　　2）步数+1， 30 跟70比交换， 50 70 30 90 10。

　　3）步数+1， 30跟90比交换， 50 70 90 30 10。

　　4）步数+1， 30跟10比不用交换， 50 70 90 30 10.

　　即：一次比较， 排出最小一个元素

再来张图看看（网上找的）

# -*- coding: UTF-8 -*-
import random
import datetime

def bubble_sort(array):
    for i in range(len(array)):
        for j in range(i,len(array)):
            if array[j] < array[i]:
                tmp = array[j]
                array[j] = array[i]
                array[i] = tmp

def getRandomList():
    array = []
    for i in range(1, 10000):
        array.append(i)
    random.shuffle(array)

　　return array

if __name__ == '__main__':
    array = getRandomList()
    t1 = datetime.datetime.now()
    bubble_sort(array)
    t2 = datetime.datetime.now()
    print t2 - t1
##########
0:00:12.298000
[Finished in 12.5s]

2. 快速排序：

　　

　　推荐看看这个视频：http://v.youku.com/v_show/id_XMzMyODk4NTQ4.html

def getRandomList():
    array = []
    for i in range(1, 10000):
        array.append(i)
    random.shuffle(array)

    return array

def subSort(array,low,high):
    key = array[low]
    while low < high:
        while low < high and array[high] >= key:
            high -= 1
        while low < high and array[high] < key:
            array[low] = array[high]
            low += 1
            array[high] = array[low]
    array[low] = key
    return low


def quickSort(array,low,high):
     if low < high:
        index = subSort(array,low,high)
        quickSort(array,low,index )
        quickSort(array,index+1,high)

if __name__ == '__main__':
    array = getRandomList()
    t1 = datetime.datetime.now()
    # bubble_sort(array)
    quickSort(array, 0, len(array)-1)
    t2 = datetime.datetime.now()
    print t2 - t1
#######
0:00:00.047000
[Finished in 0.2s]

从结果看两个速度差距不是一般大啊！！！！