排序算法對比分析

冒泡排序:

冒泡排序是一種交換排序,相鄰之間的兩個元素進行比較,如果兩個元素的順序是錯誤的,那麼就交換位置.

具體的步驟是:

比較相鄰兩個元素,如果地一個元素比第二個元素大,那麼就交換位置 每對相鄰的元素做同樣的比較,從開頭的第一對元素,直到最後一對元素.經過這輪的比較交換後,最後的那個元素是最大的了,也就是說這個最大的元素在該列表是有順序了的,此後不再參與比較工作. 重復上面的個兩個步驟,每重復一次,列表中已經有序的元素就會增加一個,且這個元素不再參與比較.不斷的對越來越少的無序元素重復上面的步驟直到沒有元素參與比較時,該列表就是一個有順序的列表了. 參考實現代碼:

import random
l = [random.randint(0,101) for n in range(10)]
print l
for i in range(len(l)):
   for j in range(len(l)-i-1):
       if l[j] > l[j+1]:
           l[j],l[j+1] = l[j+1],l[j]
print l

冒泡排序是一種很慢的排序算法,時間復雜度為O(n^{2}), 因此只適用於少量數據的情景中.

快速排序:

快速排序的思路是采用分治法將一個list分成兩個子列表,它的步驟是:

在列表中選擇一個元素作為”基准”(pivot) 所有小於”基准”的元素都移到基准的左邊,所有大於”基准”的元素移到基准的右邊. 對基准左邊和右邊的兩個子集,重復第一步和第二步,直到子集中的元素只剩下一個元素為止 參考實現:

#!/usr/bin/env python

# Written by Magnus Lie Hetland 

"Everybody's favourite sorting algorithm... :)"

def partition(list, start, end):
    pivot = list[end]                          # Partition around the last value
    bottom = start-1                           # Start outside the area to be partitioned
    top = end                                  # Ditto

    done = 0
    while not done:                            # Until all elements are partitioned...

        while not done:                        # Until we find an out of place element...
            bottom = bottom+1                  # ... move the bottom up.

            if bottom == top:                  # If we hit the top...
                done = 1                       # ... we are done.
                break

            if list[bottom] > pivot:           # Is the bottom out of place?
                list[top] = list[bottom]       # Then put it at the top...
                break                          # ... and start searching from the top.

        while not done:                        # Until we find an out of place element...
            top = top-1                        # ... move the top down.

            if top == bottom:                  # If we hit the bottom...
                done = 1                       # ... we are done.
                break

            if list[top] < pivot:              # Is the top out of place?
                list[bottom] = list[top]       # Then put it at the bottom...
                break                          # ...and start searching from the bottom.

    list[top] = pivot                          # Put the pivot in its place.
    return top                                 # Return the split point

def quicksort(list, start, end):
    if start < end:                            # If there are two or more elements...
        split = partition(list, start, end)    # ... partition the sublist...
        quicksort(list, start, split-1)        # ... and sort both halves.
        quicksort(list, split+1, end)
    else:
        return

快速排序的時間復雜度為Ο(n log n)

選擇排序:

選擇排序每次從列表中查找出最小的元素,存放到已經是有序的列表中,再從剩余未排序的列表中查找最小的元素放入已排序好的列表的最後,依次類推直到所有元素排序完畢.

def selection_sort(l):
    for i in range(len(l)):
        min = i
        for j in range(i+1, len(l)):
            if l[min]>l[j]:
                min = j
        if l[i]!=l[min]:
            l[i],l[min] = l[min],l[i]

比較次數O(n^2),比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1)+(n-2)+…+1=n*(n-1)/2。 交換次數O(n),最好情況是，已經有序，交換0次；最壞情況是，逆序，交換n-1次。 交換次數比冒泡排序少多了，由於交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。