快速排序

2019-02-17 01:51:05来源：博客园阅读 ()

划分

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

划分算法

　　划分算法是由两个指针开始工作的，两个指针分别指向数组的两头。(这里的指针不是C++里的指针，而是指数组的数据项)在左边的指针leftPtr向右移动，右边的指针rightPtr向左移动。实际上leftPtr和lightPtr初始化时分别在第一个数据的左一位及最后一个数据项的右一位，这是因为他们工作之前他们都要分别加一和减一。

　　当leftPtr遇到比枢纽小的数据项是他继续往右移动，当遇到比枢纽大的数据项停止移动。类似的，rightPtr遇到比枢纽大的值继续往左移动，当遇到比枢纽小的数据项停止移动。然后两个数据交换位置，再继续移动，重复上述操作，直至leftPtr和rightPtr相遇。

处理异常数据

需要考虑全部数据项大于或小于枢纽，如存在这种情况可能导致数组下标越界异常，所以得给程序加上判断条件

快速排序

　　毫无疑问，快速排序是当前最流行的排序算法，在大多数情况下，快速排序都是最快的，执行时间为O(N*logN)级(只对内部排序或者说随机存储器排序，对于磁盘文件中的数据排序获取其他算法更好)。

选择枢纽

　　1.应该选择具体的一个数据项的关键字为枢纽

　　2.可以选择任意一个数据项做完枢纽。为了简便，我们假设总是选择待划分的子数组最右端的数据为枢纽

　　3.划分完成后，如果枢纽被插入到左右子数组的分界处，那么枢纽就落在排序之后的最终位置上。

　　最后一条听起来似乎不可能，但请注意，正是因为使用枢纽的关键字的值来划分数组，所以划分之后的左边子数组包含的所有数据项都小于枢纽，所有右边子数据项都大于枢纽。

"三数据项取中"划分

　　人们已经设计出了许多更好的枢纽方法。方法应该简单但能避免选择最大或最小的数据项作为枢纽的情况。选择任意一个数据项作为枢纽的确最为简单，但这并不是一个好的选择。可以检测所有数据项计算出平均值，这应该是理想的枢纽选择，但是这个过程需要比排序更长的时间，因此它不行。

　　折中的方法是选取数组中的第一个数、最后一个数及中间数取平均值，并且设此数据为枢纽。该方法被称为"三数据项取中"。查找三数据项的平均值自然比取所有数据项平均值快的多，同时也避免了在数据有序的情况下取到最大值货最小值的情况。或许存在一些特殊数据排列使得"三数据项取中"的方法效率很低，但是大多数情况下他都是一个又快又有效的方法。

　　以下为快速排序代码

public class FastSort {
    private static int[] arr;

    public static int[] sort(int[] newArr){
        arr = newArr;
        recQuickSort(0,arr.length -1);
        return arr;
    }

    private static void recQuickSort(int left, int right){
        int size = right - left + 1;
        if(size <= 3){
            manualSort(left,right);
        }else {
            int median = medianOf3(left,right);
            int partition = partitionIt(left,right,median);
            recQuickSort(left,partition -1);
            recQuickSort(partition + 1,right);
        }
    }

    private static int partitionIt(int left, int right, int median) {
        int leftPtr = left;
        int rightPtr = right -1;
        while (true){
            while (arr[++leftPtr] < median);
            while (arr[--rightPtr] > median);
            if(leftPtr >= rightPtr){
                break;
            }else {
                swap(leftPtr,rightPtr);
            }
        }
        swap(leftPtr,right -1);
        return leftPtr;
    }

    private static int medianOf3(int left, int right) {
        int center = (left + right)/2;
        if(arr[left] > arr[center]){
            swap(left,center);
        }
        if(arr[left] > arr[right]){
            swap(left,right);
        }
        if(arr[center] > arr[right]){
            swap(center,right);
        }
        swap(center,right - 1);
        return arr[right - 1];
    }

    private static void swap(int dex1, int dex2) {
        int temp = arr[dex1];
        arr[dex1] = arr[dex2];
        arr[dex2] = temp;
    }

    private static void manualSort(int left, int right) {
        int size = right -left + 1;
        if(size <= 1){
            return;
        }else  if(size == 2){
           if(arr[left] > arr[right]){
               swap(left,right);
           }
        }else {
            if(arr[left] > arr[right -1])
                swap(left,right -1);
            if(arr[left] > arr[right]){
                swap(left,right);
            }
            if(arr[right-1] > arr[right]){
                swap(right -1,right);
            }
        }
    }
}

　　以下为测试快速排序代码

@Test
    public void mergeSort(){
        int[] arr = new int[100];
        Random random = new Random();
        for(int i = 0;i < arr.length;i++){
            arr[i] = random.nextInt(1000);
        }
        System.out.println("未排序前数组：" + Arrays.toString(arr));

        arr = FastSort.sort(arr);

        System.out.println("排序后数组：" + Arrays.toString(arr));

    }

处理小划分

　　如果使用三数据项划分法，则必须要遵循快速排序算法不能执行三个或者少于三个数据项的划分规则。

　　处理小划分的另一个选择是使用插入排序。当使用插入排序时，不限制以3位切割点。把界限定为10、20或者其他数。Knuth推荐使用9位切割点。但是最好的选择值取决于计算机、操作系统、编译器等。

　　以下程序以他使用插入排序处理小于10个数据项的子数组

public class FastSort {
    private static int[] arr;

    public static int[] sort(int[] newArr){
        arr = newArr;
        recQuickSort(0,arr.length -1);
        return arr;
    }

    private static void recQuickSort(int left, int right){
        int size = right - left + 1;
        if(size < 10){
            manualSort(left,right);
        }else {
            int median = medianOf3(left,right);
            int partition = partitionIt(left,right,median);
            recQuickSort(left,partition -1);
            recQuickSort(partition + 1,right);
        }
    }

    private static int partitionIt(int left, int right, int median) {
        int leftPtr = left;
        int rightPtr = right -1;
        while (true){
            while (arr[++leftPtr] < median);
            while (arr[--rightPtr] > median);
            if(leftPtr >= rightPtr){
                break;
            }else {
                swap(leftPtr,rightPtr);
            }
        }
        swap(leftPtr,right -1);
        return leftPtr;
    }

    private static int medianOf3(int left, int right) {
        int center = (left + right)/2;
        if(arr[left] > arr[center]){
            swap(left,center);
        }
        if(arr[left] > arr[right]){
            swap(left,right);
        }
        if(arr[center] > arr[right]){
            swap(center,right);
        }
        swap(center,right - 1);
        return arr[right - 1];
    }

    private static void swap(int dex1, int dex2) {
        int temp = arr[dex1];
        arr[dex1] = arr[dex2];
        arr[dex2] = temp;
    }

    private static void manualSort(int left, int right) {
        int in,out;
        for(out = left + 1;out <= right;out++){
            int temp = arr[out];
            in = out;
            while (in > left && arr[in -1 ] >= temp){
                arr[in] = arr[in-1];
                in--;
            }
            arr[in] = temp;
        }
    }
}

测试代码：

 @Test
    public void mergeSort(){
        int[] arr = new int[100];
        Random random = new Random();
        for(int i = 0;i < arr.length;i++){
            arr[i] = random.nextInt(1000);
        }
        System.out.println("未排序前数组：" + Arrays.toString(arr));

        arr = FastSort.sort(arr);

        System.out.println("排序后数组：" + Arrays.toString(arr));

    }