java算法（一）—初级排序算法

程序=数据结构+算法。对于那些构建项目的框架不是由我们来编写的，真正能判断一个项目的水平高低的是我们在其中自定义的数据结构是否方便、简洁、耦合度低；我们实现这些方法的算法是否快速、有效、不易出错。如果你想做的不是那种每天从早干到晚的搬砖工作，学会算法、品析数据结构绝对是你增长水平的必经之路。

（一）排序算法

算法和编程语言关系是紧密的，但又不仅仅只依赖于某种语言。在不考虑实现语言的情况下，我们通常有以下这些种排序方法：

1. 选择排序

2. 插入排序

3. 希尔排序

4. 归并排序

5. 快速排序

我们不仅仅只是空泛的讲述这几种排序方法，在介绍完5种排序算法之后，我们会将这些方法总结并和javaAPI进行联系。除此之外，为了方便我们对这几种排序方法的实现，我们现在这里使用了一点辅助的方法，这些辅助方法非常简单，他们存在的作用就是为了让我们的代码变得简洁。

    /**
     * 比较两个大小不同的数字，如果第一个参数比较小则返回true。
     * 
     * @param v 第一个数字
     * @param w 第二个数字
     * @return 返回比较结果
     */
    public static boolean less(int v , int w){        if(v<w) return true;        return false;
    }    /**
     * 交换数组中两个索引的内容
     * 
     * @param arr 数组
     * @param v 第一个索引
     * @param w 第二个索引
     */ 
    public static void exch(int[] arr,int v ,int w){        int temp=arr[v];
        arr[v]= arr[w];
        arr[w] = temp;
    }    /**
     * 打印数组
     * 
     * @param arr 要显示的数组
     */
    public static void show(int[] arr){        for(int i=0;i<arr.length;i++)
        System.out.println(arr[i]);
    }

（二）排序成本模型

在java中，绝大多数的元素都是对象，对这些对象的主键的描述是通过Comparable的机制来实现的，有了Comparable才有了顺序和排序的概念。那么如何去研究一个排序方法到底是快还是慢，到底有多快，到底效率如何呢？我们将从下面的几个方面来研究各个排序算法的成本。

1. 比较和交换（我们需要计算比较和交换的数量，来评判排序的成本）

2. 时间（一个排序算法所用的时间，或者在某种情况下所用的时间）

3. 额外的内存使用（有的排序方法需要使用额外的内存空间，有的则不需要）

针对某些特殊的排序算法我们会给出特殊的成本估计的方法，对于大多数的排序方法，我们都会在最后讨论这个方法在什么情况下适用——毕竟那些没用的排序早已被淘汰。

（三）选择排序

选择排序是所有排序中最为简单的一种排序算法。选择排序的核心思想就是：

在数组前端维护一个有序的子数组，每次找到后半部分无序数组中最小的元素，将其与前端结尾后的第一个无序元素交换，使这个元素变为有序。当有序部分数组元素等于总元素个数时，排序完成。

通俗的说，我们首先先找到数组中最小的那个元素，把它和第一个元素交换，如果第一个元素就是最小的元素，那么它和它自己交换。然后我们从第二个元素开始到结尾再找到最小的那个元素，将它与数组第二个元素交换，以此类推，不断地选择剩余元素中最小的那个。

1.比较和交换

选择排序有固定的比较次数N²/2，和固定的交换次数N。

对于比较次数来讲，选择排序在第一次需要从第一个元素比较到最后一个元素才能知道最小的元素是什么。在第二次，需要N-1次比较才能知道最小元素。总计需要N+(N-1)+(N-2)+ ··· + 1 = N²/2 次。

因为由于算法的编程原因，即使最小的这个元素已经在正确的位置上了，我们还是需要将它自己和自己交换位置，所以交换的次数也是固定的为N次。

2.时间

选择排序的运行时间是固定的约为N²/2次比较所需时间（N²/2的情况下，我们基本可以将交换的N次时间忽略）。如果我们在不能预估一个排序方法的运行时间时，我们现在已经至少知道了一种保底的排序方法，只要你的排序方法使用得当，它的运行时间绝对不会超过N²/2次比较的时间。

