概述：

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

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

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

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

快速排序算法更为有效。

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

从三个角度来阐述算法：代码，执行效率（大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/post/8505.html

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