基于python的七種經(jīng)典排序算法(推薦)
一、排序的基本概念和分類
所謂排序,就是使一串記錄,按照其中的某個或某些關(guān)鍵字的大小,遞增或遞減的排列起來的操作。排序算法,就是如何使得記錄按照要求排列的方法。
排序的穩(wěn)定性:
經(jīng)過某種排序后,如果兩個記錄序號同等,且兩者在原無序記錄中的先后秩序依然保持不變,則稱所使用的排序方法是穩(wěn)定的,反之是不穩(wěn)定的。
內(nèi)排序和外排序
內(nèi)排序:排序過程中,待排序的所有記錄全部放在內(nèi)存中
外排序:排序過程中,使用到了外部存儲。
通常討論的都是內(nèi)排序。
影響內(nèi)排序算法性能的三個因素:
- 時間復(fù)雜度:即時間性能,高效率的排序算法應(yīng)該是具有盡可能少的關(guān)鍵字比較次數(shù)和記錄的移動次數(shù)
- 空間復(fù)雜度:主要是執(zhí)行算法所需要的輔助空間,越少越好。
- 算法復(fù)雜性。主要是指代碼的復(fù)雜性。
根據(jù)排序過程中借助的主要操作,可把內(nèi)排序分為:
- 插入排序
- 交換排序
- 選擇排序
- 歸并排序
按照算法復(fù)雜度可分為兩類:
- 簡單算法:包括冒泡排序、簡單選擇排序和直接插入排序
- 改進(jìn)算法:包括希爾排序、堆排序、歸并排序和快速排序
以下的七種排序算法只是所有排序算法中最經(jīng)典的幾種,不代表全部。
二、 冒泡排序
冒泡排序(Bubble sort):時間復(fù)雜度O(n^2)
交換排序的一種。其核心思想是:兩兩比較相鄰記錄的關(guān)鍵字,如果反序則交換,直到?jīng)]有反序記錄為止。
其實現(xiàn)細(xì)節(jié)可以不同,比如下面3種:
1.最簡單排序?qū)崿F(xiàn):bubble_sort_simple
2.冒泡排序:bubble_sort
3.改進(jìn)的冒泡排序:bubble_sort_advance
#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 冒泡排序算法 class SQList: def __init__(self, lis=None): self.r = lis def swap(self, i, j): """定義一個交換元素的方法,方便后面調(diào)用。""" temp = self.r[i] self.r[i] = self.r[j] self.r[j] = temp def bubble_sort_simple(self): """ 最簡單的交換排序,時間復(fù)雜度O(n^2) """ lis = self.r length = len(self.r) for i in range(length): for j in range(i+1, length): if lis[i] > lis[j]: self.swap(i, j) def bubble_sort(self): """ 冒泡排序,時間復(fù)雜度O(n^2) """ lis = self.r length = len(self.r) for i in range(length): j = length-2 while j >= i: if lis[j] > lis[j+1]: self.swap(j, j+1) j -= 1 def bubble_sort_advance(self): """ 冒泡排序改進(jìn)算法,時間復(fù)雜度O(n^2) 設(shè)置flag,當(dāng)一輪比較中未發(fā)生交換動作,則說明后面的元素其實已經(jīng)有序排列了。 對于比較規(guī)整的元素集合,可提高一定的排序效率。 """ lis = self.r length = len(self.r) flag = True i = 0 while i < length and flag: flag = False j = length - 2 while j >= i: if lis[j] > lis[j + 1]: self.swap(j, j + 1) flag = True j -= 1 i += 1 def __str__(self): ret = "" for i in self.r: ret += " %s" % i return ret if __name__ == '__main__': sqlist = SQList([4,1,7,3,8,5,9,2,6]) # sqlist.bubble_sort_simple() # sqlist.bubble_sort() sqlist.bubble_sort_advance() print(sqlist)
三、簡單選擇排序
簡單選擇排序(simple selection sort):時間復(fù)雜度O(n^2)
通過n-i次關(guān)鍵字之間的比較,從n-i+1個記錄中選出關(guān)鍵字最小的記錄,并和第i(1<=i<=n)個記錄進(jìn)行交換。
通俗的說就是,對尚未完成排序的所有元素,從頭到尾比一遍,記錄下最小的那個元素的下標(biāo),也就是該元素的位置。再把該元素交換到當(dāng)前遍歷的最前面。其效率之處在于,每一輪中比較了很多次,但只交換一次。因此雖然它的時間復(fù)雜度也是O(n^2),但比冒泡算法還是要好一點。
#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 簡單選擇排序 class SQList: def __init__(self, lis=None): self.r = lis def swap(self, i, j): """定義一個交換元素的方法,方便后面調(diào)用。""" temp = self.r[i] self.r[i] = self.r[j] self.r[j] = temp def select_sort(self): """ 簡單選擇排序,時間復(fù)雜度O(n^2) """ lis = self.r length = len(self.r) for i in range(length): minimum = i for j in range(i+1, length): if lis[minimum] > lis[j]: minimum = j if i != minimum: self.swap(i, minimum) def __str__(self): ret = "" for i in self.r: ret += " %s" % i return ret if __name__ == '__main__': sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0]) sqlist.select_sort() print(sqlist)
四、直接插入排序
直接插入排序(Straight Insertion Sort):時間復(fù)雜度O(n^2)
基本操作是將一個記錄插入到已經(jīng)排好序的有序表中,從而得到一個新的、記錄數(shù)增1的有序表。
#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 直接插入排序 class SQList: def __init__(self, lis=None): self.r = lis def insert_sort(self): lis = self.r length = len(self.r) # 下標(biāo)從1開始 for i in range(1, length): if lis[i] < lis[i-1]: temp = lis[i] j = i-1 while lis[j] > temp and j >= 0: lis[j+1] = lis[j] j -= 1 lis[j+1] = temp def __str__(self): ret = "" for i in self.r: ret += " %s" % i return ret if __name__ == '__main__': sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0]) sqlist.insert_sort() print(sqlist)
該算法需要一個記錄的輔助空間。最好情況下,當(dāng)原始數(shù)據(jù)就是有序的時候,只需要一輪對比,不需要移動記錄,此時時間復(fù)雜度為O(n)。然而,這基本是幻想。
五、希爾排序
希爾排序(Shell Sort)是插入排序的改進(jìn)版本,其核心思想是將原數(shù)據(jù)集合分割成若干個子序列,然后再對子序列分別進(jìn)行直接插入排序,使子序列基本有序,最后再對全體記錄進(jìn)行一次直接插入排序。
這里最關(guān)鍵的是跳躍和分割的策略,也就是我們要怎么分割數(shù)據(jù),間隔多大的問題。通常將相距某個“增量”的記錄組成一個子序列,這樣才能保證在子序列內(nèi)分別進(jìn)行直接插入排序后得到的結(jié)果是基本有序而不是局部有序。下面的例子中通過:increment = int(increment/3)+1來確定“增量”的值。
希爾排序的時間復(fù)雜度為:O(n^(3/2))
#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 希爾排序 class SQList: def __init__(self, lis=None): self.r = lis def shell_sort(self): """希爾排序""" lis = self.r length = len(lis) increment = len(lis) while increment > 1: increment = int(increment/3)+1 for i in range(increment+1, length): if lis[i] < lis[i - increment]: temp = lis[i] j = i - increment while j >= 0 and temp < lis[j]: lis[j+increment] = lis[j] j -= increment lis[j+increment] = temp def __str__(self): ret = "" for i in self.r: ret += " %s" % i return ret if __name__ == '__main__': sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0,123,22]) sqlist.shell_sort() print(sqlist)
六、堆排序
堆是具有下列性質(zhì)的完全二叉樹:
每個分支節(jié)點的值都大于或等于其左右孩子的值,稱為大頂堆;
每個分支節(jié)點的值都小于或等于其做右孩子的值,稱為小頂堆;
因此,其根節(jié)點一定是所有節(jié)點中最大(最?。┑闹?。
如果按照層序遍歷的方式(廣度優(yōu)先)給節(jié)點從1開始編號,則節(jié)點之間滿足如下關(guān)系:
堆排序(Heap Sort)就是利用大頂堆或小頂堆的性質(zhì)進(jìn)行排序的方法。堆排序的總體時間復(fù)雜度為O(nlogn)。(下面采用大頂堆的方式)
其核心思想是:將待排序的序列構(gòu)造成一個大頂堆。此時,整個序列的最大值就是堆的根節(jié)點。將它與堆數(shù)組的末尾元素交換,然后將剩余的n-1個序列重新構(gòu)造成一個大頂堆。反復(fù)執(zhí)行前面的操作,最后獲得一個有序序列。
#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 堆排序 class SQList: def __init__(self, lis=None): self.r = lis def swap(self, i, j): """定義一個交換元素的方法,方便后面調(diào)用。""" temp = self.r[i] self.r[i] = self.r[j] self.r[j] = temp def heap_sort(self): length = len(self.r) i = int(length/2) # 將原始序列構(gòu)造成一個大頂堆 # 遍歷從中間開始,到0結(jié)束,其實這些是堆的分支節(jié)點。 while i >= 0: self.heap_adjust(i, length-1) i -= 1 # 逆序遍歷整個序列,不斷取出根節(jié)點的值,完成實際的排序。 j = length-1 while j > 0: # 將當(dāng)前根節(jié)點,也就是列表最開頭,下標(biāo)為0的值,交換到最后面j處 self.swap(0, j) # 將發(fā)生變化的序列重新構(gòu)造成大頂堆 self.heap_adjust(0, j-1) j -= 1 def heap_adjust(self, s, m): """核心的大頂堆構(gòu)造方法,維持序列的堆結(jié)構(gòu)。""" lis = self.r temp = lis[s] i = 2*s while i <= m: if i < m and lis[i] < lis[i+1]: i += 1 if temp >= lis[i]: break lis[s] = lis[i] s = i i *= 2 lis[s] = temp def __str__(self): ret = "" for i in self.r: ret += " %s" % i return ret if __name__ == '__main__': sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22]) sqlist.heap_sort() print(sqlist)
堆排序的運行時間主要消耗在初始構(gòu)建堆和重建堆的反復(fù)篩選上。
其初始構(gòu)建堆時間復(fù)雜度為O(n)。
正式排序時,重建堆的時間復(fù)雜度為O(nlogn)。
所以堆排序的總體時間復(fù)雜度為O(nlogn)。
堆排序?qū)υ加涗浀呐判驙顟B(tài)不敏感,因此它無論最好、最壞和平均時間復(fù)雜度都是O(nlogn)。在性能上要好于冒泡、簡單選擇和直接插入算法。
空間復(fù)雜度上,只需要一個用于交換的暫存單元。但是由于記錄的比較和交換是跳躍式的,因此,堆排序也是一種不穩(wěn)定的排序方法。
此外,由于初始構(gòu)建堆的比較次數(shù)較多,堆排序不適合序列個數(shù)較少的排序工作。
七、歸并排序
歸并排序(Merging Sort):建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個非常典型的應(yīng)用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。
#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 歸并排序 class SQList: def __init__(self, lis=None): self.r = lis def swap(self, i, j): """定義一個交換元素的方法,方便后面調(diào)用。""" temp = self.r[i] self.r[i] = self.r[j] self.r[j] = temp def merge_sort(self): self.msort(self.r, self.r, 0, len(self.r)-1) def msort(self, list_sr, list_tr, s, t): temp = [None for i in range(0, len(list_sr))] if s == t: list_tr[s] = list_sr[s] else: m = int((s+t)/2) self.msort(list_sr, temp, s, m) self.msort(list_sr, temp, m+1, t) self.merge(temp, list_tr, s, m, t) def merge(self, list_sr, list_tr, i, m, n): j = m+1 k = i while i <= m and j <= n: if list_sr[i] < list_sr[j]: list_tr[k] = list_sr[i] i += 1 else: list_tr[k] = list_sr[j] j += 1 k += 1 if i <= m: for l in range(0, m-i+1): list_tr[k+l] = list_sr[i+l] if j <= n: for l in range(0, n-j+1): list_tr[k+l] = list_sr[j+l] def __str__(self): ret = "" for i in self.r: ret += " %s" % i return ret if __name__ == '__main__': sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 12, 77, 34, 23]) sqlist.merge_sort() print(sqlist)
- 歸并排序?qū)υ夹蛄性胤植记闆r不敏感,其時間復(fù)雜度為O(nlogn)。
- 歸并排序在計算過程中需要使用一定的輔助空間,用于遞歸和存放結(jié)果,因此其空間復(fù)雜度為O(n+logn)。
- 歸并排序中不存在跳躍,只有兩兩比較,因此是一種穩(wěn)定排序。
總之,歸并排序是一種比較占用內(nèi)存,但效率高,并且穩(wěn)定的算法。
八、快速排序
快速排序(Quick Sort)由圖靈獎獲得者Tony Hoare發(fā)明,被列為20世紀(jì)十大算法之一。冒泡排序的升級版,交換排序的一種??焖倥判虻臅r間復(fù)雜度為O(nlog(n))。
快速排序算法的核心思想:通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?,其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小,然后分別對這兩部分繼續(xù)進(jìn)行排序,以達(dá)到整個記錄集合的排序目的。
#!/usr/bin/env python # -*- coding:utf-8 -*- # Author: Liu Jiang # Python 3.5 # 快速排序 class SQList: def __init__(self, lis=None): self.r = lis def swap(self, i, j): """定義一個交換元素的方法,方便后面調(diào)用。""" temp = self.r[i] self.r[i] = self.r[j] self.r[j] = temp def quick_sort(self): """調(diào)用入口""" self.qsort(0, len(self.r)-1) def qsort(self, low, high): """遞歸調(diào)用""" if low < high: pivot = self.partition(low, high) self.qsort(low, pivot-1) self.qsort(pivot+1, high) def partition(self, low, high): """ 快速排序的核心代碼。 其實就是將選取的pivot_key不斷交換,將比它小的換到左邊,將比它大的換到右邊。 它自己也在交換中不斷變換自己的位置,直到完成所有的交換為止。 但在函數(shù)調(diào)用的過程中,pivot_key的值始終不變。 :param low:左邊界下標(biāo) :param high:右邊界下標(biāo) :return:分完左右區(qū)后pivot_key所在位置的下標(biāo) """ lis = self.r pivot_key = lis[low] while low < high: while low < high and lis[high] >= pivot_key: high -= 1 self.swap(low, high) while low < high and lis[low] <= pivot_key: low += 1 self.swap(low, high) return low def __str__(self): ret = "" for i in self.r: ret += " %s" % i return ret if __name__ == '__main__': sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22]) sqlist.quick_sort() print(sqlist)
- 快速排序的時間性能取決于遞歸的深度。
- 當(dāng)pivot_key恰好處于記錄關(guān)鍵碼的中間值時,大小兩區(qū)的劃分比較均衡,接近一個平衡二叉樹,此時的時間復(fù)雜度為O(nlog(n))。
- 當(dāng)原記錄集合是一個正序或逆序的情況下,分區(qū)的結(jié)果就是一棵斜樹,其深度為n-1,每一次執(zhí)行大小分區(qū),都要使用n-i次比較,其最終時間復(fù)雜度為O(n^2)。
- 在一般情況下,通過數(shù)學(xué)歸納法可證明,快速排序的時間復(fù)雜度為O(nlog(n))。
- 但是由于關(guān)鍵字的比較和交換是跳躍式的,因此,快速排序是一種不穩(wěn)定排序。
- 同時由于采用的遞歸技術(shù),該算法需要一定的輔助空間,其空間復(fù)雜度為O(logn)。
基本的快速排序還有可以優(yōu)化的地方:
1. 優(yōu)化選取的pivot_key
前面我們每次選取pivot_key的都是子序列的第一個元素,也就是lis[low],這就比較看運氣。運氣好時,該值處于整個序列的靠近中間值,則構(gòu)造的樹比較平衡,運氣比較差,處于最大或最小位置附近則構(gòu)造的樹接近斜樹。
為了保證pivot_key選取的盡可能適中,采取選取序列左中右三個特殊位置的值中,處于中間值的那個數(shù)為pivot_key,通常會比直接用lis[low]要好一點。在代碼中,在原來的pivot_key = lis[low]這一行前面增加下面的代碼:
m = low + int((high-low)/2) if lis[low] > lis[high]: self.swap(low, high) if lis[m] > lis[high]: self.swap(high, m) if lis[m] > lis[low]: self.swap(m, low)
如果覺得這樣還不夠好,還可以將整個序列先劃分為3部分,每一部分求出個pivot_key,再對3個pivot_key再做一次上面的比較得出最終的pivot_key。這時的pivot_key應(yīng)該很大概率是一個比較靠譜的值。
2. 減少不必要的交換
原來的代碼中pivot_key這個記錄總是再不斷的交換中,其實這是沒必要的,完全可以將它暫存在某個臨時變量中,如下所示:
def partition(self, low, high): lis = self.r m = low + int((high-low)/2) if lis[low] > lis[high]: self.swap(low, high) if lis[m] > lis[high]: self.swap(high, m) if lis[m] > lis[low]: self.swap(m, low) pivot_key = lis[low] # temp暫存pivot_key的值 temp = pivot_key while low < high: while low < high and lis[high] >= pivot_key: high -= 1 # 直接替換,而不交換了 lis[low] = lis[high] while low < high and lis[low] <= pivot_key: low += 1 lis[high] = lis[low] lis[low] = temp return low
3. 優(yōu)化小數(shù)組時的排序
快速排序算法的遞歸操作在進(jìn)行大量數(shù)據(jù)排序時,其開銷能被接受,速度較快。但進(jìn)行小數(shù)組排序時則不如直接插入排序來得快,也就是殺雞用牛刀,未必就比菜刀來得快。
因此,一種很樸素的做法就是根據(jù)數(shù)據(jù)的多少,做個使用哪種算法的選擇而已,如下改寫qsort方法:
def qsort(self, low, high): """根據(jù)序列長短,選擇使用快速排序還是簡單插入排序""" # 7是一個經(jīng)驗值,可根據(jù)實際情況自行決定該數(shù)值。 MAX_LENGTH = 7 if high-low < MAX_LENGTH: if low < high: pivot = self.partition(low, high) self.qsort(low, pivot - 1) self.qsort(pivot + 1, high) else: # insert_sort方法是我們前面寫過的簡單插入排序算法 self.insert_sort()
4. 優(yōu)化遞歸操作
可以采用尾遞歸的方式對整個算法的遞歸操作進(jìn)行優(yōu)化,改寫qsort方法如下:
def qsort(self, low, high): """根據(jù)序列長短,選擇使用快速排序還是簡單插入排序""" # 7是一個經(jīng)驗值,可根據(jù)實際情況自行決定該數(shù)值。 MAX_LENGTH = 7 if high-low < MAX_LENGTH: # 改用while循環(huán) while low < high: pivot = self.partition(low, high) self.qsort(low, pivot - 1) # 采用了尾遞歸的方式 low = pivot + 1 else: # insert_sort方法是我們前面寫過的簡單插入排序算法 self.insert_sort()
九、排序算法總結(jié)
排序算法的分類:
沒有十全十美的算法,有有點就會有缺點,即使是快速排序算法,也只是整體性能上的優(yōu)越,也存在排序不穩(wěn)定,需要大量輔助空間,不適于少量數(shù)據(jù)排序等缺點。
七種排序算法性能對比
- 如果待排序列基本有序,請直接使用簡單的算法,不要使用復(fù)雜的改進(jìn)算法。
- 歸并排序和快速排序雖然性能高,但是需要更多的輔助空間。其實就是用空間換時間。
- 待排序列的元素個數(shù)越少,就越適合用簡單的排序方法;元素個數(shù)越多就越適合用改進(jìn)的排序算法。
- 簡單選擇排序雖然在時間性能上不好,但它在空間利用上性能很高。特別適合,那些數(shù)據(jù)量不大,每條數(shù)據(jù)的信息量又比較多的一類元素的排序。
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
python pandas最常用透視表實現(xiàn)應(yīng)用案例
透視表是一種可以對數(shù)據(jù)動態(tài)排布并且分類匯總的表格格式,它在數(shù)據(jù)分析中有著重要的作用和地位,在本文中,我將為你介紹python中如何使用pandas包實現(xiàn)透視表的功能,以及一些常見的應(yīng)用案例2024-01-01詳解如何用python實現(xiàn)一個簡單下載器的服務(wù)端和客戶端
這篇文章主要介紹了詳解如何用python實現(xiàn)一個簡單下載器的服務(wù)端和客戶端,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10淺談四種快速易用的Python數(shù)據(jù)可視化方法
這篇文章主要介紹了淺談四種快速易用的Python數(shù)據(jù)可視化方法,數(shù)據(jù)可視化,是指用圖形的方式來展現(xiàn)數(shù)據(jù),從而更加清晰有效地傳遞信息,主要方法包括圖表類型的選擇和圖表設(shè)計的準(zhǔn)則,需要的朋友可以參考下2023-04-04關(guān)于Python 多重繼承時metaclass conflict問題解決與原理探究
這篇文章主要介紹了Python 多重繼承時metaclass conflict問題解決與原理探究 ,需要的朋友可以參考下2022-10-10