佛山网站建设 骏域网站网络推广的细节
文章目录
- 引言
- 不断的插入值，并保证序列是递增的。
- Python中sort()和sorted()的区别是啥？
- sorted 函数如何使用？
- 问题： 如何返回排序之后的索引
- 问题：排序的稳定性
- 问题，寻找第K大的元素的算法。
- 引出一个算法题；
- 参考资料
引言
突然想写一个关于排序问题的文章。笔者在初学算法的时候，总是会忽略排序算法。 当时的想法是这样的，排序算法既枯燥，有无聊； 一方面，我已经知道了冒泡排序的原理， 能写出一个简单的排序算法，差不多就行啦，对于快速排序，又有点复杂， 就算时间复杂度低一点，对我的作用也不是太大，因此总是不把排序算法放在心上。后来在刷算法题目的时候，逐渐意识到了一些关于排序算法的有趣问题，于是想在这里总结一下， 主要还是基于Python语言。
简单说一下我遇到的关于排序问题的场景:
不断的插入值，并保证序列是递增的。
假设有这样的场景：
我有一个二维列表dev_list， 列表中的元素为[a,b,c], 二维列表在迭代的过程中不断添加元素，想保证这个二维列表按照元素c为基准进行降序排列。
- 方案一: 从后往前插入元素，不断比较， 找到合适的位置插入（第一个大于自己的位置， 插入到这个位置的后面）
另一个思路: 从前往后插入元素， 不断比较， 找到第一个小于自己的位置，插入到这个位置
# 如果dev_list 为空，则插入一个元素，作为哨兵# 插入元素为 ele: [a,b,c]
... 上面是迭代的代码for i in range(len(dev_list)):if ele[2] > dev_list[i][2]:dev_list.insert(i, ele)break- 方案二：如果只是一维列表的插入，我们可以采用方案一的遍历，但是这样的复杂度是O(n), 已知的列表是有序的，我们可以采用二分法来插入， 这样的实际复杂度是 O(log2n)，python中有个很好用的函数bisect， 注意，bisect这仅对升序有效。
先学习一下bisect 的用法
bisect.bisect_left(a,x)
在a中找到x合适的插入点。返回的插入点 i 将数组 a 分成两半，使得 all(val < x for val in a[lo : i]) 在左半边而 all(val >= x for val in a[i : hi]) 在右半边。bisect.bisect_right(a, x)
bisect.bisect(a,x)
插入点在右边，对于相同元素。bisect.insort_right(a,x)
bisect.insort(a,x)
先定位一个插入点， 再插入使用实例:
#在m_list 列表中维护一个升序的数组。
dev_list.insort(m_list, ele)
- 方案三： 先插入元素，再对列表进行排序， 这个复杂度就比较高了。 但是这个的实用性还是很强的(不考虑复杂度的情况下，一行代码就搞定了)。
L.append(ele)
以第二个元素为键值进行排序。result = sorted(L, key=lambda x:x[2])# 多维度比较
result = sorted(L, key=lambda x:(x[0], -x[1]))
Python中sort()和sorted()的区别是啥？
- sort()方法必须由于list对象调用， sorted()方法的参数是所有的可迭代对象
- sorted()方法是新生成一个列表对象
总的来说，sorted()这个方法笔者应用的比较多。
sorted 函数如何使用？
sorted(iterable, cmp=None, key=None, reverse=False)
cmp遵守的规则： 大于返回1， 小于返回-1， 等于返回0
-
sorted(a), 直接对a 进行排序。
-
如何使用cmp ？ 后面可以带一个lambda表达式，有两个参数， 是从可迭代对象中取出的值, 这个函数可以自己定义，不过要符号要求。
L=[('b',2),('a',1),('c',3),('d',4)]
result = sorted(L, cmp=lambda x, y:cmp(x[1],y[1]))
- 如何使用key
sorted(L, key=lambda x:x[1])
-
reverse=True 表示的是降序排序。
-
给出一个案例： 对tuple进行排序，先按照第一个元素升序，如果第一个元素相同，再按照第二个元素降序排列。
L = [(12, 12), (34, 13), (32, 15), (12, 24), (32, 64), (32, 11)]
L.sort(key=lambda x: (x[0], -x[1]))
result = sorted(L, key=lambda x: (x[0], -x[1]))
print(L)
- python 如何自定义排序
在 Python 中，通过实现类的特殊方法 lt (即“小于”运算符) 可以实现自定义排序。这个方法定义了该类的实例如何与其他实例进行比较，例如在使用 sorted 函数对该类的实例进行排序时。
以下是一个例子：
class Person:
def init(self, name, age):
self.name = name
self.age = age
def __lt__(self, other):return self.age < other.age
这个类表示一个人，其中包含姓名和年龄属性。在 lt 方法中，我们定义了一个比较规则，即以年龄大小作为比较标准。这个方法返回 True 或 False，告诉 Python 如何比较两个实例。
笔者一开始疑惑为什么只定义小于，不定义等于这个判断，想了一下，这个是不需要的。 因为我们在比较的时候，只会遇到这两种情况， 要么小于，执行交换，要么就大于等于，不执行交换。
现在我们可以创建几个 Person 实例，并使用 sorted 函数进行排序：
p1 = Person(“Alice”, 25)
p2 = Person(“Bob”, 30)
p3 = Person(“Charlie”, 20)
people = [p1, p2, p3]
sorted_people = sorted(people)
for person in sorted_people:
print(person.name, person.age)
运行结果：
Charlie 20
Alice 25
Bob 30
如你所见，sorted 函数按照我们定义的规则对 Person 实例进行排序。这个例子中只使用了一个比较规则，但你可以根据需要定义多个规则来实现更复杂的排序方式。
需要注意的是，如果两个实例的比较结果相同，Python 还会使用默认的比较规则来决定它们的顺序。因此，不同的比较规则可能会产生不同的排序结果。
问题： 如何返回排序之后的索引
有的时候，我们在解决问题的时候，不一定需要直接排序后的结果，而是想求得排序之后对应的索引， 这里我们集中讨论下。
- 考虑对一维数组排序，并返回索引
方法一： 使用numpy中的函数argsort()
import numpy as np
nums = [4, 1, 5, 2, 9, 6, 8, 7]
print(np.argsort(nums))
方法二： 使用enumerate
nums = [4, 1, 5, 2, 9, 6, 8, 7]
sorted_nums = sorted(enumerate(nums), key=lambda x: x[1])
idx = [i[0] for i in sorted_nums]
nums = [i[1] for i in sorted_nums]
这种是python原生支持的， 不需要引入任何依赖库， 比较实用。
- 当然， 我们也可能会遇到一个对象列表，想对其进行排序后并返回索引。
思路也是比较简单， 我们可以使用sorted函数， 先按照一定规则对对象进行排序，然后返回一个对象列表，最后直接遍历返回后的有序列表的对象索引就可以了。
问题：排序的稳定性
在这里，我们简单聊一聊排序的稳定性。
什么是排序的稳定性， 其实就是说，在待排序的数组中， 值相同的元素在排序之后的相对位置不变。
快排的核心思想：
选择一个基础值， 两个指针都移动，保证小于基础值的数在左边， 大于基础值的数在右边。
快排不稳定的原因： 如果有两个相同的值比基础值小， 那么它会与前面第一个比基础值大的值进行位置交换， 这个时候就会引起相同值的相对位置变化， 也就是排序不稳定
思考一下我们的冒泡排序， 在交换位置的时候， 相同值的相对位置是不会变化的。 要移动都会相对移动，要静止都会相对静止。
问题，寻找第K大的元素的算法。
参考资料:
https://www.jianshu.com/p/33ee33ce8699
-
排序法
-
插入法
-
小顶堆法
-
快速排序法。
这里贴一个快速排序的改进算法来求解第K大的元素。
public static int partition(int[] array, int left, int right) {int k = array[left];int i = left;int j = right;while (j > i) {while (array[j] < k && j > i) {j--;}if (j > i) {array[i] = array[j];i++;}while (array[i] > k && j > i) {i++;}if (j > i) {array[j] = array[i];j--;}}array[i] = k;return i;
}public static void quickSort(int[] array, int left, int right) {if (left >= right) {return;}int i = partition(array, left, right);quickSort(array, left, i - 1);quickSort(array, i + 1, right);
}public static int findK(int[] array, int left, int right, int k) {int i = partition(array, left, right);if (i == k - 1) {return array[k - 1];} else if (i > k - 1) {return findK(array, left, i - 1, k);} else if (i < k - 1) {return findK(array, i + 1, right, k);}return 0;
}
引出一个算法题；
https://leetcode.cn/problems/minimum-size-subarray-sum/comments/
长度最小的子数组。
https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
参考资料
https://blog.csdn.net/y12345678904/article/details/77507552