排序算法分为 内部排序(只使用内存)和 外部排序(内存和外部存储一起混合使用)。
内部排序:

  • 交换排序
    • 冒泡排序
    • 快速排序
  • 插入排序:
    • 直接插入排序
    • 希尔拍序
  • 选择排序
    • 简单选择排序
    • 堆排序
  • 归并排序
  • 基数排序

一. 交换排序

1.1 冒泡排序

Bubble Sort

  • 比较相邻的元素,如果第一个比第二个大,就交换它们两个
  • 对每一对相邻元素同样的步骤,从开始的第一对到结尾的最后一对
  • 针对每一个相邻元素做同样的操作,除了最后一个
  • 重复上面的步骤,直到没有任何一个数字需要比较

动画演示

冒泡排序动画

代码实现

1
2
3
4
5
6
7
8
9
def bubble_sort(arr):
n = len(arr)
if n < 2:
return arr
for i in range(1, n):
for j in range(n - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

性能表现

平均时间复杂度:O(n^2)
空间复杂度: O(1)
稳定性:稳定

1.2 快速排序

Quick Sort

  • 从数组中选取一个元素作为基准值(pivot)
  • 将数组分成小于和大于基准值的两个子数组
  • 递归两个子数组

动画演示

快速排序动画

代码实现

1
2
3
4
5
6
7
8
9
def quick_sort(arr):
n = len(arr)
if n < 2:
return arr
else:
pivot = arr[0]
sub_less = [i for i in arr[1:] if i <= pivot]
sub_great = [j for j in arr[1:] if j > pivot]
return quick_sort(sub_less) + [pivot] + quick_sort(sub_great)

性能表现
平均时间复杂度:O(nlogn)
空间复杂度:O(logn)
稳定性:不稳定(速度和基准值有关)

二. 交换排序

2.1 简单插入排序

  • 从第一个元素开始,认为该元素已经被排序
  • 取出下一个元素,在已经排好的元素序列中从后向前扫描
  • 如果该元素(已排序)大于新的元素,将该元素向后移动一个位置
  • 重复步骤三,直到找到已排序的元素小于或者等于新的元素的位置
  • 将新的元素插入到该元素位置的后面
  • 重复步骤2~5

简单排序操作n-1轮,每一轮将一个元素插入到已经排好的序列里面。开始时,默认第一个元素时排序好的,将剩余的n-1个元素逐个插入。

动画演示

简单插入排序动画

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def inser_sort(arr):
n = len(arr)

if n < 2:
return arr

for i in range(1, n):
target, pre_index = arr[i], i - 1
while pre_index >= 0 and target < arr[pre_index]:
arr[pre_index + 1] = arr[pre_index]
pre_index -= 1
arr[pre_index + 1] = target

return arr

性能表现
平均时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:稳定

2.2 希尔排序

先将需要排序的序列的一组按照某个增量d(n/2,n为要排序的序列的个数)分成若干组子序列,每组中记录下标相差d,对每组中的全部元素执行直接插入排序,然后再使用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序,,继续不断缩小增量直到为1,最后使用直接插入排序完后排序。

演示动画

希尔排序动画

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def shell_sort(arr):
n = len(arr)
if n < 2:
return arr

step = 1
while step < n // 3:
# 动态定义间隔,为了保证可以缩小到1而不是0,所以加1
step = 3 * step + 1

while step > 0:
for i in range(step, n):
target, pre_index = arr[i], i - step
while pre_index >= 0 and target < arr[pre_index]:
arr[pre_index + step] = arr[pre_index]
pre_index -= step
step //= 3

return arr

性能表现
平均时间复杂度:O(n^1.3)
空间复杂度:O(1)
稳定性:不稳定