天天看點
傳回

優化快速排序的幾種方法

快速排序

1.基本思想

快速排序采用分治思想。經過一趟排序将待排序序列分割為獨立的兩部分，其中一部分的所有排序關鍵字均小于另一部分的所有排序關鍵字，再按上述方法對序列的兩部分分别進行快速排序，整個排序過程可以遞歸執行，最終達到整個序列有序的目的。

2.算法概述

分解：在待排序數列按照某種特定選取一個元素作為主元。利用主元對序列進行重排，使得序列分成獨立的兩個部分，其中一部分的所有排序關鍵字均小于另一部分的所有排序關鍵字，即序列所有排序關鍵字小于主元的排序關鍵字的元素置于主元的左側，其他元素置于右側。

。

解決：通過遞歸對主元左側的序列已經右側的序列進行快速排序來去求解子問題。

合并：因為快速排序是原址操作，是以不需要執行合并操作，同時也節省了部分空間。

3.算法實作（Python) 

# coding = utf-8

"""
快速排序的一些優化方式
"""
import random
import time


def quick_sort(lst, first=, last=):
    # 快速排序
    if first >= last:
        return lst
    low = first
    high = last
    pivot = lst[first]  # 選取第一個為主元
    while first < last:
        while first < last and lst[last] >= pivot:
            last -= 
        lst[first] = lst[last]
        while first < last and lst[first] <= pivot:
            first += 
        lst[last] = lst[first]
    lst[last] = pivot
    quick_sort(lst, low, first - )
    quick_sort(lst, first + , high)

4. 算法分析

運作時間

快速排序的最壞時間複雜度是Θ(n2)，平均情況下的時間複雜度為Θ(nlgn)。快速排序的漸近時間複雜度介于最壞情況和平均情況。

這裡分别采用确定的快速排序（即選取序列的第一個元素或最後一個序列為主元）分别針對輸入規模>500萬的序列進行排序，獲得确定的快速排序的運作時間。

輸入規模500萬的序列排序運作時間

算法 随機序列 重複序列 升序序列 降序序列
确定的快速排序 36084ms 遞歸深度過大，堆棧溢出 同左 同左
python内置sort方法 5372ms 93ms 184ms 99ms

測試資料分析

在針對輸入序列的資料是随機的時，我們設計的快速排序的效率是可以接受的。針對輸入序列是有序的時候，雖然因為遞歸深度過大，導緻堆棧溢出（Python的解釋器沒有針對做優化），無法成功執行完程式，但是我們也可以預料到，每次排序劃分長度都是1，也就是說我們需要将序列劃分500萬次，才能使序列重新有序，其時間複雜度和空間複雜度可想而知。此時的情況為最壞的情況即時間複雜度為Θ(n2)，即淪為普通的冒泡排序。在實際情況中，輸入序列很有可能是有序的或者是部分有序的，這時我們可以通過在算法中引入随機性，使得算法對所有的輸入都能獲得較好的期望性能，同時将随機化版本的快速排序被更多的人運用在大資料輸入情況下的排序算法。

優化方式1：引入随機性

随機選取主元元素

# coding = utf-8

"""
優化方法1：引入随機性
"""

import random
import time


def quick_sort(lst, first=, last=):
    # 快速排序
    if first >= last:
        return lst
    low = first
    high = last
    pivot_index = random.randint(first, last)  # 随機選取主元位置
    lst[first], lst[pivot_index] = lst[pivot_index], lst[first]  # 将主元置于首位
    pivot = lst[first]
    while first < last:
        while first < last and lst[last] >= pivot:
            last -= 
        lst[first] = lst[last]
        while first < last and lst[first] <= pivot:
            first += 
        lst[last] = lst[first]
    lst[last] = pivot
    quick_sort(lst, low, first - )
    quick_sort(lst, first + , high)
