本文共 2084 字，大约阅读时间需要 6 分钟。
耐心排序的基本思想：耐心排序还是对插入排序做的一种优化，先将数据调整为基本有序，再进行一次插入排序。耐心排序的关键点是在建桶和入桶的规则上面。
（1）如果还没有桶，新建一个桶。如果不符合入桶规则那么新建一个桶。 （2）要入桶的数字只要比桶里最上面的数字小，即可入桶；如果有多个桶可入，则按照从左到右的顺序入桶。 举例：有待排序序列6， 3， 4， 7， 1， 2， 8，5 （1）取数据6，目前还没有桶，则新建桶[1]，将6入桶。 目前有桶[1]，桶内数据｛6｝。 （2）取数字3，桶[1]中最上面的数据6比3大，所以数据3入桶[1]。 目前有桶[1]，桶内数据｛3， 6｝。 （3）取数据4，桶[1]中最上面数据3比4小，4不能入桶[1]，新建桶[2]，4入桶[2]。 目前有桶[1]和桶[2]两个桶，桶[1]中数据为｛3， 6｝， 桶[2]中数据为｛4｝。 （4）取数据7，7比桶[1]中最上面的数据3大，比桶[2]中最上面的数据4大，所以不能入桶[1]和桶[2]，新建桶[3]，7入桶[3]。 目前有桶[1]，桶[2]，桶[3]三个桶，桶[1]中数据为｛3， 6｝， 桶[2]中数据为｛4｝，桶[3]中数据为｛7｝。 （5）取数据1，1比桶[1]、桶[2]、桶[3]最上面的数据都要小，则入从左向右第一个桶，所以1入桶[1]。 目前有桶[1]，桶[2]，桶[3]三个桶，桶[1]中数据为｛1， 3， 6｝， 桶[2]中数据为｛4｝，桶[3]中数据为｛7｝。 （6）取数据2，2比桶[2]、桶[3]最上面的数据都要小，则入从左向右第一个桶，所以2入桶[2]。 目前有桶[1]，桶[2]，桶[3]三个桶，桶[1]中数据为｛1， 3， 6｝， 桶[2]中数据为｛2， 4｝，桶[3]中数据为｛7｝。 （7）取数据8，8比桶[1]中最上面的数据1大，比桶[2]中最上面的数据2大，比桶[3]最上面的数据7大，所以不能入桶[1]、桶[2]、桶[3]，新建桶[4]，8入桶[4]。 目前有桶[1]，桶[2]，桶[3]，桶[4]四个桶，桶[1]中数据为｛1， 3， 6｝， 桶[2]中数据为｛2， 4｝，桶[3]中数据为｛7｝，桶[4]中有数据｛8｝。 （8）取数据5，5比桶[3]、桶[4]最上面的数据都要小，则入从左向右第一个桶，所以5入桶[3]。 目前有桶[1]，桶[2]，桶[3]，桶[4]四个桶，桶[1]中数据为｛1， 3， 6｝， 桶[2]中数据为｛2， 4｝，桶[3]中数据为｛5，7｝，桶[4]中有数据｛8｝。 建桶并将数据分配入桶之后，然后从第一个桶至最后一个桶顺序取出数据｛1，3，6，2，4，5，7，8｝，然后进行一次直接插入排序。BOOL PatienceSort(datatype *array, int size){ int i, j; Node **bucket; Node *p; if(array == NULL) { return FALSE; } bucket = (Node **)calloc(size, sizeof(Node *)); if(bucket == NULL) { return FALSE; } for(i = 0; i < size; i++) { j = 0; //找到第一个最上面的数据比关键字大的桶，如果没找到则指向一个空位置 while(bucket[j] != NULL && (bucket[j])->data < array[i]) j++; p = (Node *)malloc(sizeof(Node)); if(p == NULL) { return FALSE; } p->data = array[i]; //将关键字入桶 if(bucket[j] != NULL) { p->next = bucket[j]; } else { p->next = NULL; } bucket[j] = p; } i = j = 0; //顺序的从第一个桶到最后一个桶中取出数据 while(bucket[j] != NULL) { p = bucket[j]; while(p != NULL) { array[i++] = p->data; p = p->next; } j++; } //进行一次插入排序 InsertionSort(array, size); return TRUE;} 转载地址：http://qrtil.baihongyu.com/