几种有趣的不常见排序-程序员宅基地

技术标签: 奇偶排序  梳排序  臭皮匠排序  鸽巢排序  算法与ACM  鸡尾酒排序  

几种有趣的不常见排序算法

我们常见的排序算法有简单选择,冒泡,插入,两路合并,希尔,堆,快速排序等等,下面介绍几种不常见的排序算法。

 

鸡尾酒排序

鸡尾酒排序是冒泡排序的微调算法。

我们还记得,冒泡排序是每次遍历整个序列,把较大的(我们这里假设升序排序)交换到后面。鸡尾酒排序在交换到后面后,再逆向把最小的交换到前面。

为什么取名叫鸡尾酒呢?估计就像鸡尾酒的上下搅动相似。

代码:

void cocktail_sort(int *A,int N)
{
    int  bottom = 0;
    int top = N - 1;
    bool swapped = true;
    while (swapped == true)
    {
        swapped = false;
        for (int i = bottom; i < top; i = i + 1)
        {
            if (A[i] > A[i + 1])
            {
                swap(A[i], A[i + 1]);
                swapped = true;
            }
        }
        top = top - 1;
        for (int i = top; i > bottom; i = i - 1)
        {
            if (A[i] < A[i - 1])
            {
                swap(A[i], A[i - 1]);
                swapped = true;
            }
        }

        bottom = bottom + 1;
    }
}


时间复杂度O(n^2)

 

鸽巢排序

一群飞出去瞎逛的鸽子,全都飞回来原来的巢穴了,它们按照自己的编号蹲到自己的巢穴中,就变得有序了,这就是鸽巢排序。如下图:

 


 

接着,我们用数组A表示鸽子,数组B表示巢穴,即hash表,在B中记数后,放回到A中。代码如下:

 

void PigeonholeSort(int *array,int N)
{
    int n = 256;//这里本应该是待排序数组的最大值+1,作为测试所以假设备用数组的长度为256
    int j = 0;
    int b[n];
    memset(b,0,sizeof(b));
    for (int i = 0; i < N; i++)
    {
        b[array[i]]++; //备用数组的索引即是待排序数组的值
    }
    for (int i = 0; i <n; i++)
    {
        for (int k = 0; k < b[i]; k++)
        {
            array[j] = i; //把鸽巢里的值再次送回到待排序数组
            j++;
        }

    }
}


鸽巢排序方法很直观,不过我们也看出来它有过多的局限性,多余的空间,不确定的最大值等等。时间复杂度为O(n+N);


奇偶排序

又称奇偶换位排序,类似冒泡排序的思想,先是奇-偶换位,然后偶-奇换位,最后没有换位操作是,判断排序成功。如下图:

 

 

代码如下:

 

void Batcher(int *A,int N)
{
    bool sorted = false;
    while (!sorted)
    {
        sorted=true;
        for (int i = 1; i < N-1; i += 2)
        {
            if (A[i] > A[i+1])
            {
                swap(A, i,i+1);
                sorted = false;
            }
        }


        for (int i = 0; i < N-1; i += 2)
        {
            if (A[i] > A[i+1])
            {
                swap(A, i, i+1);
                sorted = false;
            }
        }
    }
}


时间复杂度O(n^2);


臭皮匠排序

看到这个名字和算法的时候,我也惊呆了。具体一个看,还真像他的名字那样,看着有意思,实际也就是臭皮匠而已。有时候效率还不及冒泡排序。

臭皮匠排序是一个递归排序,每个序列判断交换头尾两个后,分为三个子序列,也就是三个臭皮匠。


如果最后一个值小于第一个值,则交换它们

如果当前子集元素数量大于等于3:

使用臭皮匠排序前2/3的元素

使用臭皮匠排序后2/3的元素

再次使用臭皮匠排序前2/3的元素


 


代码:

void stoogesort(int *A, int i, int j)
{
    if (A[j] < A[i])
        swap(A,i,j);
    if ((j - i + 1) >= 3)
    {
        int t = (j - i + 1) / 3;
        stoogesort(A, i  , j-t);
        stoogesort(A, i+t, j  );
        stoogesort(A, i  , j-t);
    }
    return;
}


时间复杂度为:O(nlog 3 /log1.5)

 

梳排序

梳排序也类似冒泡排序,只不过他的间隔不是1,而是一个不断递减的值。Gap初始为整个队列的大小,接着按照一个递减参数减少至1,。当gap==1是,就退化为冒泡排序。

有人证明,gap的递减因子设置为1.247330950103979时,能达到最好的效果。

如下图:


交换比较的间隔不断缩小至1,变为冒泡排序。