輸入規模500萬的序列排序的運作時間
算法 随機序列 重複序列 升序序列 降序序列
随機化快速排序 45830ms 遞歸深度過大，堆棧溢出 29147ms 29363ms
python内置sort方法 6027ms 139ms 113ms 122ms

測試資料分析

通過引入随機性，我們較好的解決了序列有序的時候出現的問題，但是仍然存在一個問題那就是如果序列為重複的資料或者資料大量重複的情況，隻引入随機化并不能很好的解決問題。這時候我們可以通過将排序關鍵字與主元相等的元素聚集在一起，下次不再對這些元素進行分割，這不僅可以解決目前的設計的算法在重複序列上存在的問題，也可以一定程度上優化對其他序列排序的效率。

優化方式2：聚集 

# coding = utf-8

"""
優化方法1：引入随機性
優化方法2：聚集
"""

import random
import time


def quick_sort(lst, first=, last=):
    # 快速排序
    if first >= last:
        return lst
    low = first
    high = last
    left_lst_len =   # 分割後第一個序列和第二個序列與主元相等元素的長度
    right_lst_len = 
    # 選取随機的主元，并将主元元素與第一個元素置換
    pivot_index = random.randint(first, last)
    lst[first], lst[pivot_index] = lst[pivot_index], lst[first]
    pivot = lst[first]
    while first < last:
        while first < last and lst[last] >= pivot:
            if lst[last] == pivot:
                right_lst_len += 
            last -= 
        lst[first] = lst[last]
        while first < last and lst[first] <= pivot:
            if lst[first] == pivot:
                left_lst_len += 
            first += 
        lst[last] = lst[first]
    lst[last] = pivot
    lst1_last = first -   # 儲存分割後第一個序列的最後位置和第二個序列的最開始的位置
    lst2_first = first + 
    flag = low
    while lst1_last - low >  and flag < lst1_last and left_lst_len > :  # 将第一個序列中與主元相等的元素置于主元左側
        if pivot == lst[flag]:
            while lst[lst1_last] == pivot and left_lst_len >  and lst1_last - low > :
                left_lst_len -= 
                lst1_last -= 
            if lst1_last >  and left_lst_len > :
                lst[flag], lst[lst1_last] = lst[lst1_last], lst[flag]
                left_lst_len -= 
                lst1_last -= 
            else:
                break
        flag += 
    flag = high
    while high - lst2_first >  and flag > lst2_first and right_lst_len > :  # 将第二個序列中與主元相等的元素置于主元右側
        if pivot == lst[flag]:
            while lst[lst2_first] == pivot and right_lst_len >  and high - lst2_first > :
                right_lst_len -= 
                lst2_first += 
            if lst2_first < high and right_lst_len > :
                lst[flag], lst[lst2_first] = lst[lst2_first], lst[flag]
                right_lst_len -= 
                lst2_first += 
            else:
                break
        flag -= 
    quick_sort(lst, low, lst1_last)
    quick_sort(lst, lst2_first, high)
輸入規模500萬的序列排序的運作時間
算法 随機序列 重複序列 升序序列 降序序列
随機化快速排序+聚集 63856ms 2272ms 38797ms 42183ms
python内置sort方法 7682ms 88ms 95ms 103ms

測試資料分析

通過将排序關鍵字與主元相等的元素聚集在一起，下次不再對這些元素進行分割，這不僅可以解決目前的設計的算法在重複序列上存在的問題，也可以一定程度上優化對其他序列排序的效率，如果序列的重複度（即重複出現的資料所占比例）越大，聚集所提高的效率越大。

優化方式3：三位數取中

取序列中lst[first]、lst[mid]、lst[last]中的中位數作為主元

# coding = utf-8

"""
優化方法2：聚集
優化方法3：三位數取中
"""

import random
import time


