冒泡 选择 插入排序算法总结

时间:6年前   阅读:4879

概述:

由于排序非常重要而且可能非常耗时,所以它已经成为一个计算机科学中广泛研究的课题,

而且人们的确已经研究出一些非常成熟的方法。在这篇文中将看到三个简单排序的算法:

冒泡,选择,插入排序,还有另外两种高级排序算法,希尔和快速排序。插入排序比较重要,

它比冒泡和选择排序有时更有效率,而且对于小规模和基本有序的文件,插入排序算法能比

快速排序算法更为有效。

这篇文中阐述三种简单排序算法,下一篇文中阐述高级排序算法。

从三个角度来阐述算法:代码,执行效率(大O表示法)以及不变性。

不变性:在许多算法中,有些条件在算法执行时是不变的,这些条件被称为不变性。认识

不变性对理解算法是有用的。在一定的情况下它们对调试也有用;可以反复检查不变性是否

为真,如果不是的话就标记出错。

阐述语言:Java

冒泡排序

冒泡排序算法运行起来非常慢,但在概念上它是排序算法中最简单的,因此冒泡

排序算法在刚开始研究排序技术时是一个非常好的算法。

代码:

//冒泡排序

    public void bubbleSort()

    {

        int out,in;

        for(out = nElms - 1;out > 0;out --)

            for(in = 0;in < out; in++)

                if(array[in] > array[in + 1])

                    swap(in,in+1);

    }

 不变性:它的不变性是指out右边的所有数据项有序,在算法的整个运行过程中这个条件始终为真。

效率:

比较次数:数组中有N个数据项,第一趟排序中有N-1次比较,第二趟有N-2次比较,如此类推,

最后一趟需要1次比较

故比较次数为:(N-1)+ (N-2) + ... + 1 = N(N-1)/2

交换次数为 0 - N(N-1)/2,两个极端情况,完全有序和完全逆序时交换次数分别为0和N(N-1)/2。,

故平均比较次数为:N(N-1)/4

大O表示法要忽略常数,故BubbleSort的时间复杂度为0(N²)

ps:无论何时,只要看到一个循环嵌套在另一个循环里,就可以怀疑这个算法的运行时间为

0(N²)时间级别。

选择排序

算法描述:

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全

部待排序的数据元素排完。

与冒泡比较:

交换的复杂度降为0(N),不幸的是比较复杂度仍然保持为0(N²)

代码:

//选择排序

    public void selectSort()

    {

        int out,in,min;

        for(out = 0;out < nElms - 1;out ++)

        {

            min = out;

            for(in = out + 1;in < nElms;in ++)

                if(array[in] < array[min])

                    min = in;

            swap(min,out);

        }

    }

不变性:在算法执行过程中,下标小于或等于out的位置的数据项总是有序的。

效率:

比较次数为:N(N-1)/2

交换次数为:N/2

仍然维持在0(N²)。但是如果交换的时间级比比较的时间级大得多时,选择排序实际上是相当

快的。

ps:综上,实际编程中,能用选择排序的时候就不要用冒泡排序,冒泡排序好像只是学习排序

算法的一块垫脚石。

插入排序

算法描述:在未排序序列中,依次循环将元素插入到已排序的序列当中去。知道所有的数据

序列有序。

代码:

//插入排序

    public void insertionSort()

    {

        int out,in;

        for(out = 1;out < nElms ; out ++)

        {

            int temp = array[out];

            in = out;

            while(in > 0 && array[in - 1] >= temp )

            {

                array[in] = array[in - 1];

                --in;

            }

            array[in]  = temp;

        }

    }

不变性:在外层循环每趟结束时,比out变量下标号小的数据项都是局部有序的。

效率:

比较次数:每次循环最多的比较次数依次为1,2,......,N-1.最坏情况下和冒泡排序一样,次数为N(N-1)/2,

那平均只有一半数据项进行了比较,故比较次数为N(N-1)/4.

复制次数:复制次数大致等于比较次数,即为N(N-1)/4.

用大O表示法,那仍然维持在O(N²)。

三种算法比较:

从比较次数而言:

冒泡和选择排序的时间复杂度是一样的,而插入排序的效率是冒泡和选择排序的两倍。

从交换(复制)次数而言:

插入排序的效率是冒泡排序的3倍(一次交换的复杂度约等于三次复制,冒泡排序中是要交换,而插入排序时要复制就可以了)。

插入排序相对选择排序而言,如果都转化成复制的效率,选择时间复杂度为:选择排序为(N/2)*3,而插入排序为N(N-1)/4,

并体现不了插入排序的优势。

总结:

除非手边没有算法书可参考,一般情况几乎不太使用冒泡排序。

在大多数情况下,假设当数据量比较小或基本上有序时,插入排序算法是三种简单排序算法中

最好的选择。在实际应用中插入排序使用时最多的。

本站声明:网站内容来源于网络,如有侵权,请联系我们https://www.qiquanji.com,我们将及时处理。

微信扫码关注

更新实时通知

上一篇:期权新手入门:投资进场前必须了解的五要点你清楚吗?

下一篇:50ETF期权杠杆和期货杠杆有什么区别?

网友评论

请先 登录 再评论,若不是会员请先 注册