合并排序和快速排序

• 归属：分治法
• 算法复杂度：

• 合并排序：θ(nlogn)
• 快速排序：一般是O(nlogn)

• 稳定性：合并排序稳定，快速排序不稳定

• 思想：

  • 合并排序：
    1. 对于一个需要排序的数组，将它一分为二，并对每一个子数组进行排序，然后再将两个子数组合并成一个有序数组。
    2. 对两个有序数组的合并：两个下标分别指向两个待合并数组的第一个元素，然后比较大小，将较小的元素添加到一个新创建的数组中。接下来被复制数组下标右移。按照这种思想将两个数组合并。

  • 快速排序：取一个有startIndex、endIndex排序的数组
    1. 取一个数作为一个数组的中值（下面算法使用的“三平均划分法”），让它跟startIndex对应元素交换。
    2. 在startIndex小于endIndex的情况下，startIndex开始向右移动，直到遇到比中值大的元素为止；endIndex开始向左移动，直到遇到比中值小的到元素位置。交换startIndex和endIndex的元素的位置。即完成一次元素划分（左侧元素小，右侧元素大）
    3. 再对左侧数组和右侧数组从步骤1重复执行，越分越小，最后实现完整排序。

• 算法：

    /**
     * 合并排序
     */
    public static void mergeSort(int[] nums) {
        final int length = nums.length;
        if (length > 1) {
            int aLength = length >> 1;
            int bLength = length - aLength;
            int a[] =  new int[aLength];
            int b[] = new int[bLength];
            System.arraycopy(nums, 0,a, 0, aLength);
            System.arraycopy(nums, aLength, b, 0, bLength);

            mergeSort(a);
            mergeSort(b);
            merge(a, b, nums);
        }
    }

    /**
     * 合并a、b两个有序数组到old中
     * @param a 待合并有序数组
     * @param b 待合并有序数组
     * @param old 合并目标数组
     */
    public static void merge(int[] a, int[] b, int old[]) {
        int aIndex = 0, bIndex = 0, oldIndex = 0;
        while (aIndex < a.length && bIndex < b.length) {
            if (a[aIndex] <= b[bIndex]) {
                old[oldIndex] = a[aIndex];
                aIndex++;
            } else {
                old[oldIndex] = b[bIndex];
                bIndex++;
            }
            oldIndex++;
        }

        //把剩下还未放入old数组中的元素放进去
        if (aIndex == a.length) {
            System.arraycopy(b, bIndex, old, oldIndex, old.length - oldIndex);
        } else {
            System.arraycopy(a, aIndex, old, oldIndex, old.length - oldIndex);
        }
    }

  /* ---------------------------------------------------------------------------*/

    /**
     * 快速排序一般考虑的是数组比较大的情况
     * 在数组元素很少的情况下应考虑插入排序
     * 或者说在子数组元素在5~15个的时候改用插入排序
     */
    public static void fastSort(int[] nums,int startIndex, int endIndex) {
        //数组长度小于10时采用插入排序
        if (endIndex- startIndex < 10) {
            insertionSort(nums);
        } else {
            //找到中值，并和首值交换
            //如果只采用快排的话，请加上下面一句话，不然会数组下标越界
            //if((endIndex - startIndex) < 2) return;
            int centreIndex = selectCentreIndex(nums, startIndex, endIndex);
            swap(nums, startIndex, centreIndex);
            int partitionCentreIndex = theHoarePartition(nums, startIndex, endIndex);
            fastSort(nums, startIndex, partitionCentreIndex - 1);
            fastSort(nums, partitionCentreIndex, endIndex);
        }
    }

    /**
     * 这里使用三平均划分法
     * 还有随机划分法
     */
    private static int selectCentreIndex(int[] nums, int startIndex, int endIndex){
        int centreIndex = ((endIndex - startIndex) >> 1) + startIndex;
        int a = nums[startIndex];
        int b = nums[endIndex];
        int c = nums[centreIndex];

        int result;
        if (a > c) {
            if (b > a) {
                result = startIndex;
            } else {
                if (b > c) {
                    result = endIndex;
                } else {
                    result = centreIndex;
                }
            }
        } else {
            if (b > c) {
                result = centreIndex;
            } else {
                if (b > a) {
                    result = endIndex;
                } else {
                    result = startIndex;
                }
            }
        }
        return result;
    }

    /**
     * 交换a, b下标对应元素的位置
     */
    private static void swap(int nums[], int aIndex, int bIndex) {
        int c = nums[aIndex];
        nums[aIndex] = nums[bIndex];
        nums[bIndex] = c;
    }

    /**
     * 霍尔划分
     * 以首元素为中值实现数组划分
     */
    private static int theHoarePartition(int[] nums, int startIndex, int endIndex) {
        int centreIndex = startIndex;
        int centreValue = nums[startIndex];
        startIndex++;
        while (startIndex <= endIndex) {
            while (nums[startIndex] <= centreValue) startIndex++;
            while (nums[endIndex] >= centreValue) endIndex--;
            swap(nums, startIndex, endIndex);
        }
        //撤销最后一次交换
        swap(nums,startIndex, endIndex);
        //将中值交换到数组中间来（左小右大）
        swap(nums, centreIndex, endIndex);
        return endIndex;
    }