排序
分类
时间复杂度（最差、平均、和最好性能）: 列表（list）的大小n。一般而言，好的性能是O(
)，坏的性能是O(
)。对于一个排序理想的性能是O(n)，但平均而言不可能达到。基于比较的排序算法对大多数输入而言至少需要O(
空间复杂度
稳定性: 稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
比较
时间复杂度
空间复杂度
稳定性
稳定的
冒泡排序（bubble sort）: O(
鸡尾酒排序（cocktail sort）: O(
计数排序（counting sort）: O(n+k)；需要O(n+k)额外空间
桶排序（bucket sort）: O(n)；需要O(k)额外空间
插入排序（insertion sort）: O(
归并排序（merge sort）: O(
原地归并排序 : O(n\log^2 n)如果使用最佳的现在版本
二叉排序树排序（binary tree sort）: O(
鸽巢排序（pigeonhole sort）: O(n+k)；需要O(k)额外空间
基数排序（radix sort）: O(nk)；需要O(n)额外空间
侏儒排序（gnome sort）: O(
图书馆排序（library sort）: O(
)n额外空间
块排序（block sort）: O(
不稳定的
选择排序（selection sort）: O(
希尔排序（shell sort）: O(
)如果使用最佳的现在版本
克洛弗排序（Clover sort）: O(n)期望时间，O(
梳排序 : O(
堆排序（heap sort）: O(
平滑排序（smooth sort）: O(
快速排序（quick sort）: O(
内省排序（introsort）: O(
耐心排序（patience sort）: O(
)最坏情况时间，需要额外的O(n+k)空间，也需要找到最长的递增子序列（longest increasing subsequence）
不实用的
Bogo排序 : O(
)，最坏的情况下期望时间为无穷。
Stupid排序 : O(n^{3});递归版本需要O(
珠排序（bead sort）: O(n) 或 O(
),但需要特别的硬件
煎饼排序 : O(n),但需要特别的硬件
臭皮匠排序（stooge sort）算法简单，但需要约
的时间
比较
基于比较
冒泡
选择
插入
归并（递归实现）
快速（递归实现）
随机快速（递归实现）
堆排序
不基于比较
计数排序
基数排序
桶排序
代码实现
全部代码都已上传到Github
冒泡排序
class BubbleSort(Base):
def execute(self, L: List[int]) -> List[int]:
for i in range(0, self.length):
for j in range(i + 1, self.length):
if L[i] > L[j]:
L[i], L[j] = L[j], L[i]
return L分析
比较和交换需要一个以常量为界的时间，我们称之为c。 （标准）Bubble Sort中有两个嵌套循环。 外循环正好运行N次迭代。 但内部循环运行变得越来越短：
当 i = 0，（N-1）次迭代（比较和可能交换）时。
当 i = 1，（N-2）次迭代时，...
当 i =（N-2）时，1次迭代,
当 i=（N-1），0迭代.
因此，总迭代次数=（N-1）+（N-2）+ ... + 1 + 0 = N *（N-1）/ 2。
总时间= c N （N-1）/ 2 = O（N ^ 2）。
鸡尾酒排序
鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的性能，原因是冒泡排序只从一个方向进行比对（由低到高），每次循环只移动一个项目。
以序列（2,3,4,5,1）为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。
class CocktailSort(Base):
def execute(self, L: List[int]) -> List[int]:
flag = True
for i in range(len(L) // 2):
if flag:
flag = False
for j in range(i, len(L) - i - 1):
if L[j] > L[j+1]:
L[j], L[j+1] = L[j+1], L[j]
flag = True
for j in range(len(L) - 1 - i, i, -1):
if L[j] < L[j-1]:
L[j], L[j-1] = L[j-1], L[j]
flag = True
else:
break
return L分析
时间复杂度：鸡尾酒排序的效率还是很低的，两层循环，时间复杂度为 O(n^2) 。
空间复杂度：由于只需要几个临时变量，所以空间复杂度为 O(1) 。
插入排序
class InsertionSort(Base):
def execute(self, L: List[int]) -> List[int]:
for p in range(1, self.length):
tmp = L[p]
i = p
while i > 0 and L[i-1] > tmp:
L[i] = L[i-1]
i = i-1
L[i] = tmp
return L分析
外循环执行N-1次 内循环执行的次数取决于输入：
在最好的情况下，数组已经排序并且（L[i-1] > tmp）总是为假所以不需要移位数据，并且内部循环运行在O（1），
在最坏的情况下，数组被反向排序并且（L[i-1] > tmp）始终为真插入始终发生在数组的前端，并且内部循环以O（N）运行。
因此，最佳情况时间是O(N × 1) = O(N) ，最坏情况时间是O(N × N) = O(N2).
计数排序
当输入的元素是n个 0 到 k 之间的整数时，它的运行时间是 n+k。
由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。
class CountingSort(Base):
def execute(self, L: List[int]) -> List[int]:
n = len(L)
max_value = max(L)
min_value = min(L)
count = [0] * (max_value - min_value + 2) # 优化count数组空间
for i in L:
count[i] += 1
sort_L = []
for j in range(len(count)):
if count[j] != 0:
for y in range(count[j]):
sort_L.append(j)
return sort_L分析
计数排序用待排序的数值作为计数数组（列表）的下标，统计每个数值的个数，然后依次输出即可。
计数数组的大小取决于待排数据取值范围，所以对数据有一定要求，否则空间开销无法承受。
计数排序只需遍历一次数据，在计数数组中记录，输出计数数组中有记录的下标，时间复杂度为O(n+k)。
额外空间开销即指计数数组，实际上按数据值分为k类（大小取决于数据取值），空间复杂度O(k)。
桶排序
桶排序是计数排序的推广
将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序,在这里使用快排）
设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。
class BucketSort(Base):
def execute(self, L: List[int]) -> List[int]:
bucket_length = max(L) // 10 + 1
buckets = [[] for i in range(0, bucket_length)]
for i in L:
buckets[i // 10].append(i)
for i in buckets:
quicksort = QuickSort(len(i))
i = quicksort.execute(i)
sort_L = []
for i in buckets:
if isinstance(i, list):
for j in i:
sort_L.append(j)
else:
sort_L.append(i)
return sort_L快速排序
挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
分割：所有比基准值小的元素放在基准值的左边，所有比基准值大的元素放在基准值的右边，分割成两个子序列
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
class QuickSort(Base):
def execute(self, L: List[int]) -> List[int]:
length = len(L)
if length <= 1:
return L
self.quicksort(L, 0, length - 1)
return L
def partition(self, L: List[int], left: int, right: int) -> int:
key = left
while left < right:
while left < right and L[right] >= L[key]:
right -= 1
while left < right and L[left] <= L[key]:
left += 1
L[left], L[right] = L[right], L[left]
L[left], L[key] = L[key], L[left]
return left
def quicksort(self, L: List[int], left: int, right: int):
if left >= right:
return
mid = self.partition(L, left, right)
self.quicksort(L, left, mid - 1)
self.quicksort(L, mid + 1, right)归并排序
分而治之
（分）将一个序列从中间位置分成两个序列
继续将这两个子序列按照第一步继续二分下去
直到所有子序列的长度都为1（终止）
（治）两两合并成一个有序序列
class MergeSort(Base):
def execute(self, L: List[int]) -> List[int]:
return self.merge_sort(L)
def merge(self, a: List[int], b: List[int]) -> List[int]:
merged = []
i, j = 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
merged.append(a[i])
i += 1
else:
merged.append(b[j])
j += 1
merged.extend(a[i:])
merged.extend(b[j:])
return merged
def merge_sort(self, L: List[int]) -> List[int]:
if len(L) <= 1:
return L
mid = len(L) // 2
a = self.merge_sort(L[:mid])
b = self.merge_sort(L[mid:])
return self.merge(a, b)选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
class SelectionSort(Base):
def execute(self, L: List[int]) -> List[int]:
for i in range(self.length):
min_index = i
for j in range(i + 1, self.length):
if L[min_index] > L[j]:
min_index = j
L[min_index], L[i] = L[i], L[min_index]
return L参考
Last updated
Was this helpful?