排序算法

Posted on | In | Visitors

排序算法总结（包括冒泡排序、选择排序、插入排序、归并排序、堆排序、计数排序、基数排序和快速排序等）。

冒泡排序（Bubble Sort）

重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。是==稳定==的排序方法。

1
2
3
4
5
6
def bubble_sort(a):
  i = j = 0
  for i in range(len(a) - 1):
    for j in range(len(a) - i - 1):
      if a[j] > a[j + 1]:
        a[j], a[j+1] = a[j+1], a[j]

选择排序（Selection Sort）

工作原理：第一次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是==不稳定==的排序方法。

1
2
3
4
5
6
7
8
9
def selection_sort(a):
  i = j = 0
  for i in range(len(a) - 1):
    min_idx = i
    for j in range(i + 1, len(a)):
      if a[j] < a[min_idx]:
        min_idx = j
    if min_idx != i:
      a[i], a[min_idx] = a[min_idx], a[i]

插入排序（Insertion Sort）

如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法，插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。

直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。是==稳定==的排序方法。

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

二分插入排序

将直接插入排序中寻找a[i]的插入位置的方法改为采用二分比较，即可得到二分插入排序算法。先查找，再后移。是稳定的排序算法，时间复杂度 \(O(n^2)\)。

希尔排序（Shell’s Sort）

又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是==非稳定排序算法==。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。多次插入排序。时间复杂度 \(O(n^{1.3\text{-}2})\)。

asdad

希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。

排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。

1
2
3
4
5
6
7
8
9
10
11
def shell_sort(a):
  gap = len(a) // 2
  while gap >= 1:
    for i in range(gap, len(a)):
      tmp, j = a[i], i - gap
      while j >= 0 and a[j] > tmp:
        a[j+gap] = a[j]
        j -= gap
      if j != i - gap:
        a[j+gap] = tmp
    gap //= 2

归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序是==稳定==的排序。时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def merge_sort(a):
  if len(a) <= 1:
    return a
  mid = len(a) // 2
  left = merge_sort(a[:mid])
  right = merge_sort(a[mid:])
  
  l = r = 0
  result = []
  while l < len(left) and r < len(right):
    if left[l] <= right[r]:
      result.append(left[l])
      l += 1
    else:
      result.append(right[r])
      r += 1
  result += left[l:]
  result += right[r:]
  return result

逆序对计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def merge_sort_and_count(a):
  if len(a) <= 1:
    return a, 0
  mid = len(a) // 2
  left, cnt_l = merge_sort_and_count(a[:mid])
  right, cnt_r = merge_sort_and_count(a[mid:])
  count = cnt_l + cnt_r
  
  l = r = 0
  result = []
  while l < len(left) and r < len(right):
    if left[l] <= right[r]:
      result.append(left[l])
      l += 1
    else:
      result.append(right[r])
      r += 1
      count += len(left) - l  # 当右半部分的元素先于左半部分元素进入有序列表时，逆序对数量增加左半部分剩余的元素数
  result += left[l:]
  result += right[r:]
  return result, count

堆排序（Heap Sort）

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

基本思想：移除位在第一个数据的根节点，并做最大堆调整的递归运算。堆排序==不稳定==。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def max_heapify(a, start, end):
  root = start
  while True:
    child = root * 2 + 1  # 左孩子
    if child > end:   # 左孩子下标比最后一个大，结束
      break
    if child + 1 <= end and a[child] < a[child+1]:  # 始终记录较大的子结点下标
      child += 1
    if a[root] < a[child]:  # 父结点小于子结点直接换位置，并更新父结点
      a[root], a[child] = a[child], a[root]
      root = child
    else:
      break
      
def heap_sort(a):
  root = len(a) // 2 - 1  # 从最后一个父结点开始调整，自下向上
  for i in range(root, -1, -1):
    max_heapify(a, i, len(a) - 1)
  for i in range(len(a) - 1, -1, -1):
    a[0], a[i] = a[i], a[0]   # a[0]为当前堆的最大元素，与最后一个元素交换
    max_heapify(a, 0, i - 1)  # 重新对剩下的元素调整

计数排序（Counting Sort）

计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为\(Ο(n+k)\)（其中 $k$ 是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当 $O(k)>O(nlog(n))$ 的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是 $O(nlog(n))$， 如归并排序，堆排序）。计数排序算法是一个==稳定==的排序算法。

1
2
3
4
5
6
7
8
9
10
11
def count_sort(a, k):
  c = [0] * k
  result = [None] * len(a)
  for x in a:
    c[x] += 1a
  for i in range(1, k):
    c[i] += c[i-1]
  for i in range(len(a)-1, -1, -1):
    c[a[i]] -= 1
    result[c[a[i]]] = a[i]
  return result

基数排序（Radix Sort）

最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。

最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

基数排序假设输入是由一个小范围内的整数构成，基数排序是==稳定==的。时间复杂度为 \(O(d(n+radix))\)，其中，一趟分配时间复杂度为 \(O(n)\)，一趟收集的复杂度为 \(O(radix)\)，共进行 \(d\) 趟分配和收集。

以LSD为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

第一步

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

1
2
3
4
5
6
7
8
9
10
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

第二步

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

1
2
3
4
5
6
7
8
9
10
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import math

def radix_sort(a, radix=10):
  # 基数为10
  k = math.ceil(math.log(max(a), radix))  # 计算 a 中最大数的位数
  buckets = [[] for _ in range(radix)]  # radix 个桶
  for i in range(1, k+1):
    for val in a:
      idx = val % (radix ** i) // (radix ** (i-1))
      buckets[idx].append(val)
    a.clear()
    for b in buckets:
      a.extend(b)
      b.clear()

桶排序（Bucket Sort）

工作原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是==稳定==的。

快速排序（Quick Sort）

基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序==不稳定==。

1
2
3
4
5
6
7
8
9
10
def quick_sort(a):
  if len(a) <= 1:
    return a
  left, right = [], []
  for val in a[1:]:
    if val < a[0]:
      left.append(val)
    else:
      right.append(val)
  return quick_sort(left) + [a[0]] + quick_sort(right)

快速排序计算逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
def quick_sort_and_count(a):
  if len(a) <= 1:
    return a, 0
  count, left, right = 0, [], []
  for val in a[1:]:
    if val < a[0]:
      left.append(val)
      count += len(right) + 1
    else:
      right.append(val)
  left, count_l = quick_sort_and_count(left)
  right, count_r = quick_sort_and_count(right)
  return left + [a[0]] + right, count + count_l + count_r
此时不赞何时赞！