各大排序方法图解及Python代码实现

写在前面：整理了一下比较常用的几种排序方法的复杂度（以下所有代码实现的都是从小到大排序），并用Python进行了实现，所有代码都自测过，如果发现bug请及时留言。
下图引用链接：https://zh.wikipedia.org/wiki/排序算法

各大排序算法比较

• 均按从小到大排列
• k代表数值中的"数字"个数
• n代表数据规模
• m代表数据的最大值减最小值

插入排序(insertion sort)

插入排序的思想，以i为分界点，i前面的数都为有序的，找到合适的位置，将nums[i]插入到有序的数组中，下图给出了每一轮循环i前面数的变化。

插入排序示例图

def insertion_sort(nums):
    for i in range(1, len(nums)):
        val = nums[i]
        j = i-1
        while j >= 0:
            if nums[j] <= val:
                break
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = val
    return

选择排序(select sort)

选择排序和插入排序一个共同的思想是i前面的数都是有序的，不同的是选择排序每次都是选择i之后最小的数(绿色)和位置i上的数(黄色)进行交换。选择排序侧重于选择，插入排序侧重于插入。

选择排序示例图

def select_sort(nums):
    n = len(nums)
    for i in range(n):
        minIndex = i
        for j in range(i, n):
            if nums[minIndex] > nums[j]:
                minIndex = j
        if minIndex != i:
            nums[minIndex], nums[i] = nums[i], nums[minIndex]
    return

冒泡排序(bubble sort)

冒泡排序的思想是当前位置i上的数如果比前面的数小，就一直和前面的数交换，从下图可以看出“冒泡”这个词的意思。

冒泡排序示意图

# 代码实现的只是让小的数往前冒泡，当然也可以倒着来，让大的数往后冒泡
def bubble_sort(nums):
    n = len(nums)
    for i in range(n):
        for j in range(n-1, i, -1):
            if nums[j-1] > nums[j]:
                nums[j-1], nums[j] = nums[j], nums[j-1]
    return

合并排序(merge sort)

合并排序的思想是，每次进行两两合并，当然合并完之后是有序的，所以需要额外的空间来记录合并后的值，空间复杂度为O(n)，但是因为每次拆成了两部分，所以时间复杂度是O(nlogn)。

合并排序示例图

def merge_sort_merge(nums, begin, end):
    mid = (begin+end)//2
    nums1 = nums[begin:mid]
    nums2 = nums[mid:end]
    i1, i2, n1, n2 = 0, 0, len(nums1), len(nums2)
    for i in range(begin, end):
        if i1 >= n1 or i2 >= n2:
            nums[i:end] = nums1[i1:n1] if i1 < n1 else nums2[i2:n2]
            break
        if nums1[i1] < nums2[i2]:
            nums[i] = nums1[i1]
            i1 += 1
        else:
            nums[i] = nums2[i2]
            i2 += 1
    return

def merge_sort_sub(nums, begin, end):
    if begin >= end-1:
        return
    mid = (begin+end)//2
    merge_sort_sub(nums, begin, mid)
    merge_sort_sub(nums, mid, end)
    merge_sort_merge(nums, begin, end)
    return

def merge_sort(nums):
    merge_sort_sub(nums, 0, len(nums))
    return

快排(quick sort)

快排的基本思想简化一下就是：将第一个数放在合适的位置（即前面的数都小于该数，后面的数都大于该数），然后再分别处理前一半和后一半。下面给出了一个示例图，看着代码比较容易理解些。

快排序示例图

def partion(nums, begin, end):
    '''
    此处的partion方法用的是hoare_partion，因为hoare_partion比lomuto_partion快2倍，具体的区别参见：
    https://selfboot.cn/2016/09/01/lost_partition/，这个链接介绍partion介绍的特别清楚。
    '''
    i, j, val = begin, end - 1, nums[begin]
    while i < j:
        while i < j and nums[j] >= val: j -= 1
        nums[i] = nums[j]
        while i < j and nums[i] < val: i += 1
        nums[j] = nums[i]
    nums[i] = val
    return i

def quick_sort_sub(nums, begin, end):
    if begin >= end - 1:
        return
    index = partion(nums, begin, end)  #返回第一个数所在的合适的位置
    quick_sort_sub(nums, begin, index) #处理前一半
    quick_sort_sub(nums, index + 1, end) #处理后一半
    return

def quick_sort(nums):
    quick_sort_sub(nums, 0, len(nums))
    return

堆排序(heap sort)

总共用python做了三种实现，下面将分别介绍，前两种方法就不多做介绍了，第三种方法给出示例图。
方法一：利用了python自带的包heapq，代码简洁明了，空间复杂度O(n)

import heapq
def heap_sort(nums):
    tmp = []
    [heapq.heappush(tmp, val) for val in nums]
    for i in range(len(tmp)):
        nums[i] = heapq.heappop(tmp)
    return

方法二：自己首先实现了一个“堆”类class Heap，里面有各种堆的操作，空间复杂度O(n)
但是排序方法基本和方法一一模一样，代码简洁明了。

def heap_sort(nums):
    tmp = Heap(lambda x, y, a: a[x] > a[y]) #自己实现的堆
    for x in nums: tmp.append(x) #O(n*logn)
    for i in range(tmp.size()):
        nums[i] = tmp.pop()  #O(n*logn)
    return

