基本原理：对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻的两个数据次序和排序要求的大小次序不符合的时候，即将这两个数据进行互换。如果从小到大排序，这时，较小的数据就会逐个向前移动，好像气泡向上漂浮一样。
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)
稳定性：不稳定
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/204019.html