常用的排序算法

最近在leetcode上刷题,想回顾一下计算机编程的基本功排序。常用的排序算法(内部排序),按大类分可分为以下几种:插入排序、交换排序、选择排序、归并排序和计数排序五大类。下面用python代码简单实现一下这几种排序算法。

插入排序

插入排序(Insertion Sort)比较简单直观,原理是将为排序数据,在已排序序列中从后往前扫描,找到相应位置插入。

直接插入排序(Straight Insertion Sort)

1
2
3
4
5
6
7
8
def insertion_sort(nums):
for i in range(1, len(nums)):
j, key = i - 1, nums[i]
while j >= 0 and key < nums[j]:
nums[j+1] = nums[j]
j = j - 1

nums[j+1] = key

其他插入排序

交换排序

交换排序也是一种非常基础的算法,主要包含冒泡排序和快速排序。

冒泡排序(Bubble Sort)

1
2
3
4
5
6
7
8
9
10
def bubble_sort(nums):
for i in range(0, len(nums)-1):
swapped = False
for j in range(0, len(nums)-1-i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
swapped = True
if not swapped:
break
return nums

快速排序(Quick Sort)

快速排序,又称分区交换排序,简称快排,是对冒泡排序的一种改进。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def quick_sort(nums, low, high):
if low >= high: return

pivot = nums[low] # 选数列第一个元素作为"基准"
i, j = low, high
while i < j:
while i < j and nums[j] >= pivot:
j = j - 1
nums[i] = nums[j]

while i < j and nums[i] <= pivot:
i = i + 1
nums[j] = nums[i]
nums[i] = pivot

quick_sort(nums, low, i-1)
quick_sort(nums, i+1, high)

选择排序

堆排序(Heap Sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def heap_sort(nums):
# 堆调整
def max_heapify(nums, i, length):
parent = i
child = 2 * i + 1
if child >= length:
return
if child + 1 < length and nums[child] < nums[child+1]:
child += 1
if nums[parent] < nums[child]:
nums[parent], nums[child] = nums[child], nums[parent]
max_heapify(nums, child, length)

# 初始化,构造大顶堆
for i in range(len(nums) // 2 - 1, -1, -1):
max_heapify(nums, i, len(nums))

# 堆排序
for j in range(len(nums) - 1, 0, -1):
nums[0], nums[j] = nums[j], nums[0]
max_heapify(nums, 0, j)

归并排序(Merge Sort)

快速排序虽然排序效率高,但是不稳定,时间复杂度介于O(nlogn)跟O(n2)之间。
而归并排序可以稳定在O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def mergeSort(nums):
if len(nums) == 1:
return nums

mid = len(nums) // 2
left = mergeSort(nums[:mid])
right = mergeSort(nums[mid:])
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if left:
result += left
if right:
result += right
return result

参考

  1. 《数据结构(C语言版)》——严蔚敏、吴伟民
  2. https://zh.wikipedia.org/wiki/快速排序
  3. https://blog.csdn.net/wthfeng/article/details/78037228