排序算法之耐心排序
耐心排序的基本思想:耐心排序还是对插入排序做的一种优化,先将数据调整为基本有序,再进行一次插入排序。耐心排序的关键点是在建桶和入桶的规则上面。
(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;
}