本文實例講述了Python實現(xiàn)的數(shù)據(jù)結構與算法之快速排序。分享給大家供大家參考。具體分析如下：
一、概述
快速排序（quick sort）是一種分治排序算法。該算法首先 選取 一個劃分元素（partition element，有時又稱為pivot）；接著重排列表將其 劃分 為三個部分：left（小于劃分元素pivot的部分）、劃分元素pivot、right（大于劃分元素pivot的部分），此時，劃分元素pivot已經(jīng)在列表的最終位置上；然后分別對left和right兩個部分進行 遞歸排序。
其中，劃分元素的 選取 直接影響到快速排序算法的效率，通常選擇列表的第一個元素或者中間元素或者最后一個元素作為劃分元素，當然也有更復雜的選擇方式；劃分 過程根據(jù)劃分元素重排列表，是快速排序算法的關鍵所在，該過程的原理示意圖如下：
<-- 選取劃分元素 -->
<-- 劃分過程 -->
<-- 劃分結果 -->
快速排序算法的優(yōu)點是：原位排序（只使用很小的輔助棧），平均情況下的時間復雜度為 O(n log n)。快速排序算法的缺點是：它是不穩(wěn)定的排序算法，最壞情況下的時間復雜度為 O(n2)。
二、Python實現(xiàn)
1、標準實現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#!/usr/bin/env python# -*- coding: utf-8 -*-def stdQuicksort(L): qsort(L, 0, len(L) - 1)def qsort(L, first, last): if first < last: split = partition(L, first, last) qsort(L, first, split - 1) qsort(L, split + 1, last)def partition(L, first, last): # 選取列表中的第一個元素作為劃分元素 pivot = L[first] leftmark = first + 1 rightmark = last while True: while L[leftmark] <= pivot: # 如果列表中存在與劃分元素pivot相等的元素，讓它位于left部分 # 以下檢測用于劃分元素pivot是列表中的最大元素時， #防止leftmark越界 if leftmark == rightmark: break leftmark += 1 while L[rightmark] > pivot: # 這里不需要檢測，劃分元素pivot是列表中的最小元素時， # rightmark會自動停在first處 rightmark -= 1 if leftmark < rightmark: # 此時，leftmark處的元素大于pivot， #而rightmark處的元素小于等于pivot，交換二者 L[leftmark], L[rightmark] = L[rightmark], L[leftmark] else: break # 交換first處的劃分元素與rightmark處的元素 L[first], L[rightmark] = L[rightmark], L[first] # 返回劃分元素pivot的最終位置 return rightmark |
2、Pythonic實現(xiàn)
|
1
2
3
4
5
6
7
|
#!/usr/bin/env python# -*- coding: utf-8 -*-def pycQuicksort(L): if len(L) <= 1: return L return pycQuicksort([x for x in L if x < L[0]]) + \ [x for x in L if x == L[0]] + \ pycQuicksort([x for x in L if x > L[0]]) |
對比 標準實現(xiàn) 可以看出，Pythonic實現(xiàn) 更簡潔、更直觀、更酷。但需要指出的是，Pythonic實現(xiàn) 使用了Python中的 列表解析 （List Comprehension，也叫列表展開、列表推導），每一次 遞歸排序 都會產(chǎn)生新的列表，因此失去了快速排序算法本來的 原位排序 的優(yōu)點。
三、算法測試
|
1
2
3
4
5
6
7
8
9
10
|
#!/usr/bin/env python# -*- coding: utf-8 -*-if __name__ == '__main__': L = [54, 26, 93, 17, 77, 31, 44, 55, 20] M = L[:] print('before stdQuicksort: ' + str(L)) stdQuicksort(L) print('after stdQuicksort: ' + str(L)) print('before pycQuicksort: ' + str(M)) print('after pycQuicksort: ' + str(pycQuicksort(M))) |
運行結果：
|
1
2
3
4
5
|
$ python testquicksort.pybefore stdQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20]after stdQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93]before pycQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20]after pycQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93] |
希望本文所述對大家的Python程序設計有所幫助。