def quick_sort(lst, first=, last=):
    # 快速排序
    if first >= last:
        return lst
    low = first
    high = last
    left_lst_len =   # 分割後第一個序列和第二個序列與主元相等元素的長度
    right_lst_len = 
    select_pivot_median(lst, first, last)  # 選擇主元并将置于首位
    pivot = lst[first]
    while first < last:
        while first < last and lst[last] >= pivot:
            if lst[last] == pivot:
                right_lst_len += 
            last -= 
        lst[first] = lst[last]
        while first < last and lst[first] <= pivot:
            if lst[first] == pivot:
                left_lst_len += 
            first += 
        lst[last] = lst[first]
    lst[last] = pivot
    lst1_last = first -   # 儲存分割後第一個序列的最後位置和第二個序列的最開始的位置
    lst2_first = first + 
    flag = low
    while lst1_last - low >  and flag < lst1_last and left_lst_len > :  # 将第一個序列中與主元相等的元素置于主元左側
        if pivot == lst[flag]:
            while lst[lst1_last] == pivot and left_lst_len >  and lst1_last - low > :
                left_lst_len -= 
                lst1_last -= 
            if lst1_last >  and left_lst_len > :
                lst[flag], lst[lst1_last] = lst[lst1_last], lst[flag]
                left_lst_len -= 
                lst1_last -= 
            else:
                break
        flag += 
    flag = high
    while high - lst2_first >  and flag > lst2_first and right_lst_len > :  # 将第二個序列中與主元相等的元素置于主元右側
        if pivot == lst[flag]:
            while lst[lst2_first] == pivot and right_lst_len >  and high - lst2_first > :
                right_lst_len -= 
                lst2_first += 
            if lst2_first < high and right_lst_len > :
                lst[flag], lst[lst2_first] = lst[lst2_first], lst[flag]
                right_lst_len -= 
                lst2_first += 
            else:
                break
        flag -= 
    quick_sort(lst, low, lst1_last)
    quick_sort(lst, lst2_first, high)


def select_pivot_median(lst, first, last):
    # 将選取的主元即lst[first],lst[mid],lst[last]的中位數置于first坐标位置
    mid = first + ((last - first) >> )  # 計算序列中間元素的下标
    if lst[mid] > lst[last]:
        lst[mid], lst[last] = lst[last], lst[mid]
    if lst[first] > lst[last]:
        lst[first], lst[last] = lst[last], lst[first]
    if lst[mid] > lst[first]:
        lst[mid], lst[first] = lst[first], lst[mid]
輸入規模500萬的序列排序的運作時間
算法 随機序列 重複序列 升序序列 降序序列
三數取中的快速排序+聚集 53375ms 2550ms 30123ms 35552ms
python内置sort方法 5767ms 88ms 126ms 103ms

測試資料分析

通過引入随機性提高序列分割的效率，但是其最壞情況下的時間複雜度仍然是Θ(n2)。最佳情況下的劃分是可以将待排序的序列劃分為等長的序列，也就是說我們選取的主元是整個序列的中位數，但是如果要求整個序列的中位數那必定會花費更多的時間，有點得不償失的感覺。我們可以選取折中的辦法，選擇最左端、中心位置、最右端的元素中的中位數作為組元，能一定程度上快速排序的比較次數。

優化方式4：引入插入排序

插入排序在待排序序列長度一定時效率高于插入排序，我們可以在快速排序分割的子序列長度達到一定時采用插入排序進行排序

# coding = utf-8

"""
優化方法2：聚集
優化方法3：三位取中
優化方法4：插入排序
"""

import random
import time


