十大排序算法

1. 选择排序

思路：首先从序列中选择最小元素，将它与序列的第一个元素交换位置，再从序列剩下的元素中选择最小的元素，将它与序列的第二个元素交换位置，不断进行这样的操作，直到将整个序列排序。

class Solution:
    def select_sort(self, arr):
        n = len(arr)
        for i in range(n - 1):
            idx = i
            for j in range(i + 1, n):
                if arr[idx] > arr[j]:
                    idx = j
            if idx != i:
                arr[idx], arr[i] = arr[i], arr[idx]
    
        return arr


if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前：{arr}")
    print(f"排序后：{Solution().select_sort(arr)}")

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

2. 冒泡排序

思路：从左到右不断交换序列相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧，持续每次对越来越少的元素重复上面的步骤。优化：在一轮循环中，如果没有发生交换，则说明序列已经是有序的，此时可以直接退出。

class Solution:
    def bubble_sort(self, arr):
        n = len(arr)
        for i in range(1, n):
            flag = False
            for j in range(n - i):
                if arr[j] > arr[j + 1]:
                    arr[j],  arr[j + 1] = arr[j + 1], arr[j]
                    flag = True
            if not flag:
                 break
        
        return arr

    
if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前: {arr}")
    print(f"排序后：{Solution().bubble_sort(arr)}")

