排序算法之耐心排序

排序算法之耐心排序

     耐心排序的基本思想:耐心排序还是对插入排序做的一种优化,先将数据调整为基本有序,再进行一次插入排序。耐心排序的关键点是在建桶和入桶的规则上面。
     (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;
}
上一篇:单调递增最长子序列(南阳理工ACM)


下一篇:互联网公司里都有哪些潜规则?