这样的好处是用较大的间隔,把原先影响冒泡排序效率的最后的几个“乌龟”(如果是升序排序,就是在后面的几个小值)快速地移动到较前的地方,用以提高冒泡的效率。

 

代码:

void combsort(int *arr, int size)
{

    float shrink_factor = 1.247330950103979;
    int gap = size, swapped = 1, swap, i;

    while ((gap > 1) || swapped)
    {
        if (gap > 1) gap = gap / shrink_factor;

        swapped = 0;
        i = 0;

        while ((gap + i) < size)
        {
            if (arr[i] - arr[i + gap] > 0)
            {
                swap = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = swap;
                swapped = 1;
            }
            ++i;
        }
    }
}

时间复杂度:O(n^2/2^p)

 

图书馆排序

图书馆排序是一种改进的插入排序,是一种以空间换时间的方法。

回忆一下插入排序,由前往后寻找插入的位置,接着把位置之后的所有元素后移一个位置。图书馆排序就是来处理第二步,后移一个位置。

图书馆管理员在放书的时候,一本本书放到书架上,如果每放一本都紧贴着,那么后来要在中间插入的时候,就要费工夫把书分开,腾出插入的空间了。如果在放书的时候,就预留了空间,那么就可以少花这些工夫了。


 

 

具体的间隔设置是多少,没有搜到相关资料。

 图书馆君的编码:

首先我们新建一个数组,把每个元素以某个间隔存放,然后执行直接插入。插入时,选择插入位置前某个空余空间;如果没有空余空间,按照原来的直接插入的方法,全部往后移;最后去掉空格,整理排序结果。


这里我们取gap=4,用一个额外的数组B来记录空余空间,代码如下:

 

void libsort(int *A,int *B,int N,int l)
{
    for (int i=1;i<N;i++)
    {
        if (B[i])
        {
            for (int j=0;j<i;j++)
            {
                if (B[j]&&A[j]>A[i])
                {
                    if (!B[j-1])
                    {
                        B[j-1]=1;
                        A[j-1]=A[i];
                        A[i]=0;
                        B[i]=0;
                        break;
                    }
                    else
                    {
                        int temp=A[i];
                        for (int k=i;k>=j+1;k--)
                        {

                            A[k]=A[k-1];
                            B[k]=B[k-1];
                        }
                        A[j]=temp;
                        B[j]=1;
                        break;
                    }
                }
            }
        }

    }
}

int main()
{
    int N,A[maxn],B[maxn];
    cin>>N;
    memset(B,0,sizeof(B));
    memset(A,0,sizeof(B));
    int k=0;
    int gap=4;
    for (int i=0;i<N;i++)
    {
        cin>>A[k];
        B[k]=1;
        k+=gap;
    }
    libsort(A,B,k-gap+1,k);
    for (int i=0;i<=k;i++)
    {
        if (B[i])
            cout<<A[i]<<' ';
    }
    return 0;
}


BoGo排序

不知道谁想出来的,貌似非常不实用,时间复杂度高达O(n*n!)。

Bogo排序步骤:

1.      把队列随机打乱

2.      队列有序?OK;否则,重新执行第1步。

 

如果我理解没有错,这个算法能排序好的概率是不是跟中彩票一样?


 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/ice110956/article/details/12152591

智能推荐

MySQL联合索引与索引下推图文详解_联合索引图解-程序员宅基地

文章浏览阅读3k次,点赞5次,收藏25次。联合索引的树结构、最左匹配原则、如何选择合适的索引列顺序、索引下推图文讲解_联合索引图解

nslookup-程序员宅基地

文章浏览阅读49次。nslookupserver 114.114.114.114set q=mx set q=aset q=ptrset q=ns转载于:https://www.cnblogs.com/huang99882008/p/10696756.html_nslookup时显示的server为114.114.114.114

计算机控制系统的典型类型是什么,计算机控制系统作业参考答案-程序员宅基地

文章浏览阅读2.2k次。计算机控制系统作业参考答案 (15页) 本资源提供全文预览,点击全文预览即可全文预览,如果喜欢文档就下载吧,查找使用更方便哦!9.90 积分计算机控制系统作业参考答案作业一第一章11什么是计算机控制系统画出典型计算机控制系统的方框图。答计算机控制系统又称数字控制系统,是指计算机参与控制的自动控制系统,既用算机代替模拟控制装置,对被控对象进行调节和控制控制系统中的计算机是由硬件和软件两部分组成的硬..._kkxkt

通过广域网(Intelnet)进行远程唤醒[或开机]_magic packet utility-程序员宅基地

