shooting’s sky

快 速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要 小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。最坏情况的时间复杂度为O(n2)，最好 情况时间复杂度为O(nlog2n)。

   假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一趟快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

                  A[1]    A[2]    A[3]    A[4]    A[5]     A[6]    A[7]：

                    49       38      65      97      76      13       27

进行第一次交换后： 27       38      65      97      76      13       49

                  ( 按照算法的第三步从后面开始找)

进行第二次交换后： 27       38      49      97      76      13       65

                 ( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )

进行第三次交换后： 27       38      13      97      76      49       65

( 按照算法的第五步将又一次执行算法的第三步从后开始找)

进行第四次交换后： 27       38      13      49      76      97       65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

     此时再执行第三步的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27       38      13      49      76      97       65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

     快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态                       {49    38    65    97    76    13    27}   

进行一次快速排序之后划分为     {27    38    13}    49 {76    97    65}

分别对前后两部分进行快速排序   {13}   27   {38}

                               结束        结束   {49   65}   76   {97}

                                                   49 {65}        结束

                                                       结束

                         图6   快速排序全过程

1）、设有N（假设N=10）个数，存放在S数组中；

2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出 T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]， 在S[K]以后的数都大于S[K]；

3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。

如具体数据如下，那么第一躺快速排序的过程是：

数组下标： 1     2     3     4     5     6     7     8     9     10

          45    36    18    53    72    30    48    93    15     36

           I                                                        J

（1）     36    36    18    53    72    30    48    93    15     45

（2）     36    36    18    45    72    30    48    93    15     53

（3）     36    36    18    15    72    30    48    93    45     53

（4）     36    36    18    15    45    30    48    93    72     53

（5）     36    36    18    15    30    45    48    93    72     53

通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。

    /**

    * 交换指定数组a的两个变量的值

    * @param a 数组应用

    * @param i 数组下标

    * @param j 数组下标

    */

    public static void swap(int a[], int i, int j) {

        if(i == j) return;

        int tmp = a[i];

        a[i] = a[j];

        a[j] = tmp;

    }

    /**

    *

    * @param array 待排序数组

    * @param low 数组下标下界

    * @param high 数组下标上界

    * @return pivot

    */

    public static int partition(int array[], int low, int high) {

        //当前位置为第一个元素所在位置

        int p_pos = low;

        //采用第一个元素为轴

        int pivot = array[p_pos];

        for (int i = low + 1; i <= high; i++) {

            if (array[i] < pivot) {            

                p_pos++;

                swap(array, p_pos, i);

            }

        }

        swap(array, low, p_pos);

        return p_pos;

    }

    /**

     * 快速排序实现

     * @param array

     * @param low

     * @param high

     */

    public static void quickSort(int array[], int low, int high) {

        if (low < high) {

            int pivot = partition(array, low, high);

            quickSort(array, low, pivot – 1);

            quickSort(array, pivot + 1, high);

        }

    }v

下面让我们看看一个例子，它展示了按构建顺序进行合成、继承以及多形性的效果：

//: Sandwich.java
// Order of constructor calls
class Meal {
Meal() { System.out.println(“Meal()”); }
}
class Bread {
Bread() { System.out.println(“Bread()”); }
}

class Cheese {
Cheese() { System.out.println(“Cheese()”); }
}

class Lettuce {
Lettuce() { System.out.println(“Lettuce()”); }
}

class Lunch extends Meal {
Lunch() { System.out.println(“Lunch()”);}
}

class PortableLunch extends Lunch {
PortableLunch() {
System.out.println(“PortableLunch()”);
}
}

class Sandwich extends PortableLunch {
Bread b = new Bread();
Cheese c = new Cheese();
Lettuce l = new Lettuce();

Sandwich() {
System.out.println(“Sandwich()”);
}

public static void main(String[] args) {
new Sandwich();
}
} ///:

这个例子在其他类的外部创建了一个复杂的类，而且每个类都有一个构建器对自己进行了宣布。其中最重要

的类是Sandwich，它反映出了三个级别的继承（若将从Object的默认继承算在内，就是四级）以及三个成

员对象。在 main()里创建了一个Sandwich 对象后，输出结果如下：

Meal()

Lunch()

PortableLunch()

Bread()

Cheese()

Lettuce()

Sandwich()

这意味着对于一个复杂的对象，构建器的调用遵照下面的顺序：

(1) 调用基础类构建器。这个步骤会不断重复下去，首先得到构建的是分级结构的根部，然后是下一个衍生类，等等。直到抵达最深一层的衍生类。

(2) 按声明顺序调用成员初始化模块。

(3) 调用衍生构建器的主体。

构建器调用的顺序是非常重要的。进行继承时，我们知道关于基础类的一切，并且能访问基础类的任何public和protected 成员。这意味着当我们在衍生类的时候，必须能假定基础类的所有成员都是有效的。采用一种标准方法，构建行动已经进行，所以对象所有部分的成员均已得到构建。但在构建器内部，必须保证使用的所有成员都已构建。为达到这个要求，唯一的办法就是首先调用基础类构建器。然后在进入衍生类构建器以后，我们在基础类能够访问的所有成员都已得到初始化。此外，所有成员对象（亦即通过合成方法置于类内的对象）在类内进行定义的时候（比如上例中的b，c 和l），由于我们应尽可能地对它们进行初始化，所以也应保证构建器内部的所有成员均为有效。若坚持按这一规则行事，会有助于我们确定所有基础类成员以及当前对象的成员对象均已获得正确的初始化。