Python天天美味(30) - python資料結構與算法之快速排序

快速排序的原理是将取出第一個數，将整個數組分為兩波，一撥都大于這個數，另一波都小于這個數，然後遞歸用同樣的方法處理第一波數字和第二波數字。都說是“快速排序”，效率肯定比其他的一般排序算法高，下面我們就來驗證一把，比較一下所謂的“快速排序”和“冒泡排序”的性能差異。

def quicksort(data, low = 0, high = None):

    if high == None:

        high = len(data) - 1

    if low < high:

        s, i, j = data[low], low, high

        while i < j:

            while i < j and data[j] >= s:

                j = j - 1

            if i < j:

                data[i] = data[j]

                i = i + 1

            while i < j and data[i] <= s:

                data[j] = data[i]

        data[i] = s

        quicksort(data, low, i - 1)

        quicksort(data, i + 1, high)

def bubblesort(data):

    for i in range(len(data) - 1, 0, -1):

        for j in range(0, i):

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

                data[j], data[j + 1] = data[j + 1], data[j]

上面看來，冒泡排序隻需要5行，夠簡潔的，但性能咋樣呢？來比較一下吧：

import random

import datetime

import copy

def sort_perfmon(sortfunc, data):

    sort_data = copy.deepcopy(data)

    t1 = datetime.datetime.now()

    sortfunc(sort_data)

    t2 = datetime.datetime.now()

    print sortfunc.__name__, t2 - t1

    #print sort_data

data = [random.randint(0, 65536) for i in range(2000)]

#print data

sort_perfmon(quicksort, data)

sort_perfmon(bubblesort, data)

通過對随機的2000個數字進行排序，下面的結果可非常容易的看出，快速排序的優勢是非常大的。

quicksort 0:00:00.062000

bubblesort 0:00:03.563000

5. 代碼下載下傳

...

本文轉自CoderZh部落格園部落格，原文連結：http://www.cnblogs.com/coderzh/archive/2008/09/20/1294947.html，如需轉載請自行聯系原作者