文章浏览阅读4k次。WAN远程唤醒与LAN远程唤醒有着诸多不同,WAN远程唤醒首先需要主板、网卡等硬件的支持,需要一条有效的Intelnet连接,与Lan远程唤醒不同的是,WAN远程唤醒需要经过路由器。WAN远程唤醒与LAN远程唤醒有着诸多不同,WAN远程唤醒首先需要主板、网卡等硬件的支持,需要一条有效的Intelnet连接,与Lan远程唤醒不同的是,WAN远程唤醒需要经过路由器,因此下面我就来详细讲解如何在路由_magic packet utility

通过 PCIE Inbound-程序员宅基地

文章浏览阅读4.3k次,点赞3次,收藏23次。Inbound:PCI域访问存储器域Outbound:存储器域访问PCI域RC访问EP: RC存储器域->outbound->RC PCI域->EP PCI域->inbound->EP存储器域EP访问RC:EP存储器域->outbound->EP PCI域->RC PCI域->inbound->RC存储器域Out即出去,发起访问的一侧,需要进行outbound,去访_pcie inbound

小程序 报错之 thirdScriptError ..... is not a function 的解决方法_京东小程序 thirdscripterror #bound-程序员宅基地

文章浏览阅读9.9k次。参考网址https://blog.csdn.net/fangkang7/article/details/81943614我的解决办法判断 数据为空的情况下为 []如下所示success: function (res) { var contentlist = res.data.school; if (!contentlist) { contentli..._京东小程序 thirdscripterror #bound

随便推点

苹果安卓鸿蒙对比,鸿蒙OS对比iOS,华为再次“超越”,流畅度大幅领先苹果!...-程序员宅基地

文章浏览阅读264次。随着越来越多的细节被曝光,鸿蒙系统也已经进入到了最后内测阶段。近日,华为消费者业务软件部总裁公开王成录表示,华为手机从6月开始,可以陆续升级到鸿蒙系统正式版。这是华为官方首次明确告知正式版推动的时间,此前在2月的Mate X2发布会上,余承东曾宣称会在4月份推动鸿蒙OS。事实上,最近已经有很多用户升级到了鸿蒙系统,不过需要注意的是,现在用户们使用的都是内测版和公测版。前不久,华为刚开启了鸿蒙OS ..._苹果系统,安卓系统,华为鸿蒙系统排名

postgresql upsert 的实现_pqsql upsert-程序员宅基地

文章浏览阅读3.3k次。os: ubuntu 16.04db: postgresql 9.6.8postgresql upsert 是从 9.5 开始引入的功能,语法中并没有 upsert 这个关键字,是通过 insert into 来实现的。所以现在 postgresql 也可以使用 insert into 来实现 oracle 的 merge into 功能。强大,赞一个。语法# su - postgre..._pqsql upsert

计算机网络实验3.1.1·PPP基本配置与分析_ppp的基本配置-程序员宅基地

文章浏览阅读4.8k次,点赞7次,收藏41次。PPP基本配置与分析实验目的实验装置实验原理任务要求实验步骤实验过程实验目的1.掌握 PPP 特点、工作过程和基本配置方法。2.掌握 PPP PAP 鉴别的特点配置方法。3.掌握 PPP CHAP 鉴别的特点和配置方法。4.掌握 PPP IP 地址协商的配置方法。实验装置1.华为 eNSP 软件。2.ping。3.Wireshark。实验原理PPP 是目前使用最为广泛的数据链路层协议,可以在点对点链路上传输多种协议的数据。PPP 包括三个组成部分:1.将数据报封装到串行链路的方法_ppp的基本配置

win7安装sqlserver2014_sqlserver 2014 win7可以安装么-程序员宅基地

文章浏览阅读1.9w次,点赞2次,收藏22次。SQL Server2014要求:https://docs.microsoft.com/zh-cn/sql/sql-server/install/hardware-and-software-requirements-for-installing-sql-server?view=sql-server-2014第一步:下载第二步:解压第三步:管理员身份运行第四步:全新安装..._sqlserver 2014 win7可以安装么

typeid与typedef-程序员宅基地

文章浏览阅读187次。typedef可以用来定义类型的同义词。typeid是用来查看类型的,请看下面程序分析。#include&lt;iostream&gt;using namespace std;int main(){typedef int zhangxing;typedef double shuangjingdu;zhengxing a=20;shuangji..._java mysql typedef

oracle 物化视图-程序员宅基地

文章浏览阅读86次。物化视图与普通视图的区别普通视图:虚表,比较耗时物化视图:物理表,可以建索引,性能好,占数据库磁盘空间实现sql下面为每隔10秒刷新一次的视图VIEW_NAME 表示视图名称SQL 表示你要创建的sqlcreate materialized view VIEW_NAME refresh force on demand start with sysdate nextto_dat...

推荐文章

热门文章

相关标签