--- title: 排序算法 冒泡 选择 插入 堆 归并 快速 图解 记录 url: 'https://yayi.site/archives/排序算法冒泡选择插入堆归并快速图解记录' categories: 算法与设计 cover: 'https://cdn.jsdelivr.net/gh/yan-bolan/picbed/img/动漫/結城友奈は勇者である/三ノ·輪 銀.png' tags: '数据结构,排序算法,二叉树,堆排序,归并排序' abbrlink: d3986485 date: 2020-09-20 23:42:36 updated: 2021-05-14 22:04:49 ---  # 排序算法 一些算法记录 复杂度 和时间度这种衡量，只能说适用的场景不同，没有优劣之分 最好自己动手手动排一下。 不想排的话，推荐 ==算法动画图解== 这个app 就是收费而已 ### 冒泡排序\`\` \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9 \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 5 \| 9 \| 3 \| 1 \| 2 \| 8 \| 4 \| 7 \| 6 \| 1. 将天平放在 右端， 比较7 和6， 2. 7大于6 ，交换 。小于等于不交换。 3. 交换后，移动天平，前进1格。 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9 \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 5 \| 9 \| 3 \| 1 \| 2 \| 8 \| 4 \| 6 \| 7 \| 4. 4 和6比 。不交换 5. 一直到最左端 两个比较。完成后，最小的被移到最左端了。标志 一号位置为已排序. \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9 \| \| ----- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| \~\~1\~\~ \| 5 \| 9 \| 3 \| 2 \| 4 \| 8 \| 6 \| 7 \| 6. 重复同样的操作 。与上次不同的是 不需要再到一号位置停止了，因为一号位置是最小的了。所以到二号位置停止。 7. 依次停止，最后一定是只比较8和9号位置。 8. 完成 ### 选择性排序 1. 线性搜索 数列找到最小值，==交换==，放到最左端，如果已经在最左，则无操作。 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9 \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 1 \| \| \| 8 \| \| \| \| \| \| 2. 重复操作，搜索==剩下的== 。从剩下的开始搜索。如 第二次时，剩下最小放到第二号位置。 3. 完成。 ### 插入排序 1. 首先，1号位置 当作已排序，取出尚未操作的左端数字。与已操作的数字进行比较。如 5 3 比较 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9 \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 5 \| \| 4 \| 7 \| 2 \| 8 \| 6 \| 9 \| 1 \| \| \| 3 \| \| \| \| \| \| \| \| 2. 5 3 比较，交换 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9 \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 3 \| 5 \| 4 \| 7 \| 2 \| 8 \| 6 \| 9 \| 1 \| \| \| \| \| \| \| \| \| \| \| 3. 然后选出三号位置的4 与 3 5两个（前面） 比较。 ==插在前面比4小，后面比4大的地方== ，==一位一位的与前面比==， 也就是3 和5 之间，5向后移一位 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9 \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 3 \| 4 \| 5 \| 7 \| 2 \| 8 \| 6 \| 9 \| 1 \| \| \| \| \| \| \| \| \| \| \| 4. 重复 插入比较动作，剩下已排序 元素右移一个单位，因为，你插入到队伍中，肯定要有人腾出位置，后面的人跟着腾出位置，直到你原来的位置。也就是只有已排序的移动 而已。 5. 重复动作。 直到最后一个元素9号位置的元素被操作了，就完成 了。 ### 堆排序 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9 \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 5 \| 2 \| 7 \| 3 \| 6 \| 1 \| 4 \| \| \| 堆是一种结构。像树。 1. 首先 。得先数字==存储到堆里==，按==降序==构建堆。？？？ 降堆是：父结点比子结点大。左孩子比右孩子大。  依次从数列中取出，作为新的子结点，先==左孩子再右孩子==，然后==与父结点比较，一直没有父结点大于它 ，停止。== 总之， 大的往上移动。  一棵二叉树  堆 2. 降堆 好处是 ，取出数据时 按从大到小取出，取出来 相反排序就相当于是完成 了排序 。 \~\~只需要取出根结点。取出的时候，叶子结点的右孩子（没有就取左），填到根结点上，然后与 自己（根）的==孩子结点==比，大的则交换，一直交换到没有比它大的。这样保证每次取出来的都是根结点是最大的，而且有序的。\~\~ 3. 其实堆是也用数列来储存的 !\[image-20200920230819942\](http://img.yayi.site/csdn/d0914db707fc6d7d81d6a5cb2baa41f0.png-watermaskStyle) \| A \| B \| C \| D \| E \| F \| G \| H \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 7 \| 6 \| 5 \| 2 \| 3 \| 1 \| 4 \| \| 对应起来就是这个样子 1. 最大的肯定是A， A与G 比 ，G是数列最后一个元素。交换。 2. 这样，A 是4 ，G 是7 。然后，重新构建堆。保持降序的结构。 3. 然后还是 A 与==G-1==(因为G和后面的排好了)也就是A 位置与 F位置交换。再重新构建堆 重复步骤。完成 注意是 从数列的角度来取的。而不是堆视图，乱 。取出后，可以去除堆视图中相应的元素，以便学习观察。或者数列中标灰。 ### 归并排序 1. 首先将数列分两半，分到第三层 !\[image-20200920232934899\](http://img.yayi.site/csdn/d140531691c6a5907618927dd21d6e58.png-watermaskStyle)怎么有点像二叉树 2. 从最底层开始。两个两个比 ，比完交换完，移动到上一层。 !\[image-20200920233256859\](http://img.yayi.site/csdn/c2e933ff778afabac03ab1babce99c1a.png-watermaskStyle) 当图形内一个组 多于一个数字时，比较这两个组 里分别开头的数字。 4 和3 比，大的就先往上层移，排在开头。所以是选3 再 4 。剩下的依次对比。6 和7 比。 !\[image-20200920233743368\](http://img.yayi.site/csdn/f663566e61779fd6152f2000dccff755.png-watermaskStyle) 3. 递归地重复合并操作。直到所有的数字在同一个组中。 关键点：分成了两个，一层层上来，只需要对比对应位置的就行了。 归并 ### 快速排序 交换次数少。某些情况下。， 1. 第一个操作对象 是 数列中所有 的数字，随机选择一个数字作为pivot . 为了方便，取 最右边 。 \| A \| B \| C \| D \| E \| F \| G \| H \| J \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 3 \| 5 \| 8 \| 1 \| 2 \| 9 \| 4 \| 7 \| 6 \| \| L \| \| \| \| \| \| R \| \| P \| 最左标记为L ,最右为R 原理：使用标记递归重复操作。 2. L 向右前进，当对位置的数字==大于==p位置的数字时，停止移动 。 如到8 。然后，R 向左移，一直到==小于==p的数字停止。如到4 然后==交换L和R位置的数字== \| A \| B \| C \| D \| E \| F \| G \| H \| J \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 3 \| 5 \| 4 \| 1 \| 2 \| 9 \| 8 \| 7 \| 6 \| \| \| \| \| \| \| L \| R \| \| P \| 如此 ，L 继续移动 ，到9 时，停止，轮到R移动了，R 移动到F位置，也就是9 。L与R 在同一个位置了，所以R 只能停止，然后LR位置 与P交换。 \| A \| B \| C \| D \| E \| F \| G \| H \| J \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ----- \| ---- \| ---- \| ----- \| \| 3 \| 5 \| 4 \| 1 \| 2 \| ==6== \| 8 \| 7 \| ==9== \| \| \| \| \| \| \| LR \| \| \| P \| 3. LR相遇，算完成一次排序。这样下来，左则收集的数字小于F位置，右则的数字大于F位置，即小于6 大于 6 因此，下一次排序不需要 整个数列了，排的是 ==A到E位置==的数字， 在程序上，这种操作可以用递归来实现。一种子集关系嘛， 对子集进行 重复上面 一 二步骤操作。：建立L R P \| A \| B \| C \| D \| E \| F \| G \| H \| J \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 3 \| 5 \| 4 \| 1 \| 2 \| 6 \| 8 \| 7 \| 9 \| \| L \| \| \| R \| P \| \| \| \| \| 一直到 建立LRP时，发现只有一个数字，则算是到底了。 \| A \| B \| C \| D \| E \| F \| G \| H \| J \| \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| ---- \| \| 1 \| 5 \| 4 \| 3 \| 2 \| 6 \| 8 \| 7 \| 9 \| \| \| LR \| \| \| P \| \| \| \| \| 如左边子集只剩1了，分配LR时 L等于R了，所到底了， 关键在于 ：递归子集， --- ==主要是记录一下，还是找相关书看一下好。==