常用的排序算法

最近在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
def bubble_sort(nums):
for i in range(0, len(nums)-1):
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]

快速排序(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)

参考

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