第七章 高级排序

希尔排序：

插入排序的缺点是复制的次数太多，如果数据开始时是相对有序的，那么插入排序的效率就能提高很多。希尔排序基于插入排序，通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能大跨度地移动。当这些数据项排过一趟序之后，希尔排序算法减小数据项的间隔再进行排序，依此进行下去。进行这些排序时数据项之间的间隔被称为增量，并且习惯上用字母h表示。常用的话值序列用公式h=h*3+1产生。

       希尔排序比插入排序快很多，原因是，当h值大的时时候，数据项每一趟排序需要移动的元素的个数很少，但是数据项移动的距离很长。这是非常有效率的。当h减小时，每一趟排序需要移动的元素的个数增多。但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率这么高。希尔排序的代码：

class shellShort 
{
    private static long[] theArray;
    private static int nElems;

    public static void display()
    {
        System.out.print("A=");
        for (int j=0; j<nElems; j++)
        {
            System.out.print(theArray[j] + " ");
        }
        System.out.println("");
    }

    public static void shellSort()
    {
        int inner,outer;
        long temp;

        int h = 1;
        while (h <= nElems/3)    //find initial value of h
        {
            h = h*3 + 1;
        }

        while (h>0)        //decreasing h, util h=1
        {
            //h-sort the file
            for (outer=h; outer<nElems; outer+=h)
            {
                temp = theArray[outer];
                inner = outer;

                // one subpass(eg 0,4,8)
                while (inner > h-1 && theArray[inner-h] >= temp)
                {
                    theArray[inner] = theArray[inner-h];
                    inner -= h;
                }

                theArray[inner] = temp;
            }//end for

            h = (h-1)/3;        //decrease h
        }    //end while
    }    //end shellSort()
    
    public static void main(String[] args) 
    {
        //System.out.println("Hello World!");
        theArray = new long[1000];
        for (int j=0; j<1000; j++)
        {
            long n = (int)(java.lang.Math.random()*99);
            theArray[j] = n;
            nElems++;
        }

        //shellShort.display();
        System.out.println(new java.util.Date());
        shellShort.shellSort();
        System.out.println(new java.util.Date());
        //shellShort.display();
    }
}

快速排序：

划分是快速排序的根本机制，划分数据就是把数据分为两组，使所有关键字大于特定值得数据项在一组，使所有关键字小于特定值的数据项在另一组。

       划分算法由两个指针开始工作，两个指针分别指向数组的两头。在左边的指针，leftPtr，向右移动，而在右边的指针，rightPtr，向左移动。当leftPtr遇到比枢纽小的数据项时，它继续向右移，因为这个数据项的位置已经处在数组的正确一边了，但是当遇到比枢纽大的数据时，它就停下来。类似地，当rightPtr遇到大于枢纽的数据项时，它继续左移，但是当发现比枢纽小的数据项时，它就停下来。这可以对两个指针用分别用一个循环来实现，当两个指针都指着数组的错误一方位置上的数据项，就交换这两个数据项。然后重复之前的指针移动及数据项交换动作。直到两个指针最终相遇的时候后，划分过程结束。

       快速排序算法在大多数情况下都是最快的，执行时间为O（N*LogN）级。快速排序算法本质上通过吧一个数组划分为两个子数组，然后递归地调用自身为每个子数组进行快速排序来实现的。算法要解决的问题是选择合适的枢纽，并且对小的划分区域进行排序。一般取数组左端、右端、中部的三个数中的中间值作为枢纽。

       快速排序代码：

class QuickSort2 
{
    private static long[] theArray;
    private static int nElems;

    public static void display()
    {
        System.out.print("A=");
        for (int j=0; j<nElems; j++)
        {
            System.out.print(theArray[j] + " ");
        }
        System.out.println("");
    }

    public static void quickSort()
    {
        recQuickSort(0, nElems - 1);
    }

    public static void recQuickSort(int left, int right)
    {
        int size = right-left+1;
        if (size <= 3)            //manual sort if small
        {
            manualSort(left, right);
        }

        else                    //quick sort if large
        {
            long median = medianOf3(left, right);    //median item
                                            //partition range
            int partition = partitionIt(left, right, median);
            recQuickSort(left, partition-1);//sort left side
            recQuickSort(partition+1, right);//sort right side
        }
    }    //end recQuickSort()

    public static long medianOf3(int left, int right)
    {
        int center = (left+right)/2;
                                    //order left & center
        if(theArray[left] > theArray[center])
            swap(left,center);
                                    //order left & right
        if(theArray[left] > theArray[right])
            swap(left, right);
                                    //order right & center
        if(theArray[center] > theArray[right])
            swap(center, right);

        swap(center, right-1);        //put pivot on right
        return theArray[right-1];
    }//end medianOf3()

    public static int partitionIt(int left, int right, long pivot)
    {
        int leftPtr = left;                //right of first elem
        int rightPtr = right-1;            //left of pivot

        while (true)
        {
                                            //find bigger item
            while (theArray[++leftPtr] < pivot)
            {
                ;
            }
                                            //find smaller item
            while (theArray[--rightPtr] > pivot)
            {
                ;
            }

            if (leftPtr >= rightPtr)        //if pointers cross,partition done
            {
                break;
            }
            else                            //not crossed, so swap elements
                swap(leftPtr, rightPtr);
        }//end while(true)

        swap(leftPtr, right-1);                //restore pivot
        return leftPtr;                        //return pivot location
    }

    public static void swap(int dex1, int dex2)    //swap two elements
    {
        long temp;
        temp = theArray[dex1];
        theArray[dex1] = theArray[dex2];
        theArray[dex2] = temp;
    }

    public static void manualSort(int left, int right)
    {
        int size = right-left+1;
        if(size <= 1)
            return;            //no necessary sort
        if(size == 2)
        {                    //2-sort left and right
            if(theArray[left] > theArray[right])
                swap(left, right);
            return;
        }
        else
        {
            if(theArray[left] > theArray[right-1])
                swap(left, right-1);
            if(theArray[left] > theArray[right])
                swap(left, right);
            if(theArray[right-1] > theArray[right])
                swap(right-1, right);
        }
    }//end manualSort()
    
    public static void main(String[] args) 
    {
        //System.out.println("Hello World!");
        theArray = new long[16];
        for (int j=0; j<16; j++)
        {
            long n = (int)(java.lang.Math.random()*199);
            theArray[j] = n;
            nElems++;
        }

        QuickSort2.display();
        //System.out.println(new java.util.Date());
        QuickSort2.quickSort();
        QuickSort2.display();
    }
}