def quick_sort(lst, first=, last=):
    if last - first +  > :
        insert_sort(lst, first, last)
    else:
        # 快速排序
        if first >= last:
            return lst
        low = first
        high = last
        left_lst_len =   # 分割後第一個序列和第二個序列與主元相等元素的長度
        right_lst_len = 
        select_pivot_median(lst, first, last)  # 選擇主元并将置于首位
        pivot = lst[first]
        while first < last:
            while first < last and lst[last] >= pivot:
                if lst[last] == pivot:
                    right_lst_len += 
                last -= 
            lst[first] = lst[last]
            while first < last and lst[first] <= pivot:
                if lst[first] == pivot:
                    left_lst_len += 
                first += 
            lst[last] = lst[first]
        lst[last] = pivot
        lst1_last = first -   # 儲存分割後第一個序列的最後位置和第二個序列的最開始的位置
        lst2_first = first + 
        flag = low
        while lst1_last - low >  and flag < lst1_last and left_lst_len > :  # 将第一個序列中與主元相等的元素置于主元左側
            if pivot == lst[flag]:
                while lst[lst1_last] == pivot and left_lst_len >  and lst1_last - low > :
                    left_lst_len -= 
                    lst1_last -= 
                if lst1_last >  and left_lst_len > :
                    lst[flag], lst[lst1_last] = lst[lst1_last], lst[flag]
                    left_lst_len -= 
                    lst1_last -= 
                else:
                    break
            flag += 
        flag = high
        while high - lst2_first >  and flag > lst2_first and right_lst_len > :  # 将第二個序列中與主元相等的元素置于主元右側
            if pivot == lst[flag]:
                while lst[lst2_first] == pivot and right_lst_len >  and high - lst2_first > :
                    right_lst_len -= 
                    lst2_first += 
                if lst2_first < high and right_lst_len > :
                    lst[flag], lst[lst2_first] = lst[lst2_first], lst[flag]
                    right_lst_len -= 
                    lst2_first += 
                else:
                    break
            flag -= 
        quick_sort(lst, low, lst1_last)
        quick_sort(lst, lst2_first, high)


def select_pivot_median(lst, first, last):
    # 将選取的主元即lst[first],lst[mid],lst[last]的中位數置于first坐标位置
    mid = first + ((last - first) >> )  # 計算序列中間元素的下标
    if lst[mid] > lst[last]:
        lst[mid], lst[last] = lst[last], lst[mid]
    if lst[first] > lst[last]:
        lst[first], lst[last] = lst[last], lst[first]
    if lst[mid] > lst[first]:
        lst[mid], lst[first] = lst[first], lst[mid]


def insert_sort(lst, first, last):
    # 插入排序
    for index in range(first + , last + ):
        key = lst[index]
        j = index - 
        while j >= first:
            if lst[j] > key:
                lst[j + ] = lst[j]
                lst[j] = key
            j -=
輸入規模500萬的序列排序的運作時間
算法 随機序列 重複序列 升序序列 降序序列
三數取中的快速排序+聚集+插入排序 40934ms 2549ms 21389ms 34769ms
python内置sort方法 5690ms 88ms 119ms 124ms

測試資料分析

針對長度較小或者部分有序數組時，插入排序的效率優于快速排序，引入插入排序将會使算法整體效率略有提高，而且這個方法适用于大部分序列。

其他優化方式

優化遞歸操作

我們可以使用尾遞歸的方式對快速排序的遞歸操作進行處理，來減少遞歸層次，避免堆棧溢出的發生，可以解決确定的快速排序無法處理已排序序列的問題

【待完成】。

使用并行算法或者多線程算法處理子序列

【待完成】

總結

快速排序的優化細節沒有處理好，導緻算法的整體效率沒有很大的提升，以後有時間對算法細節進行處理，可以達到更佳的效果。另外輸入資料都是随機生成的，導緻有的優化甚至比沒優化之前排序所花費的時間更多，這除了細節問題，還有資料特征不符合現實生活。現實生活中的資料經常是部分有序的序列，是以如果采用優化後的算法，實際運作情況會比目前測試的情況更佳。

參考資料

http://blog.csdn.net/hacker00011000/article/details/52176100

算法入門 快速排序 優化 算法 遞歸
上一篇: 現代社會宏觀治理的最大問題是資料造假
下一篇: 閑聊vue版本差異和開發中不太容易注意的點（基礎篇）

繼續閱讀