单向链表冒泡排序（单向链表快速排序）



基本原理：对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻的两个数据次序和排序要求的大小次序不符合的时候，即将这两个数据进行互换。如果从小到大排序，这时，较小的数据就会逐个向前移动，好像气泡向上漂浮一样。

https://www.runoob.com/wp-content/uploads/2019/03/bubbleSort.gif

冒泡排序的特点：升序排序中每一轮比较会把最大的数下沉到最底，所以相互比较的次数每一轮都会比前一轮少

时间复杂度：O(n2)

这是曾经思考过的问题， 它为什么叫快速排序呢？思考无果，然后忘记了，然后昨天被问起，自然想不出很好的答案。直到，看到了《暗时间》上有这个问题的答案。

在《暗时间》里，作者刘未然并没有直接给出答案，而是先说了两个游戏，猜数字和称球。这两个问题都很好理解，并且不难解答。然而，令我豁然开朗的是，他们指向了同一个思想，分而治之！把问题不断切割一半又一半，直到答案水落石出。

回到正题，我们的目标是排序，无论哪个排序方法都是基于两两比较的，问题在于如何才能减少比较的次数呢？举个例子，有这么一组数：1，2,3,4,5,15，78,89,90,100，200；一共11个。并且给出的初始顺序是从小到大的， 现在要排成从大到小。快速排序的思想，就是从中抽取一个数（称为基准吧），然后大于基准的在一边，小于或等于在另一边。比如，现在随机的抽取了78，那么1，2,3,4,5,15会在一边，89,90,100，200会在另一边。这时候，注意到，从这一刻开始，小于78的那些数就再也没有机会与大于78的数进行两两比较了。快速排序用了分而治之的思想，虽然，由于随机抽取，我们最好第一次抽到的是15，这样就平分了。但是没关系。忽略掉这个随机性因素，快排还是把大问题分成了两个小问题，哪怕这两个字问题不一定对等。只要递归下去，结果水到渠成。

相比大家应该都玩过猜数的游戏。就是给你一个100以内的数，然后让你猜这个数是多少。

先说第一个解决方案，就是从0到100一个一个数。

第二个解决方案就是先猜50，如果比50大就猜50左边的数，如果比50小就猜50左边的数，假设这个数是75，小于50的数就再也不用比较，就大大减少了比较次数。

这个例子就可以看成一个分而治之。把大问题拆成小问题。

而用到这个分而治之的想法时，在c语言就可以使用递归。

时间复杂度：O(N*logN)

空间复杂度：O(logN)

稳定性：不稳定

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/40037.html