排序算法

<p> </p>
<p>转载整理自<a href="https://blog.csdn.net/developer1024" id="uid">7-sevens</a>大佬，本文仅供本人学习使用，请勿用作其他用途，如有所需，请联系大佬本人！！！</p>
<p>原文链接合集附在本文底部。</p>
<hr>
<h2>一、排序算法系列目录说明</h2>
<blockquote>
<p>冒泡排序（Bubble Sort）<br> 插入排序（Insertion Sort）<br> 希尔排序（Shell Sort）<br> 选择排序（Selection Sort）<br> 快速排序（Quick Sort）<br> 归并排序（Merge Sort）<br> 堆排序（Heap Sort）<br> 计数排序（Counting Sort）<br> 桶排序（Bucket Sort）<br> 基数排序（Radix Sort）</p>
</blockquote>
<hr>
<h2>二、排序算法简介说明</h2>
<p><strong>1. 定义</strong><br> 将一组杂乱无章的数据按一定的规律顺次排列起来。例如：</p>
<p>输入：a1，a2，a3，…，an</p>
<p>输出：a1’，a2’，a3’，…，an’（满足a1′ <= a2′ <= a3′ <= … <= an’排列）</p>
<p><strong>2. 算法性能评估术语言</strong><br> 稳定：如果a原本在b前面，而a=b时，排序之后a仍然在b的前面。<br> 不稳定：如果a原本在b的前面，而a=b时，排序之后a可能出现在b的后面。</p>
<p>内排序：所有排序操作都在内存中完成。<br> 外排序：通常是由于数据太大，不能同时存放在内存中，根据排序过程的需要而在外存与内存之间数据传输才能进行。</p>
<p>时间复杂度：时间频度，一个算法执行所耗费的时间。算法中通常用数据比较次数与数据移动次数进行衡量。<br> 空间复杂度：算法执行所需要的内存大小。<br> </p>
<hr>
<h2>三、冒泡排序（Bubble Sort）</h2>
<h3>1. 基本思想</h3>
<p>冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。</p>
<p>重复走访要排序的数列，通过两两比较相邻记录的排序码。排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。</p>
<p>趣味解释：<br> 有一群泡泡，其中一个泡泡跑到一个泡小妹说，小妹小妹你过来咱俩比比谁大，小妹说哇你好大，于是他跑到了泡小妹前面，又跟前面的一个泡大哥说，大哥，咱俩比比谁大呗。泡大哥看了他一眼他就老实了。这就是内层的for，那个泡泡跟每个人都比一次。</p>
<p>话说那个泡泡刚老实下来，另一个泡泡又开始跟别人比谁大了，这就是外层的for，每个泡泡都会做一次跟其他泡泡比个没完的事。</p>
<h3>2. 实现逻辑</h3>
<p>比较相邻的元素。如果第一个比第二个大，就交换他们两个。<br> 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。<br> 针对所有的元素重复以上的步骤，除了最后一个。<br> 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。<br> 通过两层循环控制：</p>
<p>第一个循环（外循环），负责把需要冒泡的那个数字排除在外；<br> 第二个循环（内循环），负责两两比较交换。</p>
<h3><br> 3. 动图演示bubble_sort</h3>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-5d4fb94418562fa1c7ac9157f8dced82"></p>
<h3>4. 性能分析</h3>
<blockquote>
<ul><li>平均时间复杂度：O(N^2)</li><li>最佳时间复杂度：O(N)</li><li>最差时间复杂度：O(N^2)</li><li>空间复杂度：O(1)</li><li>排序方式：In-place</li><li>稳定性：稳定</li></ul>
</blockquote>
<p>解析说明：<br> 冒泡排序涉及相邻两两数据的比较，故需要嵌套两层 for 循环来控制。<br> 外层循环 n 次，内层最多时循环 n – 1次、最少循环 0 次，平均循环(n-1)/2；<br> 所以循环体内总的比较交换次数为：n*(n-1) / 2 = (n^2-n)/2<br> 按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2)<br> 最优的空间复杂度为开始元素已排序，则空间复杂度为 0；<br> 最差的空间复杂度为开始元素为逆排序，则空间复杂度为 O(N);<br> 平均的空间复杂度为O(1)</p>
<p>注：</p>
<blockquote>
<ul><li>n：数据规模</li><li>k：”桶”的个数</li><li>In-place：占用常数内存，不占用额外内存</li><li>Out-place：占用额外内存</li></ul>
</blockquote>
<h3><a id="5_C_84"></a>5. 代码实现（C++版&

排序算法

浏览过的版块