基本排序算法

常用排序算法实现

更多的排序算法可以查看:https://en.wikipedia.org/wiki/Sorting_algorithm

冒泡排序

冒泡排序 是我们在大学里面最先接触的排序算法,它是一种稳定排序算法,但是平均的时间复杂度在 O(n^2),空间复杂度:O(1),虽然稳定但性能不好,下面是Python示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bubble_sort(items: list) -> list:
length = len(items)
if length < 1:
return items

for i in range(length):
exchange = False
for j in range(length - i - 1):
if items[j] > items[j+1]:
items[j], items[j+1] = items[j+1], items[j]
if not exchange:
exchange = True
if not exchange:
break
return items

归并排序

归并排序 是一种快速稳定的排序算法,时间复杂度:O(nlogn),空间复杂度:O(n),下面是 Python 示例:

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

def merge_sort(items: List[int]) -> List[int]:
recursion(items, 0, len(items) - 1)
return items

def recursion(items: List[int], low: int, high: int):
if low < high:
mid = low + (high - low) // 2
recursion(items, low, mid)
recursion(items, mid + 1, high)
merge(items, low, mid, high)


def merge(items: List[int], low: int, mid: int, high: int):
i, j = low, mid + 1
tmp = []
while i <= mid and j <= high:
if items[i] < items[j]:
tmp.append(items[i])
i += 1
else:
tmp.append(items[j])
j += 1
rest_start = i if i <= mid else j
rest_end = mid if i <= mid else high
tmp.extend(items[rest_start:rest_end + 1])
items[low:high+1] = tmp

快速排序

快速排序 是一种比较快的排序算法,时间复杂度平均是:O(nlogn),但它不稳定,最差情况下是:O(n^2),以下是Python示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quick_sort(items: List[int]) -> List[int]:
recursion(items, 0, len(items) - 1)
return items


def recursion(items: List[int], low: int, high: int):
if low < high:
k = randint(low, high)
items[k], items[low] = items[low], items[k]
point = partition(items, low, high)
recursion(items, low, point - 1)
recursion(items, point + 1, high)


def partition(items: List[int], low: int, high: int):
pivot = items[high]
i = low
for j in range(low, high):
if items[j] < pivot:
items[i], items[j] = items[j], items[i]
i += 1
items[i], items[high] = items[high], items[i]
return i

计数排序

时间复杂度O(n),空间复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from typing import List


def counting_sort(items: List[int]) -> List[int]:
length = len(items)
max_item = max(items)
bucket = [0] * (max_item + 1)

# 计数
for item in items:
bucket[item] += 1

# 累加
for i in range(1, max_item + 1):
bucket[i] = bucket[i - 1] + bucket[i]

# 排序
tmp = [0] * length
for i in range(length - 1, -1, -1):
index = bucket[items[i]] - 1
tmp[index] = items[i]
bucket[items[i]] -= 1

return tmp

堆排序

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
from random import randint
from typing import List


def sort(nums: List[int]):
length = len(nums)
build_heap(nums, length)
for i in range(length - 1, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
heapify(nums, i, 0)


def build_heap(nums: List[int], length: int):
for i in range((length - 2) >> 1, -1, -1):
heapify(nums, length, i)


def heapify(nums: List[int], length: int, i: int):
while True:
max_pos, left, right = i, 2 * i + 1, 2 * i + 2
if left < length and nums[left] > nums[max_pos]:
max_pos = left
if right < length and nums[right] > nums[max_pos]:
max_pos = right
if i == max_pos:
break
nums[i], nums[max_pos] = nums[max_pos], nums[i]
i = max_pos

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def insert_sort(items: list) -> list:
length = len(items)
if length < 1:
return items

for i in range(1, length):
value = items[i]
j = i - 1
while j >= 0:
if items[j] > value:
items[j+1] = items[j]
else:
break
j -= 1
items[j+1] = value
return items

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
def selection_sort(items: list) -> list:
length = len(items)
if length < 1:
return items
for i in range(length - 1):
min_index = i + 1
for j in range(i + 2, length):
if items[j] < items[min_index]:
min_index = j
if items[min_index] < items[i]:
items[i], items[min_index] = items[min_index], items[i]
return items