排序前: [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

3. 插入排序

思路：插入元素时，在左侧已排序序列中从后到前扫描，找到相应位置并插入，插入到左侧已经排序的序列中，使得插入之后左侧序列依旧有序。

class Solution:
    def insert_sort(self, arr):
        n = len(arr)
        for i in range(1, n):
            for j in range(i, 0, -1):
                if arr[j] < arr[j - 1]:
                    arr[j], arr[j - 1] = arr[j - 1], arr[j]
        
        return arr


if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前：{arr}")
    print(f"排序后：{Solution().insert_sort(arr)}")

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

4. 希尔排序

思路：对于大规模的序列，插入排序很慢，因为它只能交换相邻元素，每次只能将逆序数量减1。希尔排序先将整个待排序的序列分割为若干个子序列分别进行直接插入排序，通过交换不相邻的元素，每次减少的逆序数量大于1。希尔排序使用插入排序对间隔h的序列进行排序，通过不断减少h，最后令h=1，可以使整个序列有序。

class Solution:
    def shell_sort(self, arr):
        n = len(arr)
        h = 1
        while h < n // 3:
            h = 3 * h + 1
        
        while h >= 1:
            for i in range(h, n):
                for j in range(i, h - 1, -h):
                    if arr[j] < arr[j - h]:
                        arr[j], arr[j - h] = arr[j - h], arr[j]
            h = h // 3
        
        return arr

if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前：{arr}")
    print(f"排序后：{Solution().shell_sort(arr)}")
                    

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

5. 归并排序

思路：归并排序采用的是分治法，即将序列分为两部分，分别进行排序，然后归并起来。首先申请空间用来存放合并后的序列，其大小为两个已排序序列之和，然后设定两个指针，分别指向为两个已排序序列的起始位置，比较两个指针所指向的元素，选择相对较小的元素存入合并空间，并移动指针到下一个位置，重复上述操作直到某一指针到达序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。

class Solution:
    def merge_sort(self, arr):
        n = len(arr)
        if n < 2:
            return arr
        mid_idx = n // 2
        left, right = arr[:mid_idx], arr[mid_idx:]
        
        return self.merge(self.merge_sort(left), self.merge_sort(right))
    
    def merge(self, left, right):
        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
        
        
if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前：{arr}")
    print(f"排序后：{Solution().merge_sort(arr)}")

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

6. 快速排序

思路：快速排序通过从数列中挑出一个元素作为基准，将序列分为两个子序列，左子序列所有元素小于等于切分元素，右子序列所有元素大于等于切分元素，然后再将这两个子序列切分排序重复上述操作，最终得到排序好的序列。

class Solution:
    def quick_sort(self, arr, left_idx, right_idx):
        if left_idx < right_idx:
            partition_idx = self.partition(arr, left_idx, right_idx)
            self.quick_sort(arr, left_idx, partition_idx - 1)
            self.quick_sort(arr, partition_idx + 1, right_idx)
    
        return arr
    
    def partition(self, arr, left_idx, right_idx):
        pivot = arr[right_idx]
        i = left_idx - 1
        for j in range(left_idx, right_idx):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[right_idx] = arr[right_idx], arr[i + 1]
        
        return i + 1

    
if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前：{arr}")
    print(f"排序后：{Solution().quick_sort(arr, 0, len(arr) - 1)}")
    

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

7. 堆排序

思路：利用堆这种数据结构所设计的一种排序算法，堆是一棵完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）其父节点，即大顶堆（小顶堆）。把最大元素和当前堆中序列的最后一个元素交换位置，并且不删除它。

class Solution:
    def __init__(self, arr):
        self.length = len(arr)
        self.build_max_heap(arr)
    
    def build_max_heap(self, arr):
        for i in range(self.length // 2, -1, -1):
            self.heapify(arr, i)
    
    def heapify(self, arr, i):
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i
        if left < self.length and arr[left] > arr[largest]:
            largest = left
        if right < self.length and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            self.heapify(arr, largest)
    
    def heap_sort(self, arr):
        for i in range(self.length - 1, 0, -1):
            arr[0], arr[i] = arr[i], arr[0]
            self.length -= 1
            self.heapify(arr, 0)
        
        return arr


if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前：{arr}")
    print(f"排序后：{Solution(arr).heap_sort(arr)}")
    

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

8. 计数排序

思路：核心在于将输入的数据值转化为键存储在额外开辟的数组空间，先找出待排序数组中最大和最小的元素，统计数组中每个值为i的元素出现的次数，存入数组的第i项，对所有的计数累加，反向填充目标数组，将每个元素i放在新数组的第i项，每放一个元素就将对应位置减去1。

class Solution:
    def counting_sort(self, arr):
        max_value = max(arr)
        bucket = [0] * (max_value + 1)
        sort_idx = 0
        n = len(arr)
        for i in range(n):
            if not bucket[arr[i]]:
                bucket[arr[i]] = 0
            bucket[arr[i]] += 1 
        for j in range(max_value + 1):
            while bucket[j] > 0:
                arr[sort_idx] = j
                sort_idx += 1
                bucket[j] -= 1
        
        return arr
    

if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前：{arr}")
    print(f"排序后：{Solution().counting_sort(arr)}")

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

9. 桶排序

思路：桶排序是计数排序的升级版，利用了函数的映射关系。需要注意，在额外空间充足的情况下，尽量增大桶的数量，尽量使用映射函数能够将n个数据均匀的分配到k个桶中。

元素分布在桶中：

元素在每个桶中排序:

class Solution:
    def bucket_sort(self, arr):
        max_value = max(arr)
        bucket = {i: [] for i in range(max_value + 1)}
        n = len(arr)
        for i in range(n):
            num = arr[i]
            bucket[num].append(num)
        arr = []
        for i in range(max_value + 1):
            if bucket[i]:
                arr += sorted(bucket[i])
        
        return arr

    
if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前：{arr}")
    print(f"排序后：{Solution().bucket_sort(arr)}")
    

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

10. 基数排序

思路：将整数按位数切割成不同的数字，然后按每个位数分别比较。

class Solution:
    def radix_sort(self, arr):
        max_value = max(arr)
        iter_cnt = len(str(max_value))
        for i in range(iter_cnt):
            bucket = [[] for _ in range(10)]
            for n in arr:
                idx = (n // 10 ** i) % 10
                bucket[idx].append(n)
            arr.clear()
            for b in bucket:
                arr += b
    
        return arr

if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(f"排序前：{arr}")
    print(f"排序后：{Solution().radix_sort(arr)}")

排序前：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

11. 小结

排序算法	稳定性	时间复杂度	空间复杂度	备注
选择排序	×	N^2	1
冒泡排序	√	N^2	1
插入排序	√	N^2	1	时间复杂度和初始顺序有关
希尔排序	×	NlogN	1	改进版插入排序
归并排序	√	NlogN	N
快速排序	×	NlogN	logN
堆排序	×	NlogN	1	无法利用局部性原理
计数排序	√	n + k	k
桶排序	√	n + k	n + k
基数排序	√	n x k	n + k

参考文章

本文是笔者通过下列网站学习排序算法的记录，有部分修改和补充，转载请注明出处，并附带下面链接。

1. 【CS-Notes】
2. 【菜鸟教程排序算法】