排序算法
2020-08-28 本文已影响0人
dingtom
| 排序算法 | 平均时间复杂度 | 最好/差时间复杂度 | 空间复杂度 | 数据对象稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n)/O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2)/O(n2) | O(1) | 不稳定 |
| 插入排序 | O(n2) | O(n)/O(n2) | O(1) | 稳定 |
| 希尔排序 | O(n^(1.3-2)) | O(1) | 不稳定 | |
| 快速排序 | O(nlog2n) | O(nlog2n)/O(n2) | O(log2n) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n)/O(nlog2n) | O(1) | 不稳定 |
| 归并排序 | O(nlog2n) | O(nlog2n)/O(nlog2n) | O(n) | 稳定 |
| 计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
| 桶排序 | O(n) | O(n) | O(m) | 稳定 |
| 基数排序 | O(k*n) | O(n2) | 稳定 |
不稳定：快选堆希
稳定：排序后，关键字相同的元素保持原顺序中的相对位置不变
O(n*log2n) 快归堆希
快、归，使用了递归需要栈保存信息
插入排序：基本有序的数组排序。快速排序此时最差(取第n个为基准）
快速排序：内部排序算法平均性能最优。
堆排序：取一组数中K个最大\小的元素。
基数排序：所有中国人生日排序。
冒泡、插入有时可达线性时间
冒泡排序
原理：n-1轮，从头开始，前面和后面比较交换，找出未排序中最大的数，放到未排序序列的后面。
image
每一轮比较可能多个元素移动位置，而元素位置的互换是需要消耗资源的，所以这是一种偏慢的排序算法，仅适用于对于含有较少元素的数列进行排序。
def bubbleSort(arr):
for i in range(len(arr)-1): # 最后一个不用比
for j in range(len(arr)-1-i): # 比到len-i
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
bubbleSort(a)
稳定性：它是指对同样的数据进行排序，会不会改变它的相对位置。比如 [ 1, 3, 2, 4, 2 ] 经过排序后，两个相同的元素 2 位置会不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。
空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);
时间复杂度：由于嵌套了 2 层循环，故为 O(n*n);
选择排序
n-1轮， 从未排序第一个开始对和后面的比较找到最小的，和未排序第一个对调 。
交换次数比冒泡排序少，就 减少cpu的消耗，所以在数据量小的时候可以用选择排序，实际适用的场合非常少。
def selectionSort(arr):
for i in range(len(arr)-1):
min_index = i # 设i最小
for j in range(i+1, len(arr)): # 和i后面的比
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
a = [12, 11, 13, 5, 0, 6, 7, 0, 12, 34, 54, 2, 3]
selectionSort(a)
稳定性：排序过程中元素是按顺序进行遍历，相同元素相对位置不会发生变化，故稳定。
空间复杂度：在原序列进行操作，故为 O( 1 );
时间复杂度：需要 2 次循环遍历，故为 O( n * n );
插入排序
原理：n轮，未排序第一个，向前和已排序比较，找到一个小于或者等于它的元素，插入到该元素后面。
def insertionSort(arr):
for i in range(1, len(arr)):
sorted_index = i-1
current_value = arr[i]
# 在已排序列中找到比当前值小的索引，然后交换位置
while sorted_index>=0 and current_value<arr[sorted_index]:
arr[sorted_index+1] = arr[sorted_index] # 往后腾空位
sorted_index -= 1
arr[sorted_index+1] = current_value
return arr
a = [12, 11, 13, 5, 0, 6, 7, 0, 12, 34, 54, 2, 3]
insertionSort(a)
稳定性：它是从后往前遍历已排序好的序列，相同元素不会改变位置，故为稳定排序；
空间复杂度：它是在原序列进行排序，故为 O ( 1 );
时间复杂度：排序的过程中，首先要遍历所有的元素，然后在已排序序列中找到合适的位置并插入。共需要 2 层循环，故为 O ( n * n );
希尔排序
也称递减增量排序算法
是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序.
def shellSort(arr):
gap = len(arr)//2
while gap > 0:
for i in range(gap, len(arr)):
sorted_index = i-gap # 要与前面元素比较的索引
current_value = arr[i]
# 不能超过gap而且前面的数大，交换，跟更前面的比较
while sorted_index>=0 and current_value<arr[sorted_index]:
arr[sorted_index+gap] = arr[sorted_index] # 往后腾空位
sorted_index -= gap
arr[sorted_index+gap] = current_value
gap = int(gap/2)
return arr
a = [12, 11, 13, 5, 0, 6, 7, 0, 12, 34, 54, 2, 3]
print(shellSort(a))
稳定性：它可能会把相同元素分到不同的组中，那么两个相同的元素就有可能调换相对位置，故不稳定。
空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);
时间复杂度：希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(log n的3/2)，希尔排序时间复杂度的下界是n*log2n
快速排序
（根据基准数将数组分为三部分）递归， 拼接起来
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
print(quicksort([3, 6, 8, 19, 1, 5])) # [1，3, 5, 6, 8, 19]
堆排序
堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
递归调整大根堆。(在堆中做结构调整使得父节点的值大于子节点)
- 从下到上，递归调整大根堆，生成大根堆
- 堆顶最大，和未排序末尾交换，得到新的无序区(R0,R1,……Ri-1)和新的有序区(Ri,……Rn)，从上到下，不管已排序好的，调整为大根堆
# 递归调整为大根堆。在堆中做结构调整使得父节点的值大于子节点
def heapify(arr, heap_size, root):
largest = root # 指示最大值索引
left = 2*root+1 # 左子节点索引
right = left+1 # 右子节点索引
# 递归，找出最大值索引
if left<heap_size and arr[largest]<arr[left]:largest = left
if right<heap_size and arr[largest]<arr[right]:largest = right
# 交换
if largest != root:
arr[root], arr[largest] = arr[largest], arr[root] # 交换
heapify(arr, heap_size, largest) # 递归
def heapSort(arr):
# 从下到上 生成大根堆
for i in range(len(arr)//2-1, 0, -1): # heapify如果初始根比子节点大，则结束
print(i)
heapify(arr, len(arr), i)
# 堆顶最大，和未排序末尾交换，得到新的无序区(R0,R1,……Ri-1)和新的有序区(Ri,……Rn)
for i in range(len(arr)-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0) # 从上到下不管已排序好的，调整为大根堆
return arr
a = [12, 11, 13, 5, 0, 6, 7, 0, 12, 34, 54, 2, 3]
print(heapSort(a))
归并排序
递归（分成两个子序列， 将两个排好的子序列合并）
def merge_sort(arr):
if len(arr) <= 1:
return arr
left = merge_sort(arr[:len(arr)//2])#
right = merge_sort(arr[len(arr)//2:])
sorted = []
while left and right:
sorted.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
sorted.extend(right if right else left) #该方法没有返回值，但会在已存在的列表中添加新的列表内容
return sorted
a = [12, 11, 13, 5, 0, 6, 7, 0, 12, 34, 54, 2, 3]
print(merge_sort(a))
计数排序
arr每个元素放进max-min个桶里，依次从桶里取出放进arr
def countingSort(arr):
min_num, max_num = min(arr), max(arr)
buckets = [0]*(max_num-min_num+1)
# 装进桶里
for i in arr:
buckets[i-min_num]+=1
# 依次从桶里取出
arr.clear()
for i, buc in enumerate(buckets):
while buc>0:
arr.append(i+min_num)
buc -= 1
return arr
a = [12, 11, 13, 5, 0, 6, 7, 0, 12, 34, 54, 2, 3]
countingSort(a)
桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
- 在额外空间充足的情况下，尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
image
def bucket_sort(arr):
min_num = min(arr)
max_num = max(arr)
# 桶的大小
bucket_range = (max_num-min_num) / len(arr)
# 桶数组
buckets = [ [] for i in range(max_num-min_num+1)]
# 向桶数组填数
for i in range(len(arr)):
buckets[int((arr[i]-min_num)//bucket_range)].append(arr[i])
arr.clear()
# 回填，这里桶内部排序直接调用了sorted
for b in buckets:
for i in sorted(b):
arr.append(i)
return arr
arr = [12, 11, 13, 5, 0, 6, 7, 0, 12, 34, 54, 2, 3]
print(bucket_sort(arr))
基数排序
- 取得数组中的最大数，并取得位数；
- 对数位较短的数前面补零； 先从个位开始，根据位值(0-9)分别放到0~9号桶中;
- 再将放置在0~9号桶中的数据按顺序放到数组中;
image
def radix_sort(arr):
digit_index = 0 # 指示当前位数
digit_len = 1 # 最长位数
# 找出列表中最大的位数
while 10**digit_len < max(arr):
digit_len += 1
while digit_index < digit_len:
buckets =[[] for _ in range(10)] #初始化桶数组
for i in arr:
buckets[i//(10**digit_index) % 10].append(i) # 当前位上的数字
arr.clear()
for b in buckets: # 放回原序列
for i in b:
arr.append(i)
digit_index = digit_index + 1
return arr
arr = [12, 11, 13, 5, 0, 6, 7, 0, 12, 34, 54, 2, 3]
print(radix_sort(arr))
