常见排序算法 Python实现

Bubble Sort – 冒泡排序

持续比较相邻的两个元素,大的挪到后面,因此大的会逐渐的挪到后面,因此称冒泡

冒泡排序图示

def bubble_sort(arr):
length = len(arr)
for i in range(length):
for j in range(1, length - i):
if arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
return arr

复杂度分析:时间复杂度为O(n^2), 空间复杂度为O(1)

Selection Sort – 选择排序

不断选择剩余数组中最小的元素并和剩余数组的第一个位置交换

选择排序图示

def selection_sort(arr):
length = len(arr)
for i in range(length):
idx = i
for j in range(i + 1, length):
if arr[idx] > arr[j]:
idx = j
arr[i], arr[idx] = arr[idx], arr[i]
return arr

复杂度分析:时间复杂度为O(n^2), 空间复杂度为O(1)

Insertion Sort – 插入排序

对于后面未排序的元素,对前面已排序的元素从后往前扫描找到相应位置插入

插入排序图示

def insert_sort(arr):
for i, item in enumerate(arr):
idx = i
while idx > 0 and arr[idx - 1] > item:
arr[idx - 1], arr[idx] = arr[idx], arr[idx - 1]
idx -= 1
return arr

复杂度分析:时间复杂度为O(n^2), 空间复杂度为O(1)

Shell Sort – 希尔排序

希尔排序实质上是分组插入排序,基本思路是:
设置一个步长,根据步长把数组分成几组,分别对每组进行插入排序,当步长为1时,希尔排序就变成了插入排序(因为只有一个分组)

例如:[3, 1, 23, 42, 23, 0, -1, 20], 设置步长3

# 对每列分别进行插入排序
3 1 23
43 23 0
-1 20

希尔排序

def shell_sort(arr):
n = len(arr)
gap = n / 2
while gap > 0:
for i in range(gap, n):
tmp = arr[i]
j = i
while j >= gap and arr[j - gap] > tmp:
arr[j - gap], arr[j] = arr[j], arr[j - gap]
j -= gap
gap = gap / 2
return arr

复杂度分析:时间复杂度为O(n^2), 空间复杂度为O(1)

Merge Sort – 归并排序

将两个有序的数组合并为一个大的有序数组,通常使用递归的做法,是典型的分治思想的应用

归并排序

def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) >> 1
a = merge_sort(arr[:mid])
b = merge_sort(arr[mid:])
return mergeSortedArray(a, b)
def mergeSortedArray(a, b):
c = []
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] < b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
c += a[i:]
c += b[j:]
return c

复杂度分析:时间复杂度为O(nlogn), 空间复杂度为O(n)

Quick Sort – 快速排序

选择一个基址,将所有比基址小的元素置于左边,大的置于右边,递归的调用切分过程

快速排序图示

def qSort(arr, lower, upper):
if lower >= upper:
return
pivot = arr[lower]
left, right = lower + 1, upper
while left <= right:
while left <= right and arr[left] < pivot:
left += 1
while left <= right and arr[right] >= pivot:
right -= 1
if left > right:
break
arr[left], arr[right] = arr[right], arr[left]
arr[lower], arr[right] = arr[right], arr[lower]
qSort(arr, lower, right - 1)
qSort(arr, right + 1, upper)

复杂度分析:时间复杂度O(nlogn), 空间复杂度O(logn)

Heap Sort – 堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

步骤:

  1. 创建最大堆:将数组的所有数据进行排序,使其成为最大堆
  2. 堆排序:移除位于第一个数据的根结点,剩余的元素做最大堆调整

下图是一个创建最大堆的图示:

创建最大堆

动态图:
堆排序

def heap_sort(lst):
n = len(lst)
first = int(n/2 - 1) #最后一个非叶子节点
for start in range(first, -1, -1):
shift_down(lst, start, n - 1)
for end in range(n-1, 0, -1):
lst[0], lst[end] = lst[end], lst[0]
shift_down(lst, 0, end - 1)
return lst
def shift_down(lst, start, end):
root = start
while True:
child = 2 * root + 1
if child > end: break
if child + 1 <= end and lst[child] < lst[child + 1]:
child += 1
if lst[root] < lst[child]:
lst[root], lst[child] = lst[child], lst[root]
root = child
else: break

复杂度分析:时间复杂度O(nlogn), 空间复杂度O(1)

总结

对比

坚持原创技术分享