基本排序算法

发表于 | 分类于 |

冒泡排序

稳定排序, 时间复杂度: O(N^2)

冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序，它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 二次遍历时，第二大的元素就被排列在最大元素之前。N次遍历整个数列都有序。

1
2
3
4
5
6
7
8
9
def bubble_sort(lists):
  cnt = len(lists)
  for i in range(cnt):
    # 比较序列递减
    for j in range(1, cnt-i):
      if lists[j-1] > lists[j]:
        #swap
        lists[j-1], lists[j] = lists[j], lists[j-1]
  return lists

选择排序

稳定排序, 时间复杂度: O(N^2)

选择排序(Selection sort)是一种简单直观的排序算法，基本思想是：首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

1
2
3
4
5
6
7
8
9
def select_sort(lists):
  cnt = len(lists)
  for i in range(cnt):
    # 比较序列递减
    for j in range(i+1, cnt):
      if lists[i] > lists[j]:
        #swap
        lists[i], lists[j] = lists[j], lists[i]
  return lists

直接插入排序

稳定排序, 时间复杂度: O(N^2)

直接插入排序(Straight Insertion Sort)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程

  • 数据后移
1
2
3
4
5
6
7
8
9
def insert_sort(lists):
  for i in range(1, len(lists)):
    j = i-1
    tmp = lists[i]
    while lists[j]>tmp and j>=0:
      lists[j+1] = lists[j]
      j -= 1
    lists[j+1] = tmp
  return lists
  • 数据交换
1
2
3
4
5
6
7
8
def insert_sort(lists):
  for i in range(1, len(lists)):
    j = i-1
    while lists[j]>lists[j+1] and j>=0:
      # swap
      lists[j+1], lists[j] = lists[j], lists[j+1]
      j -= 1
  return lists

希尔排序

不稳定排序， 时间复杂度: O(N^(3/2))

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
def shell_sort(lists):
  gap = len(lists) / 2
  while gap > 0:
    for i in range(gap, len(lists)):
      # 同组直接插入排序
      j = i - gap
      while lists[j] > lists[j+gap] and j>=0:
        # swap
        lists[j+gap], lists[j] = lists[j], lists[j+gap]
        j -= gap
    gap /= 2
  return lists

归并排序

稳定排序, 时间复杂度: O(NlogN)

将两个的有序数列合并成一个有序数列，我们称之为”归并“。
归并排序(Merge Sort)就是利用归并思想对数列进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge(left, right):
  res = []
  i, j = 0, 0
  while i<len(left) and j<len(right):
    if left[i]<right[j]:
      res.append(left[i])
      i += 1
    else:
      res.append(right[j])
      j += 1
  res.extend(left[i:])
  res.extend(right[j:])
  return res

def merge_sort(lists):
  lens = len(lists)
  if lens <= 1:
    return lists
  num = lens / 2
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)

快速排序

不稳定排序，时间复杂度: O(NlogN)

快速排序(Quick Sort)使用分治法策略，它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流程：
(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
(3) 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def quick_sort(lists, l, r):
  if l >= r:
    return lists

  key = lists[l]
  low = l
  high = r
  while l < r:
    while l<r and lists[r] >= key:
      r -= 1
    lists[l] = lists[r]
    while l<r and lists[l] < key:
      l += 1
    lists[r] = lists[l]

  lists[l] = key
  quick_sort(lists, low, l-1)
  quick_sort(lists, l+1, high)
  return lists

基数排序

稳定排序, 时间复杂度: O(N)

基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

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


def radix_sort(lists, radix=10):
    k = int(math.ceil(math.log(max(lists), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(k):
        for j in lists:
            bucket[j/(radix**(i)) % radix].append(j)
        del lists[:]
        for z in bucket:
            lists.extend(z)
            del z[:]
    return lists

堆排序

不稳定排序，时间复杂度: O(NlogN)

堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。最大堆通常被用来进行”升序”排序，而最小堆通常被用来进行”降序”排序。

最大堆进行升序排序的基本思想：
① 初始化堆：将数列a[1…n]构造成最大堆。
② 交换数据：将a[1]和a[n]交换，使a[n]是a[1…n]中的最大值；然后将a[1…n-1]重新调整为最大堆。 接着，将a[1]和a[n-1]交换，使a[n-1]是a[1…n-1]中的最大值；然后将a[1…n-2]重新调整为最大值。 依次类推，直到整个数列都是有序的。

“数组实现的二叉堆的性质”,在第一个元素的索引为 0 的情形中：
性质一：索引为i的左孩子的索引是 (2i+1);
性质二：索引为i的左孩子的索引是 (2i+2);
性质三：索引为i的父结点的索引是 floor((i-1)/2);

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 adjust_heap(lists, i, size):
  lchild = 2 * i + 1
  rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild
    if max != i:
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size)
 
def build_heap(lists, size):
  for i in range(size/2-1, -1, -1):
    adjust_heap(lists, i, size)
 
def heap_sort(lists):
  size = len(lists)
  build_heap(lists, size)
  for i in range(size-1, -1, -1):
    lists[0], lists[i] = lists[i], lists[0]
    adjust_heap(lists, 0, i)
  return lists