排序算法总结

1
sort_array = [3,1,5,4,6,9,8,2,7]

冒泡排序

算法描述

  • 若有N个元素需要排序, 则需要进行N轮遍历, 每轮遍历需要逐一比较相邻的两个元素大小, 大的往前冒泡(交换两者位置)
  • 每轮遍历都能确定一个元素的最终位置
  • 复杂度为O(N*2)
    -

实现代码

1
2
3
4
5
6
7
8
def bubble_sort(array):
print('before: {}'.format(array))
n = len(array)
for i in range(n):
for j in range(1,n-i):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
print('after: {}'.format(array))
1
2
3
4
bubble_sort(sort_array[:])
"""out"""
before: [3, 1, 5, 4, 6, 9, 8, 2, 7]
after: [1, 2, 3, 4, 5, 6, 7, 8, 9]

选择排序

算法描述

  • 不断的取当前未排序数组中的最小(最大)值放入已排序数据的末尾

实现代码

1
2
3
4
5
6
7
8
9
10
11
def select_sort(array):
print('before: {}'.format(array))
n = len(array)
for sorted_index in range(n-1): # sorted_index 为下一个最小值插入的位置
min_index = sorted_index # 最小元素索引
for j in range(sorted_index+1, n):
if array[min_index] > array[j]:
min_index = j
array[sorted_index], array[min_index] = array[min_index], array[sorted_index] # 将原先位置元素与最小值交换
print('after: {}'.format(array))
return array
1
2
3
4
select_sort(sort_array[:])
"""out"""
before: [3, 1, 5, 4, 6, 9, 8, 2, 7]
after: [1, 2, 3, 4, 5, 6, 7, 8, 9]

插入排序

算法描述

  • 逐一遍历未排序元素, 将其插入到已排序数组中的正确位置中
  • 默认第一个元素为已排序元素

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def insert_sort(array):
print('before: {}'.format(array))
n = len(array)
if n < 2:
return array
for i in range(1,n):
index = i - 1 # 待插入位置
tmp = array[i] # 待插入数字
while index >= 0 and tmp < array[index]:
array[index+1] = array[index] # index所在的值向后移动一位
index -= 1
array[index+1] = tmp # 将待插入数字插入到正确位置, 保证已排序数据有序
print('after {} --- {}'.format(tmp, array))
print('after: {}'.format(array))
return array
1
2
3
4
5
6
7
8
9
10
11
12
insert_sort(sort_array[:])
"""out"""
before: [3, 1, 5, 4, 6, 9, 8, 2, 7]
after 1 --- [1, 3, 5, 4, 6, 9, 8, 2, 7]
after 5 --- [1, 3, 5, 4, 6, 9, 8, 2, 7]
after 4 --- [1, 3, 4, 5, 6, 9, 8, 2, 7]
after 6 --- [1, 3, 4, 5, 6, 9, 8, 2, 7]
after 9 --- [1, 3, 4, 5, 6, 9, 8, 2, 7]
after 8 --- [1, 3, 4, 5, 6, 8, 9, 2, 7]
after 2 --- [1, 2, 3, 4, 5, 6, 8, 9, 7]
after 7 --- [1, 2, 3, 4, 5, 6, 7, 8, 9]
after: [1, 2, 3, 4, 5, 6, 7, 8, 9]

快速排序

算法描述

  • 随机取一个值为基准值
  • 小于该基准值的放在该基准值左边, 大于的放在右边
  • 分别对该基准值左右两边的数组递归做相同处理

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 快速排序
def quick_sort(array, left, right):
print('before: {}'.format(array))
if left >= right:
return array
key = array[left]
lp, rp = left, right
while lp < rp:
while array[lp] < key and lp < rp:
lp += 1
while array[rp] > key and lp < rp:
rp -= 1
array[lp], array[rp] = array[rp], array[lp]
print(' {} --- left {} lp {}'.format(array, array[left], array[lp]))
quick_sort(array, left, lp)
quick_sort(array, rp+1, right)
return array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
quick_sort(sort_array[:], 0, 8)
"""out"""
before: [3, 1, 5, 4, 6, 9, 8, 2, 7]
[2, 1, 3, 4, 6, 9, 8, 5, 7] --- left 2 lp 3
before: [2, 1, 3, 4, 6, 9, 8, 5, 7]
[1, 2, 3, 4, 6, 9, 8, 5, 7] --- left 1 lp 2
before: [1, 2, 3, 4, 6, 9, 8, 5, 7]
[1, 2, 3, 4, 6, 9, 8, 5, 7] --- left 1 lp 1
before: [1, 2, 3, 4, 6, 9, 8, 5, 7]
before: [1, 2, 3, 4, 6, 9, 8, 5, 7]
before: [1, 2, 3, 4, 6, 9, 8, 5, 7]
before: [1, 2, 3, 4, 6, 9, 8, 5, 7]
[1, 2, 3, 4, 6, 9, 8, 5, 7] --- left 4 lp 4
before: [1, 2, 3, 4, 6, 9, 8, 5, 7]
before: [1, 2, 3, 4, 6, 9, 8, 5, 7]
[1, 2, 3, 4, 5, 6, 8, 9, 7] --- left 5 lp 6
before: [1, 2, 3, 4, 5, 6, 8, 9, 7]
[1, 2, 3, 4, 5, 6, 8, 9, 7] --- left 5 lp 5
before: [1, 2, 3, 4, 5, 6, 8, 9, 7]
before: [1, 2, 3, 4, 5, 6, 8, 9, 7]
before: [1, 2, 3, 4, 5, 6, 8, 9, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9] --- left 7 lp 8
before: [1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9] --- left 7 lp 7
before: [1, 2, 3, 4, 5, 6, 7, 8, 9]
before: [1, 2, 3, 4, 5, 6, 7, 8, 9]
before: [1, 2, 3, 4, 5, 6, 7, 8, 9]

