最后俩排序方法（归并排序 & 基数排序）

﹏ヽ暗。殇╰゛Y 2023-02-28 11:23 8阅读 0赞

--------------------

<table> 
 <tbody> 
 <tr> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:94pt;"> 排序方法 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:60pt;"> 稳定性 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:153pt;"> 时间复杂度 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:102pt;"> 空间复杂度 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:149pt;"> 元素最终位置 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:117pt;"> 初始影响 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:94pt;"> 直接插入 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:60pt;"> Y </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:153pt;"> 平均：O（n2） 基本有序O（n） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:102pt;"> O（1）哨位 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:149pt;"> 每趟无 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:117pt;"> 基本有序较好 适用规模小 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:94pt;"> 希尔 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:60pt;"> N </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:153pt;"> 下限：O(nlog2n) 上限：O（n2） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:102pt;"> O（1） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:149pt;"> 每趟无 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:117pt;"> 无影响 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:94pt;"> 冒泡 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:60pt;"> Y </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:153pt;"> 平均：O（n2） 最好：O（n） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:102pt;"> O（1） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:149pt;"> 每趟有最大或最小 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:117pt;"> 有序时最好 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:94pt;"> 快速 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:60pt;"> N </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:153pt;"> 平均：O（nlog2n） 最差：O（n2） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:102pt;"> O（log2n） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:149pt;"> 每趟有最大或最小 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:117pt;"> 有序时最坏 适用规模大 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:94pt;"> 直接选择 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:60pt;"> N </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:153pt;"> O（n2） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:102pt;"> O（1） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:149pt;"> 每趟有最大或最小 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:117pt;"> 无影响 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:94pt;"> 堆排序 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:60pt;"> N </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:153pt;"> O（nlog2n） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:102pt;"> O（1） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:149pt;"> 每趟有最大或最小 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:117pt;"> 无影响 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:94pt;"> 归并排序 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:60pt;"> Y </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:153pt;"> O（nlog2n） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:102pt;"> O（n） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:149pt;"> 每趟无 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:117pt;"> 无影响 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:94pt;"> 基数排序 </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:60pt;"> Y </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:153pt;"> O（d*n） </td> 
 <td style="border-color:#000000;text-align:center;vertical-align:middle;width:102pt;"> O（n+rd） </td> 
 <td style="border-color:#000000;vertical-align:middle;width:149pt;"> &nbsp; </td> 
 <td style="border-color:#000000;vertical-align:middle;width:117pt;"> &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

--------------------

# 归并排序 #

[https://www.runoob.com/python3/python-merge-sort.html][https_www.runoob.com_python3_python-merge-sort.html]

**是指将两个或两个以上的有序表合并成一个新的有序表。**

**利用归并的思想进行排序：**

*  **首先将整个表看成是****n****个有序子表，每个子表的长度为1；**
 *  **然后两两归并，得到****n/2****个长度为2的有序子表；**
 *  **然后再两两归并,直至得到一个长度为****n****的有序表为止。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

![20200721112632607.png][]

![20200721112646563.png][]

![20200721112653948.png][]

空间复杂度: O(n)          不能就地归并，需要一倍的辅助空间

时间复杂度: ![O(nlog\_2n)][O_nlog_2n]

[https://www.jianshu.com/p/3ad5373465fd][https_www.jianshu.com_p_3ad5373465fd]

def mergesort(seq):
 """归并排序"""
 if len(seq) <= 1:
 return seq
 mid = len(seq) // 2 # 将列表分成更小的两个列表
 # 分别对左右两个列表进行处理，分别返回两个排序好的列表
 left = mergesort(seq[:mid])
 right = mergesort(seq[mid:])
 # 对排序好的两个列表合并，产生一个新的排序好的列表
 return merge(left, right)
 
 
 def merge(left, right):
 """合并两个已排序好的列表，产生一个新的已排序好的列表"""
 result = [] # 新的已排序好的列表
 i = 0 # 下标
 j = 0
 # 对两个列表中的元素 两两对比。
 # 将最小的元素，放到result中，并对当前列表下标加1
 while i < len(left) and j < len(right):
 if left[i] <= right[j]:
 result.append(left[i])
 i += 1
 else:
 result.append(right[j])
 j += 1
 result += left[i:]
 result += right[j:]
 return result
 
 
 if __name__ == '__main__':
 seq = [5, 3, 0, 6, 1, 4]
 print('排序前：', seq)
 result = mergesort(seq)
 print('排序后：', result)

--------------------

# 多关键字排序与基数排序  #

[https://juejin.im/post/5ec9000f6fb9a047967326ac][https_juejin.im_post_5ec9000f6fb9a047967326ac]

**关键字按：由高到低** **/** **由低到高**  **排序**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

**示例：基数排序的过程演示**

**（****158,261,379,426,571,603,782,900,58,17,211,60,608,723****）**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

**排序结果****:** **(17,58,60,158,211,261,379,426,571,603,608,723,782,900)**

最低位优先法LSD:由键值的最右边开始

最高位优先法MSD:由键值的最左边开始

稳定性：稳定排序

时间复杂度：O(d\*n) -> O(n) ——  d是关键字个数

分配是O(n) ；收集是O(rd) ,rd是“基”；完成一趟分配\-收集就是O(n+rd)；那么时间复杂度是 O(d(n+rd))

# radix_sort 代码实现
    from typing import List
    
    
    def radix_sort(arr: List[int]):
        n = len(str(max(arr)))  # 记录最大值的位数
        for k in range(n):  # n轮排序
            # 每一轮生成10个列表
            bucket_list = [[] for i in range(10)]  # 因为每一位数字都是0~9，故建立10个桶
            for i in arr:
                # 按第k位放入到桶中
                bucket_list[i // (10 ** k) % 10].append(i)
            # 按当前桶的顺序重排列表
            arr = [j for i in bucket_list for j in i]
        return arr
    
    
    # 测试数据
    
    if __name__ == '__main__':
        import random
    
        random.seed(54)
        arr = [random.randint(0, 100) for _ in range(10)]
        print("原始数据：", arr)
        arr_new = radix_sort(arr)
        print("基数排序结果为：", arr_new)

[https_www.runoob.com_python3_python-merge-sort.html]: https://www.runoob.com/python3/python-merge-sort.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20230209/ae4c49f11a674ed9961d1befaee22efa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200721112621913.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5,size_16,color_FFFFFF,t_70
[20200721112632607.png]: https://img-blog.csdnimg.cn/20200721112632607.png
[20200721112646563.png]: https://img-blog.csdnimg.cn/20200721112646563.png
[20200721112653948.png]: https://img-blog.csdnimg.cn/20200721112653948.png
[O_nlog_2n]: https://private.codecogs.com/gif.latex?O%28nlog_2n%29
[https_www.jianshu.com_p_3ad5373465fd]: https://www.jianshu.com/p/3ad5373465fd
[https_juejin.im_post_5ec9000f6fb9a047967326ac]: https://juejin.im/post/5ec9000f6fb9a047967326ac
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020072111563614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200721115724538.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5,size_16,color_FFFFFF,t_70