基於python的七種經典排序演算法的詳細介紹
- 高洛峰原創
- 2017-03-23 16:43:041630瀏覽
一、排序的基本概念和分類
所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序演算法，就是如何使得記錄依照要求排列的方法。
排序的穩定性：
經過某種排序後，如果兩個記錄序號同等，且兩者在原始無序記錄中的先後秩序依然保持不變，則稱所使用的排序方法是穩定的，反之是不穩定的。
內排序與外排序
內排序：排序過程中，待排序的所有記錄全部放在記憶體中
外排序：排序過程中，使用到了外部儲存。
通常討論的都是內排序。
影響內排序演算法效能的三個因素：
時間複雜度：即時間效能，高效率的排序演算法應該是具有盡可能少的關鍵字比較次數與記錄的移動次數
空間複雜度：主要是執行演算法所需的輔助空間，越少越好。
演算法複雜性。主要是指程式碼的複雜性。
依排序過程中藉助的主要操作，可將內排序分成：
# 插入排序
交換排序
選擇排序
歸併排序
依演算法複雜度可分為兩類：
簡單演算法：包含冒泡排序、簡單選擇排序和直接插入排序
改進演算法：包括希爾排序、堆排序、歸併排序和快速排序
以下的七種排序演算法只是所有排序演算法中最經典的幾種，不代表全部。
二、冒泡排序
冒泡排序（Bubble sort）：時間複雜度O(n^2)
交換排序的一種。其核心思想是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序記錄為止。
其實作細節可以不同，例如下面3種：
1.最簡單排序實作:bubble_sort_simple
2.冒泡排序:bubble_sort
# 3.改進的冒泡排序: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):
"""定义一个交换元素的方法，方便后面调用。"""
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def bubble_sort_simple(self):
"""
最简单的交换排序，时间复杂度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):
"""
冒泡排序，时间复杂度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):
"""
冒泡排序改进算法，时间复杂度O(n^2)
设置flag，当一轮比较中未发生交换动作，则说明后面的元素其实已经有序排列了。
对于比较规整的元素集合，可提高一定的排序效率。
"""
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）:時間複雜度O(n^2)
透過n-i次關鍵字之間的比較，從n-i+1個記錄中選出關鍵字最小的記錄，並和第i （1
通俗的說就是，對尚未完成排序的所有元素，從頭到尾比一遍，記錄下最小的那個元素的下標，也就是該元素的位置。再把該元素交換到目前遍歷的最前面。其效率之處在於，每一輪比較了很多次，但只交換一次。因此雖然它的時間複雜度也是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):
"""定义一个交换元素的方法，方便后面调用。"""
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def select_sort(self):
"""
简单选择排序，时间复杂度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）:時間複雜度O( n^2)
基本操作是將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄數增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)
# 下标从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)此演算法需要一個記錄的輔助空間。最好情況下，當原始資料就是有序的時候，只需要一輪對比，不需要移動記錄，此時時間複雜度為O(n)。然而，這基本是幻想。 
五、希爾排序
希爾排序（Shell Sort）是插入排序的改進版本，其核心思想是將原
資料集
合分割成若干個子序列，然後再對子序列分別進行直接插入排序，使子序列基本上有序，最後再對全體記錄進行一次直接插入排序。 這裡最關鍵的是跳躍和分割的策略，也就是我們要怎麼分割數據，間隔多大的問題。通常將相距某個「增量」的記錄組成一個子序列，這樣才能保證在子序列內分別進行直接插入排序後得到的結果是基本有序而不是局部有序。下面的範例中透過：increment = int(increment/3)+1來決定「增量」的值。
希爾排序的時間複雜度為：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)
六、堆排序
堆是具有下列性质的完全二叉树：
每个分支节点的值都大于或等于其左右孩子的值，称为大顶堆；
每个分支节点的值都小于或等于其做右孩子的值，称为小顶堆；
因此，其根节点一定是所有节点中最大（最小）的值。
如果按照层序遍历的方式（广度优先）给节点从1开始编号，则节点之间满足如下关系：
堆排序（Heap Sort）就是利用大顶堆或小顶堆的性质进行排序的方法。堆排序的总体时间复杂度为O(nlogn)。（下面采用大顶堆的方式）
其核心思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆的根节点。将它与堆数组的末尾元素交换，然后将剩余的n-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 swap(self, i, j):
"""定义一个交换元素的方法，方便后面调用。"""
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)
# 将原始序列构造成一个大顶堆
# 遍历从中间开始，到0结束，其实这些是堆的分支节点。
while i >= 0:
self.heap_adjust(i, length-1)
i -= 1
# 逆序遍历整个序列，不断取出根节点的值，完成实际的排序。
j = length-1
while j > 0:
# 将当前根节点，也就是列表最开头，下标为0的值，交换到最后面j处
self.swap(0, j)
# 将发生变化的序列重新构造成大顶堆
self.heap_adjust(0, j-1)
j -= 1
def heap_adjust(self, s, m):
"""核心的大顶堆构造方法，维持序列的堆结构。"""
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)
堆排序的运行时间主要消耗在初始构建堆和重建堆的反复筛选上。
其初始构建堆时间复杂度为O(n)。
正式排序时，重建堆的时间复杂度为O(nlogn)。
所以堆排序的总体时间复杂度为O(nlogn)。
堆排序对原始记录的排序状态不敏感，因此它无论最好、最坏和平均时间复杂度都是O(nlogn)。在性能上要好于冒泡、简单选择和直接插入算法。
空间复杂度上，只需要一个用于交换的暂存单元。但是由于记录的比较和交换是跳跃式的，因此，堆排序也是一种不稳定的排序方法。
此外，由于初始构建堆的比较次数较多，堆排序不适合序列个数较少的排序工作。
七、归并排序
归并排序（Merging Sort）：建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
#!/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):
"""定义一个交换元素的方法，方便后面调用。"""
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)
归并排序对原始序列元素分布情况不敏感，其时间复杂度为O(nlogn)。
归并排序在计算过程中需要使用一定的辅助空间，用于递归和存放结果，因此其空间复杂度为O(n+logn)。
归并排序中不存在跳跃，只有两两比较，因此是一种稳定排序。
总之，归并排序是一种比较占用内存，但效率高，并且稳定的算法。
八、快速排序
快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n))。
快速排序算法的核心思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分继续进行排序，以达到整个记录集合的排序目的。
#!/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):
"""定义一个交换元素的方法，方便后面调用。"""
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def quick_sort(self):
"""调用入口"""
self.qsort(0, len(self.r)-1)
def qsort(self, low, high):
"""递归调用"""
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不断交换，将比它小的换到左边，将比它大的换到右边。
它自己也在交换中不断变换自己的位置，直到完成所有的交换为止。
但在函数调用的过程中，pivot_key的值始终不变。
:param low:左边界下标
:param high:右边界下标
:return:分完左右区后pivot_key所在位置的下标
"""
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)
快速排序的时间性能取决于递归的深度。
当pivot_key恰好处于记录关键码的中间值时，大小两区的划分比较均衡，接近一个平衡二叉树，此时的时间复杂度为O(nlog(n))。
当原记录集合是一个正序或逆序的情况下，分区的结果就是一棵斜树，其深度为n-1，每一次执行大小分区，都要使用n-i次比较，其最终时间复杂度为O(n^2)。
在一般情况下，通过数学归纳法可证明，快速排序的时间复杂度为O(nlog(n))。
但是由于关键字的比较和交换是跳跃式的，因此，快速排序是一种不稳定排序。
同时由于采用的递归技术，该算法需要一定的辅助空间，其空间复杂度为O(logn)。
基本的快速排序还有可以优化的地方：
1. 优化选取的pivot_key
前面我们每次选取pivot_key的都是子序列的第一个元素，也就是lis[low]，这就比较看运气。运气好时，该值处于整个序列的靠近中间值，则构造的树比较平衡，运气比较差，处于最大或最小位置附近则构造的树接近斜树。
为了保证pivot_key选取的尽可能适中，采取选取序列左中右三个特殊位置的值中，处于中间值的那个数为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应该很大概率是一个比较靠谱的值。
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. 优化小数组时的排序
快速排序算法的递归操作在进行大量数据排序时，其开销能被接受，速度较快。但进行小数组排序时则不如直接插入排序来得快，也就是杀鸡用牛刀，未必就比菜刀来得快。
因此，一种很朴素的做法就是根据数据的多少，做个使用哪种算法的选择而已，如下改写qsort方法：
def qsort(self, low, high):
"""根据序列长短，选择使用快速排序还是简单插入排序"""
# 7是一个经验值，可根据实际情况自行决定该数值。
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. 优化递归操作
可以采用尾递归的方式对整个算法的递归操作进行优化，改写qsort方法如下：
def qsort(self, low, high):
"""根据序列长短，选择使用快速排序还是简单插入排序"""
# 7是一个经验值，可根据实际情况自行决定该数值。
MAX_LENGTH = 7
if high-low < MAX_LENGTH:
# 改用while循环
while low < high:
pivot = self.partition(low, high)
self.qsort(low, pivot - 1)
# 采用了尾递归的方式
low = pivot + 1
else:
# insert_sort方法是我们前面写过的简单插入排序算法
self.insert_sort()
九、排序算法总结
排序算法的分类：
没有十全十美的算法，有有点就会有缺点，即使是快速排序算法，也只是整体性能上的优越，也存在排序不稳定，需要大量辅助空间，不适于少量数据排序等缺点。
七种排序算法性能对比
如果待排序列基本有序，请直接使用简单的算法，不要使用复杂的改进算法。
归并排序和快速排序虽然性能高，但是需要更多的辅助空间。其实就是用空间换时间。
待排序列的元素个数越少，就越适合用简单的排序方法；元素个数越多就越适合用改进的排序算法。
简单选择排序虽然在时间性能上不好，但它在空间利用上性能很高。特别适合，那些数据量不大，每条数据的信息量又比较多的一类元素的排序。
以上是基於python的七種經典排序演算法的詳細介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！