Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之快速排序詳解

更新時間：2015年04月22日 15:40:23 作者：RussellLuo

這篇文章主要介紹了Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之快速排序,詳細分析了快速排序的原理與Python實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了Python實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之快速排序。分享給大家供大家參考。具體分析如下：

一、概述

快速排序（quick sort）是一種分治排序算法。該算法首先選取一個劃分元素（partition element，有時又稱為pivot）；接著重排列表將其劃分為三個部分：left（小于劃分元素pivot的部分）、劃分元素pivot、right（大于劃分元素pivot的部分），此時，劃分元素pivot已經(jīng)在列表的最終位置上；然后分別對left和right兩個部分進行遞歸排序。

其中，劃分元素的選取直接影響到快速排序算法的效率，通常選擇列表的第一個元素或者中間元素或者最后一個元素作為劃分元素，當然也有更復雜的選擇方式；劃分過程根據(jù)劃分元素重排列表，是快速排序算法的關(guān)鍵所在，該過程的原理示意圖如下：

<-- 選取劃分元素 -->

<-- 劃分過程 -->

<-- 劃分結(jié)果 -->

快速排序算法的優(yōu)點是：原位排序（只使用很小的輔助棧），平均情況下的時間復雜度為 O(n log n)?？焖倥判蛩惴ǖ娜秉c是：它是不穩(wěn)定的排序算法，最壞情況下的時間復雜度為 O(n2)。

二、Python實現(xiàn)

1、標準實現(xiàn)

#!/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)

#!/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)點。

三、算法測試

#!/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)))

運行結(jié)果：

$ python testquicksort.py
before 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程序設計有所幫助。

您可能感興趣的文章: