排序-蓝桥杯

迷南。 2023-09-24 17:49 64阅读 0赞

# **一、排序算法** #

*  基于比较的低效算法:

选择排序、插入排序、冒泡排序。时间复杂度O(n2)。

*  基于比较的高效算法:

归并排序、快速排序、堆排序。时间复杂度O(nlogn)。

*  基于数值划分的高效算法:

计数排序、基数排序、桶排序。时间复杂度O(n)。

# **二、sort()函数和sorted()函数** #

## **1.sort()和sorted()的区别** ##

*  sort()是应用在list上的方法；在原列表上排序。

*  sorted()可以对所有可迭代的对象进行排序操作；产生一个新的列表，不改变原列表。

*  实例对比如下：

![04875827c55d4fa5802057d5dd7f6f21.png][]

![51085d33f6ed4667bba808ba201caf6a.png][]

## **2.细说sorted()函数** ##

![4045c2a95cdf4b818fd60079b7980197.png][]

*  语法：

sorted(iterable,key=None,reverse=False)

*  参数说明:

1.  iterable:可迭代对象。

1.  key:用来进行比较的元素，只有一个参数，具体的函数的参数取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。

1.  reverse:排序规则，reverse = True 降序，reverse = False 升序(默认)

1.  返回值:重新排序的列表。

*  实例：

![3543ae42f74242b58bf876f04657279c.png][]

## **3.部分排序** ##

sort()不能在一部分上做排序，只能整体排序。

sorted()可以部分排序，但是不能在原数据上排序。

![22be553f0ff7401c8e3c778673000f0b.png][]

## **4.函数的应用实例1** ##

![6f4fe989b78940418f24956d2234c2ac.png][]

![0f0bb9a84ec241d5a4bdeda90f4faf6d.png][]

补充join函数

语法：

'sep'.join(sep\_object)

参数说明：

sep：分割符，可为“ ，、；”等。

sep\_object：分割对象，可为字符串、以及储存字符串的元组、列表、字典。

作用：

连接任意数量的字符串（包括要连接的元素字符串、元组、列表、字典），用新的目标分隔符连接，返回新的字符串。

## **6.**函数的应用实例2 ##

![3dcee97469ec41f2bd45eceaa56a48ba.png][]

![c5c252e824154801a9284134b969152d.png][]

### **（1）超时做法** ###

![6884f160c8964be7a16f6ce9ee54aacd.png][]

### **（2）巧妙做法** ###

![f5e0cf09913c4169aa3d995500dbe3ee.png][]

## **7.**函数的应用实例3 ##

![90baad4c52114affaa0a7225b58e8073.png][]

![0917b8c62c864286b39898b361956c3d.png][]

![8a1dfe1c1d454f9987b9375c1dfc295d.png][]

# **二、结构体排序** #

**sort()和sorted()都能对结构体排序**

## **1.简介写法** ##

s.sort(key=lambda x:x[i],reverse=True)

a=sorted(s,key=lambda x:x[i],reverse=True)

## **2.自己写比较函数** ##

def cmp():
        s.sort(key=functools.cmp_to_key(cmp))
        a=sorted(s,key=functools.cmp_to_key(cmp))

## **3.经典例题1** ##

![2ec73ee231594bca9441f29ac8a6fa2f.png][]

![9179e4cac3844a39943506e23e62e0bb.png][]

### **（1）简洁写法** ###

![caab3da890d34a8d8af9d322490d7351.png][]

### **（2）自写比较函数cmp()** ###

![78d6f5a4f74e4d99aca5d1d95f1f522e.png][]

# **三、部分排序** #

Python的sort()或 sorted()，没有C++的sort()灵活

sort()不能在数组的一部分上做排序，只能对整个数组排序。只能先拷贝出要排序的部分，排序后再拷贝回去。

sorted()虽可以对一部分排序，但是不能直接在原数组上排序。同样也需要拷贝。

## **1.经典例题1** ##

![8a115d6e678b4a848fa670b95a29f3a7.png][]

![728df766f09f440f880ba9d6ce83c5a9.png][]

### **（1）sort()代码** ###

![b76b41bb36914116a21ed2e41a0bfc54.png][]

### **（2）sorted()代码** ###

![12d7b1e46a9b48e69cd1632542cb1a2e.png][]

## **2.经典例题2** ##

![283d7ec28c064f44b10bbf6eb8fb21f9.png][]

### **（1）硬算+排序** ###

由于Python编码简洁，即使硬算出所有3、5、7的倍数，然后再排序找到59084709587505的位置，也容易编码。

![9dcbce8c339b49eeab4ac0dc1505d492.png][]

### **（2）暴力搜** ###

这个系列的数可以表示为3ix5jx7，搜索所有不超过范围的i、i、k组合即可。

Python不用担心大数，循环时顺便取个很大的范围作为终止条件，代码中最小的350肯定超过59084709587505。

![48414b633ef041e085d66d61a0566e69.png][]

[04875827c55d4fa5802057d5dd7f6f21.png]: https://img-blog.csdnimg.cn/img_convert/04875827c55d4fa5802057d5dd7f6f21.png
[51085d33f6ed4667bba808ba201caf6a.png]: https://img-blog.csdnimg.cn/img_convert/51085d33f6ed4667bba808ba201caf6a.png
[4045c2a95cdf4b818fd60079b7980197.png]: https://img-blog.csdnimg.cn/img_convert/4045c2a95cdf4b818fd60079b7980197.png
[3543ae42f74242b58bf876f04657279c.png]: https://img-blog.csdnimg.cn/img_convert/3543ae42f74242b58bf876f04657279c.png
[22be553f0ff7401c8e3c778673000f0b.png]: https://img-blog.csdnimg.cn/img_convert/22be553f0ff7401c8e3c778673000f0b.png
[6f4fe989b78940418f24956d2234c2ac.png]: https://img-blog.csdnimg.cn/img_convert/6f4fe989b78940418f24956d2234c2ac.png
[0f0bb9a84ec241d5a4bdeda90f4faf6d.png]: https://img-blog.csdnimg.cn/img_convert/0f0bb9a84ec241d5a4bdeda90f4faf6d.png
[3dcee97469ec41f2bd45eceaa56a48ba.png]: https://img-blog.csdnimg.cn/img_convert/3dcee97469ec41f2bd45eceaa56a48ba.png
[c5c252e824154801a9284134b969152d.png]: https://img-blog.csdnimg.cn/img_convert/c5c252e824154801a9284134b969152d.png
[6884f160c8964be7a16f6ce9ee54aacd.png]: https://img-blog.csdnimg.cn/img_convert/6884f160c8964be7a16f6ce9ee54aacd.png
[f5e0cf09913c4169aa3d995500dbe3ee.png]: https://img-blog.csdnimg.cn/img_convert/f5e0cf09913c4169aa3d995500dbe3ee.png
[90baad4c52114affaa0a7225b58e8073.png]: https://img-blog.csdnimg.cn/img_convert/90baad4c52114affaa0a7225b58e8073.png
[0917b8c62c864286b39898b361956c3d.png]: https://img-blog.csdnimg.cn/img_convert/0917b8c62c864286b39898b361956c3d.png
[8a1dfe1c1d454f9987b9375c1dfc295d.png]: https://img-blog.csdnimg.cn/img_convert/8a1dfe1c1d454f9987b9375c1dfc295d.png
[2ec73ee231594bca9441f29ac8a6fa2f.png]: https://img-blog.csdnimg.cn/img_convert/2ec73ee231594bca9441f29ac8a6fa2f.png
[9179e4cac3844a39943506e23e62e0bb.png]: https://img-blog.csdnimg.cn/img_convert/9179e4cac3844a39943506e23e62e0bb.png
[caab3da890d34a8d8af9d322490d7351.png]: https://img-blog.csdnimg.cn/img_convert/caab3da890d34a8d8af9d322490d7351.png
[78d6f5a4f74e4d99aca5d1d95f1f522e.png]: https://img-blog.csdnimg.cn/img_convert/78d6f5a4f74e4d99aca5d1d95f1f522e.png
[8a115d6e678b4a848fa670b95a29f3a7.png]: https://img-blog.csdnimg.cn/img_convert/8a115d6e678b4a848fa670b95a29f3a7.png
[728df766f09f440f880ba9d6ce83c5a9.png]: https://img-blog.csdnimg.cn/img_convert/728df766f09f440f880ba9d6ce83c5a9.png
[b76b41bb36914116a21ed2e41a0bfc54.png]: https://img-blog.csdnimg.cn/img_convert/b76b41bb36914116a21ed2e41a0bfc54.png
[12d7b1e46a9b48e69cd1632542cb1a2e.png]: https://img-blog.csdnimg.cn/img_convert/12d7b1e46a9b48e69cd1632542cb1a2e.png
[283d7ec28c064f44b10bbf6eb8fb21f9.png]: https://img-blog.csdnimg.cn/img_convert/283d7ec28c064f44b10bbf6eb8fb21f9.png
[9dcbce8c339b49eeab4ac0dc1505d492.png]: https://img-blog.csdnimg.cn/img_convert/9dcbce8c339b49eeab4ac0dc1505d492.png
[48414b633ef041e085d66d61a0566e69.png]: https://img-blog.csdnimg.cn/img_convert/48414b633ef041e085d66d61a0566e69.png