排序算法之耐心排序

简介: 排序算法之耐心排序     耐心排序的基本思想:耐心排序还是对插入排序做的一种优化,先将数据调整为基本有序,再进行一次插入排序。耐心排序的关键点是在建桶和入桶的规则上面。      (1)如果还没有桶,新建一个桶。如果不符合入桶规则那么新建一个桶。      (2)要入桶的数字只要比桶里最上面的数字小,即可入桶;如果有多个桶可入,则按照从左到右的顺序入桶。     

排序算法之耐心排序

     耐心排序的基本思想:耐心排序还是对插入排序做的一种优化,先将数据调整为基本有序,再进行一次插入排序。耐心排序的关键点是在建桶和入桶的规则上面。
     (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;
}
目录
相关文章
|
3月前
|
算法 C++
【洛谷 P1223】排队接水(贪心算法+结构体排序)
该问题要求安排$n$个人的排队顺序以最小化平均等待时间。每个人接水需时$T_i$,解决方案是让接水时间短的人优先。给定$n\leq1000$和$t_i\leq10^6$,代码示例使用C++实现,通过排序使时间从小到大排列,然后计算平均等待时间。样例输入为10个人的时间数组,输出为优化后的排队顺序及平均等待时间(291.90)。
32 0
|
1月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
1月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
16 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
28天前
|
算法 搜索推荐 Java
算法实战:手写归并排序,让复杂排序变简单!
归并排序是一种基于“分治法”的经典算法,通过递归分割和合并数组,实现O(n log n)的高效排序。本文将通过Java手写代码,详细讲解归并排序的原理及实现,帮助你快速掌握这一实用算法。
36 0
|
1月前
|
算法 关系型数据库 MySQL
揭秘MySQL中的版本号排序:这个超级算法将颠覆你的排序世界!
【8月更文挑战第8天】在软件开发与数据管理中,正确排序版本号对软件更新及数据分析至关重要。因MySQL默认按字符串排序版本号,可能出现&#39;1.20.0&#39;在&#39;1.10.0&#39;之前的不合理情况。解决办法是将版本号各部分转换为整数后排序。例如,使用`SUBSTRING_INDEX`和`CAST`函数从`software`表的`version`字段提取并转换版本号,再按这些整数排序。这种方法可确保版本号按逻辑正确排序,适用于&#39;major.minor.patch&#39;格式的版本号。对于更复杂格式,需调整处理逻辑。掌握此技巧可有效应对版本号排序需求。
73 3
|
1月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
|
1月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
18 0
|
2月前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
65 4
|
3月前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
3月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素