归并排序

算法描述

  • 递归拆分数组(如长度为8的数组拆成两个长度为四的数组 , 直到全部拆成长度为1的数组)
  • 将拆分后的数组递归两两合并,形成有序数组

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 归并排序
def merge_sort(array):
# 递归拆分数组
if len(array) <= 1:
return array
num = len(array) // 2
left = merge_sort(array[:num])
right = merge_sort(array[num:])
return merge(left, right)

def merge(left, right):
# 合并数组
lp = rp = 0
ret = []
while lp < len(left) and rp < len(right):
if left[lp] < right[rp]:
ret.append(left[lp])
lp += 1
else:
ret.append(right[rp])
rp += 1
ret += left[lp:]
ret += right[rp:]
return ret

希尔排序(Shell排序)

算法描述

  • 假设待排序序列长度为N, 则先按步长为(N/2)拆分数组, 并进行插入排序
  • 步长逐渐递减为原来的(1/2), 重复原先操作
  • 直到步长为1

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 希尔排序
def shell_sort(array):
n = len(array)
gap = n // 2
while gap > 0:
for i in range(n):
if i+gap < n:
tmp = array[i+gap] # 待插入元素
index = i + gap # 待插入位置
while index - gap >= 0 and tmp < array[index - gap]:
array[index] = array[index - gap]
index -= gap
array[index] = tmp
gap = gap // 2
return array

堆排序

复杂度分析

堆排序总共涉及三个函数

  • max_heapify(堆维护), 时间复杂度为O(lgn)

    因为一个具有n个元素的二叉堆, 层数为lg(n+1)(向上取整)或者为lgn+1(向下取整), 这边需要注意的是,虽然堆的层数是lgn+1, 但是遍历的层数是lgn, 因为每个叶子节点都是最大堆,无需进行调整, 因此时间复杂度为O(lgn)

  • build_max_heap(构建初始最大堆)非渐近准确可以当做O(nlgn), 渐近准确的为O(n),具体数学证明可以看算法导论
  • heap_sort(堆排序)时间复杂度为O(nlgn)

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# -*- coding: UTF-8 -*-


def max_heapify(arr, start, end):
"""
维护最大堆,本质上是从start向下遍历, 如果子节点大于父节点, 则父节点与子节点交换,
然后, 继续以该子节点为起点,向下调整
"""
while start < end:
left = start * 2 + 1
right = start * 2 + 2
if left < end and arr[left] > arr[start]:
largest = left
else:
largest = start
if right < end and arr[right] > arr[largest]:
largest = right
if largest != start:
arr[largest], arr[start] = arr[start], arr[largest]
start = largest
else:
break


def build_max_heap(arr):
"""构建初始最大堆, 只能确保首个元素为最大值"""
length = len(arr)
for x in range(length // 2 - 1, -1, -1):
max_heapify(arr, x, length)


def heap_sort(arr):
"""利用最大堆实现升序排序, 每次取走一个根节点,可以获得当前堆中的最大值, 因此取n次即可得到有序序列"""
length = len(arr)
build_max_heap(arr)
while length > 0:
max_heapify(arr, 0, length)
arr[0], arr[length - 1] = arr[length - 1], arr[0]
length -= 1
return arr

计数排序

算法描述

  • 非比较型算法, 稳定性算法
  • 通过统计小于等于当前元素个数,进行排序
  • 时间复杂度为O(n+k), 适用于k = O(n) 情况, 若k = O(n), 则时间复杂度为O(n)

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import Counter


def counting_sort(arr, k):
"""
计数排序: 非比较排序, 稳定
:param k: 表示数组中元素都是在0~k范围内
"""
ret = [0] * len(arr)
count = Counter(arr)
for x in range(1, k+1):
count[x] += count[x-1]
# 倒序遍历, 确保稳定
for y in range(len(arr)-1, -1, -1):
ret[count[arr[y]]] = arr[y]
count[arr[y]] -= 1
return ret

本文标题:排序算法总结

文章作者:定。

发布时间:2018年2月9日 - 14时02分

本文字数:7,078字

原始链接:http://cocofe.cn/2018/02/09/排序算法总结/

许可协议: Attribution-NonCommercial 4.0

转载请保留以上信息。