3.java实现

package Sort;/**
 * 
 * @author QuinnNorris 选择排序
 */public class Sort1 {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };        // 测试数组
        sort(arr);        // 调用排序算法
        Tool.show(arr);        // 打印
    }    /**
     * 用选择排序将arr升序排列
     * 
     * @param arr
     *            所要排列的数组
     */
    public static void sort(int[] arr) {        
    for (int i = 0; i < arr.length; i++) {            
    int min = i;            
    for (int j = i + 1; j < arr.length; j++)                
    if (Tool.less(arr[j], arr[min]))
                    min = j;
            Tool.exch(arr, min, i);
        }
    }
}

4.特点

选择排序非常简单，他有两个很鲜明的特点：
1.运行时间和输入无关
运行时间和输入无关，好听的讲就是无论多么乱的数据都会在固定的时间之内完成排序，但是更多的情况下，这种前一遍比较不能为后一遍比较提供任何价值的算法是非常费时的。夸张的讲，如果我们要完成某个几乎接近有序的数组的排序，你会发现，使用选择排序所需的时间和去排序那些无序的数组竟然是完全一样的。这在很多情况下是大家不能接受的。
2.数据移动最少
为了保证最少的交换数据，我们不断的进行比较，每次的交换都会百分之百的把一个数字放在正确的位置上。其他的任何排序方法都不具备这个特性。

（四）插入排序

在选择排序中，一个几乎有序的数组和一个完全无序的数组所需时间是一样的。插入排序则完美的解决了这个问题：

从数组的头部开始，通过不断的一次一位的比较和交换，让每个数据都能插入前端有序部分中自己合理的位置，当所有的元素都完成一遍操作后，排序完成。

我们将要排序的那个元素和前面一位元素比较，如果比前面的元素小，则交换位置，这个元素继续和再前面的元素比较，如果仍然小则继续交换，知道前面的元素小于该元素位置。这个时候，这个不断交换的元素就在这个数组中达到了自己合适的位置，刚才其他被交换的元素，都像是“向后移动一个位置”，为这个元素挪出了空间，这就是插入排序。这种排序很类似我们在打桥牌时整理牌的方法，不断地将牌按照大小从后向前插入。

1.比较和交换

在一个随机排序而且主键不重复的数组中，平均情况下插入排序需要N²/4次比较以及N²/4次交换。在最坏的情况下需要N²/2次比较和N²/2次交换，最好情况下需要N-1次比较和0次交换。
这个平均情况是怎么计算得出的呢？通常情况下，我们认为数组中的一个数字在整个数组中会被移动半个数组的长度（在平均情况下，每个数字都会移动到有序部分的中间位置，在这种情况下，数字自己的移动和被向后“推”的移动加起来长度为半个数组），在半个数组的移动算作平均情况下，我们得到N²/4的比较和交换次数。

2.时间

我们可以看出，用插入排序算法排序的时间和这个数组情况有很大关系，如果数组是非常无序的，它的速度要慢于选择排序，但是如果我们现在要排序的数组是几乎完全有序的，那么它的时间将会非常的小。就像我们手中握着一副全都排好顺序的扑克牌，这时你抽到一张梅花9，你可以非常快的将它插到你的手牌中。

1. 数组中每个元素距离他的最终位置不远

2. 一个有序数组的大数组接一个小数组

3. 数组中只有几个元素的位置不正确

上述的三种情况下，使用插入算法会非常非常有效。事实上，当顺序错误的数量很少的时候，插入排序会比其他任何排序算法都快。

3.java实现

package Sort;/**
 * 
 * @author QuinnNorris 插入排序
 */public class Sort2 {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };        // 测试数组
        sort(arr);        // 调用排序算法
        Tool.show(arr);        // 打印
    }    /**
     * 用插入排序将arr升序排列
     * 
     * @param arr
     *            所要排列的数组
     */
    public static void sort(int[] arr) {        
    for (int i = 0; i < arr.length; i++)            
    for (int j = i; j > 0; j--)                
    if (Tool.less(arr[j], arr[j - 1]))
                    Tool.exch(arr, j, j - 1);
    }
}

