经典排序算法 - 耐心排序Patience Sorting

旧城等待， 2022-01-10 15:51 214阅读 0赞

**经典排序算法 - 耐心排序**Patience Sorting

这个排序的关键在建桶和入桶规则上

建桶规则:如果没有桶,新建一个桶;如果不符合入桶规则那么新建一个桶

入桶规则:只要比桶里最上边的数字小即可入桶,如果有多个桶可入,那么按照从左到右的顺序入桶即可

举个例子,待排数组\[6 4 5 1 8 7 2 3\]

第一步,取数字6出来,此时一个桶没有,根据建桶规则1新建桶,将把自己放进去,为了表述方便该桶命名为桶1或者1号桶

第二步,取数字4出来,由于4符合桶1的入桶规则,所以入桶1,并放置在6上边,如下图2所示

第三步,取数字5出来,由于5不符合桶1的入桶规则,比桶1里最上边的数字大,此时又没有其它桶,那么根据建桶规则新建桶2,放入住该桶

第四步,取数字1出来,1即符合入1号桶的规则,比4小嘛,也符合入2号桶的规则,比5也小,两个都可以入,根据入桶规则1入住1号桶(实际入住2号桶也没关系)

第五步,取数字8出来,8比1号桶的掌门1大,比2号桶的掌门5也大,而且就这俩桶,所以8决定自立门派,建立了3号桶,并入住该桶成为首位掌门

第六步,取数字7出来,1号桶,2号桶的掌门都不行,最后被3号桶收服,投奔了3号桶的门下

第七步,取数字2出来,被2号桶掌门收了

第八步,取数字3出来,被3号桶的现任掌门7收了

全部入桶完毕....

[![Image(3)][Image_3]][Image_3_Image_3]

然后从第一个桶顺序取出数字1 4 6,2 5,3 7 8

剩下的使用[插入排序][Link 1]结束战斗,下班回家也~

[返回主目录 \[经典排序算法\]\[集锦\]][Link 2]

转载于:https://www.cnblogs.com/kkun/archive/2011/11/23/2260291.html

[Image_3]: https://images.cnblogs.com/cnblogs_com/kkun/201111/20111123143829563.png
[Image_3_Image_3]: /images/20220110/16cc7c2c87994e53a505d7725d22e92a.png
[Link 1]: http://www.cnblogs.com/kkun/archive/2011/11/23/2260265.html
[Link 2]: http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java经典排序算法：冒泡排序Bubble Sort，动图演示排序过程

Java经典排序算法之冒泡排序Bubble Sort，动图演示排序过程 ![2019092011431184.gif][] public class ...

冷不防/ 2024年04月19日 13:29/ 0 赞/ 63 阅读

相关经典排序算法

一、概念：将杂乱无序的数据元素，通过一定的方法按关键字顺序排列的过程就是排序。二、常见的排序算法：不稳定的排序算法：快速排序、希尔排序、堆排序、直接选择排序

桃扇骨/ 2023年01月21日 10:27/ 0 赞/ 91 阅读

相关经典排序算法—冒泡排序

冒泡排序原理：定义一个数组 $ar=array('1','3','2',

红太狼/ 2022年07月13日 04:46/ 0 赞/ 197 阅读

相关经典排序算法 - 冒泡排序Bubble sort

原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换, 这样一趟过去后,最大或最小的数字被交换到了最后一位, 然后再从头开始进行两两比较交换,直到倒数第二位

清疚/ 2022年06月09日 03:18/ 0 赞/ 205 阅读

相关 Java 经典算法之冒泡排序(Bubble Sort)

原理：比较两个相邻的元素，将值大的元素交换至右端。思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后

落日映苍穹つ/ 2022年06月03日 03:51/ 0 赞/ 191 阅读

相关 python实现耐心排序算法

前面我们讲解了[耐心排序算法][Link 1]，今天我们来看一下代码的实现，直接上代码 !/usr/bin/python -- coding: utf-8

红太狼/ 2022年05月11日 01:42/ 0 赞/ 178 阅读

相关 go实现耐心排序算法

前面我们讲解了[耐心排序算法][Link 1]，今天我们来看一下代码的实现，直接上代码 package main import (

野性酷女/ 2022年05月11日 01:42/ 0 赞/ 161 阅读

相关耐心排序详解

嗯，看名字挺有耐心的，耐心排序充分集合了桶排序和插入排序的优点首先使用桶排序，排序之后每个桶中数据相对有序，这样再使用插入排序，简化了问题，速度变的更快我们通过例子来讲

旧城等待，/ 2022年05月11日 01:40/ 0 赞/ 153 阅读

相关经典排序算法

冒泡排序冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序。它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相

淩亂°似流年/ 2022年03月21日 02:29/ 0 赞/ 242 阅读

相关经典排序算法 - 耐心排序Patience Sorting

经典排序算法 - 耐心排序Patience Sorting 这个排序的关键在建桶和入桶规则上建桶规则:如果没有桶,新建一个桶;如果不符合入桶规则那么新建一个桶入桶规则

旧城等待，/ 2022年01月10日 15:51/ 0 赞/ 215 阅读