# 以下是Heap类具体的实现代码
class Heap:
    def __init__(self, cmp):
        self.cmp = cmp  # 最小堆: cmp=lambda x, y, a: a[x] > a[y]，最大堆: cmp=lambda x, y, a: a[x] < a[y]
        self.heap = [None]  # index begins from 1
    
    def __swap__(self, x, y, a):
        a[x], a[y] = a[y], a[x]
    
    def size(self):
        return len(self.heap) - 1
    
    def top(self):
        return self.heap[1] if self.size() else None
    
    def append(self, x):
        self.heap.append(x)
        self.siftUp(self.size())
    
    def pop(self):
        if self.size() == 0: return None
        top, last = self.top(), self.heap.pop()
        if self.size():
            self.heap[1] = last
            self.siftDown(1)
        return top
    
    def siftUp(self, idx):
        while idx > 1 and self.cmp(idx/2, idx, self.heap):
            self.__swap__(idx/2, idx, self.heap)
            idx /= 2
        return
    
    def siftDown(self, idx):
        while idx*2 <= self.size():
            nidx = idx*2
            if nidx+1 <= self.size() and self.cmp(nidx, nidx+1, self.heap):
                nidx += 1
            if self.cmp(idx, nidx, self.heap):
                self.__swap__(idx, nidx, self.heap)
                idx = nidx
            else:
                break
        return

方法三：只为了堆排序写了两个子函数，即建堆和重置堆（参见如下示例图），空间复杂度O(1)。
和方法二比起来，不需要具体实现一个类，同时又能满足排序的要求，又不需要利用内置Python包。

堆排序示例图

def reset_heap(nums, n):
    i = 0
    while i < n:
        l, r = 2 * i + 1, 2 * i + 2
        if l >= n: break
        c = l
        if r < n and nums[c] < nums[r]: c = r
        if nums[c]>nums[i]: nums[i], nums[c] = nums[c], nums[i]
        i = c
    return

def build_heap(nums):
    i = (len(nums)-1)/2
    while i >= 0:
        j = i
        while j < len(nums):
            jl, jr = 2*j+1, 2*j+2
            if jl >= len(nums): break
            jc = jl
            if jr < len(nums) and nums[jr] > nums[jc]: jc = jr
            if nums[jc] <= nums[j]: break
            nums[jc], nums[j] = nums[j], nums[jc]
            j = jc
        i -= 1
    return

def heap_sort(nums):
    build_heap(nums)  #O(n)，构建一个最大堆，如果是从大到小排序，则构建一个最小堆
    n = len(nums)
    for i in range(n):
        nums[0], nums[n-i-1] = nums[n-i-1], nums[0] #看到这儿应该能理解为什么是构建最大堆了。
        reset_heap(nums, n-i-1)
    return

计数排序(count sort)

计数排序只能对整数进行排序，对其它非整数无法用该方法。
思想：开辟了一个新数组，记录每个数出现的次数；然后循环该新数组，即可得到排序结果。
换了一个例子，可以更直观的展示计数排序的特点，如下图所示。

计数排序示例图

def count_sort(nums):
    n, maxNum, minNum = len(nums), nums[0], nums[0]
    for i in range(n):
        maxNum = max(maxNum, nums[i])
        minNum = min(minNum, nums[i])
    c = [0] * (maxNum - minNum + 1)
    for i in range(n):
        c[nums[i] - minNum] += 1
    p = 0
    for i in range(len(c)):
        for j in range(c[i]):
            nums[p] = minNum + i
            p += 1
    return

bucket sort

• 设置一个定量的数组当作空桶；
• 遍历输入数据，将每个数插入桶内时进行插入排序；
• 从不是空的桶里把排好序的数据拼接起来。

def bucket_sort(nums):
    # step1.get the maximum and minimum number in the array
    maxNum, minNum = nums[0], nums[0]
    for val in nums:
        maxNum = max(maxNum, val)
        minNum = min(minNum, val)
    distance = (maxNum-minNum+10)//10
    # step2.sort
    bucket, n = [[] for _ in range(10)], len(nums)
    for i in range(n):
        index = (nums[i]-minNum) / distance
        bucket[index].append(nums[i])
        k = 0
        for j in range(len(bucket[index])-2, -1, -1):
            if bucket[index][j] > nums[i]:
                bucket[index][j+1] = bucket[index][j]
            else:
                k = j+1
                break
        bucket[index][k] = nums[i]
    k = 0
    for i in range(10):
        for val in bucket[i]:
            nums[k] = val
            k += 1
    return

基数排序(radix sort)

基数排序示例图

# 实现1：按照示例图的方式，直接开了一个字典记录对应位置的数。
def radix_sort(nums):
    # step1. get the max number in the array
    maxNum, n = nums[0], len(nums)
    for i in range(n):
        if nums[i] > maxNum:
            maxNum = nums[i]
    # step2. sort by exp
    exp = 1
    while maxNum / exp > 0:
        bucket = {0: [], 1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: [], 9: []}
        for val in nums:
            bucket[(val / exp) % 10].append(val)
        i = 0
        for r in range(10):
            for val in bucket[r]:
                nums[i] = val
                i += 1
        exp *= 10
    return

# 实现2：常见的实现方法
def radix_sort(nums):
    maxNum = nums[0]
    for val in nums:
        maxNum = max(maxNum, val)
    exp = 1
    while maxNum/exp > 0:
        bucket = [0]*10
        output = nums[:]
        for val in nums:
            bucket[(val/exp) % 10] += 1
        for i in range(1, 10):
            bucket[i] += bucket[i-1]
        for i in range(len(output)-1, -1, -1):
            r = (output[i]/exp) % 10
            bucket[r] -= 1
            nums[bucket[r]] = output[i]
        exp *= 10
    return