4.特点

在插入排序中，因为他的速度和原有的序列有很大关系。在这里，我们将在原序列中位置顺序颠倒的一对数字叫做倒置，这只是我们起的一个名字，它表示两个数字的位置是错误的（a应该在b的前面，但是在数组中a在b的后面，无论a与b相隔多远，都可以称a、b是一个倒置）。插入排序具有以下几点特性：

1. 交换和比较的次数相同

2. 比较的次数大于等于倒置的数量

3. 比较的次数小于等于倒置数量加上数组的大小再减一

除此之外，插入排序作为一种初级排序算法，会在之后的高级排序算法中作为一个中间算法频频出现，我们会在以后再见到他。

（五）选择算法和插入算法比较

这两种算法是如此的相似，以至于我们非常好奇想将他们比较一番。对于随机排序无重复的数组，插入排序和选择排序的运行时间都是平方级别的，所以两者只比应该是一个较小的常数。

（六）希尔排序

我们接下来要介绍的一种排序算法并不属于初级排序算法，但是它实际上是运用了插入算法的技术来实现的，我们不妨在这里一起讨论一下。希尔排序是指：

通过由大到小的制定一个常量h的值，通过插入排序使数组中任意间隔为h的元素都是有序的。不断减小h的大小，直到h=1，使得整个数组都是有序的。

我们还是用桥牌来做比喻，一开始的时候你手上有一副毫无顺序的牌，你可以一个一个的去找位置，但是这时你突然觉得这种方法太慢了，于是你打算先粗略的筛一遍。你把一些牌放的有顺序，但是其他有的牌并没有顺序，就这样，你筛了几遍你的牌最后让所有的手牌都变得有序。这就是希尔排序。

在我们需要排序的数组成千上万时，我们通常可以去采用希尔排序。
在希尔排序中，我们先定义一个h，我们以h为间隔，划分出一个子数组，我们用插入算法将这个子数组排序。然后不断地让h变小，我们再去将新的数组排序，最后当h为1时，这一遍排序让所有的数据都有序。

1.优势

那么希尔排序有什么优势呢？我们知道，插入排序的优势是对于已经部分有序的序列排序极快，而且对于小型数组排序速度很快。我们的希尔排序就是结合了这两个优点。在h较大的时候，整个数组比较小，插入排序较快，在h较小的时候整个数组已经渐渐趋于有序，这时使用插入排序也是非常好的选择。可以说希尔排序集合了这两个优点，整体的时间是比较快的。

2.时间

对于希尔排序，我们并不打算按照我们上面的分析方式来分析，原因如下。首先希尔排序非常难以研究交换和比较，因为关键因素在于h，h是一个常量，我们可以通过设置不同的h来改变这种跳跃的间隔。而且并没有一个明确的解释：h到底遵循什么规律效果最优（通常我们可以采用3*h+1 即：1，4，13，40，121，364…这组数字来作为h）。h既然不能被确定那么也就没有什么最优时间的说法。

3.实际应用

有经验的程序员有的时候会采用希尔排序，因为对于中等大小的数组，希尔排序的运行时间是可以接受的。他的代码量很小，而且不用使用额外的内存空间。或许我们确实有更快的算法但是对于很大的N，他们很有可能只比希尔排序快了不到两倍的时间。而且非常的复杂。如果你需要排序但是没有一个系统的排序函数，或者可以考虑使用希尔排序，然后再去考虑是否将它替换成更高级的排序方法。

程序=数据结构+算法。对于那些构建项目的框架不是由我们来编写的，真正能判断一个项目的水平高低的是我们在其中自定义的数据结构是否方便、简洁、耦合度低；我们实现这些方法的算法是否快速、有效、不易出错。如果你想做的不是那种每天从早干到晚的搬砖工作，学会算法、品析数据结构绝对是你增长水平的必经之路。

以上就是java算法（一）—初级排序算法的内容，更多相关内容请关注PHP中文网（www.php.cn）！