2017-12-07发表数据结构和算法

数据结构（四）归并排序和快速排序

归并排序和快速排序都是时间复杂度为 O(nlogn) 的排序算法。

归并排序

要将一个有16个元素的数组排序，可以先将它分成两半，每一半8个元素，分别排序，然后将排序好的两个8元素的结果归并起来。

要将一个有8个元素的数组排序，可以先将它分成两半，每一半4个元素，分别排序，然后将排序好的两个4元素的结果归并起来。

要将一个有4个元素的数组排序，可以先将它分成两半，每一半2个元素……

基于这种思想的排序，就是归并排序。

MergeSort1

MergeSort2

实现思路

从上面的图可以看到，归并排序的两个步骤：

第一步：分治

即不断地把长数组拆分成两半，直到只有2个了，再排大小。

实现分治非常简单，用递归调用自己，大数组自然会被划分到最小：

public static void mergeSort(int[] arr, int low, int high){
    if (high <= low ) return;

    // 找到中间点
    int mid = (low + high) / 2;

    // 排序左半边
    mergeSort(arr, low, mid);

    // 排序右半边
    mergeSort(arr, mid+1, high);

    // 左右两边归并
    merge(arr, low, mid, high);
}

第二步：归并

把很多个排好的两半，重新拼接起来，拼到最后，就把所有元素排序好了。

如何实现呢？

假设原来要排序的数组为a[]，可以先将a[] 全部复制到辅助数组 aux[] 中。然后依次判断：

左半边是否用尽，如果用尽，取右半边的元素，否则2
右半边是否用尽，如果用尽，取左半边的元素，否则3
右半边的当前元素是否小于左半边的当前元素，如果是，取右半边的元素，否则取左半边的元素

public static void merge(int[] arr, int low, int mid, int high){
    int left = low;
    int right = mid + 1;

    // 将数组复制到一个新的临时数组中
    int[] tempArr = new int[high+1];
    for (int i = low; i <= high; i++) {
        tempArr[i] = arr[i];
    }

    for (int i = low; i <= high; i++) {
        // 左半边是否用尽，如果用尽，取右半边的元素
        if ( left > mid ) arr[i] = tempArr[right++];

        // 右半边是否用尽，如果用尽，取左半边的元素
        else if ( right > high ) arr[i] = tempArr[left++];

        // 右半边的当前元素是否小于左半边的当前元素，如果是，取右半边的元素
        else if ( tempArr[right] < tempArr[left]) arr[i] = tempArr[right++];

        // 否则取左半边的元素
        else arr[i] = tempArr[left++];
    }

}

归并排序完整实现

public static void mergeSort(int[] arr, int low, int high){
    if (high <= low ) return;

    // 找到中间点
    int mid = (low + high) / 2;

    // 排序左半边
    mergeSort(arr, low, mid);

    // 排序右半边
    mergeSort(arr, mid+1, high);

    // 左右两边归并
    merge(arr, low, mid, high);
}

public static void main(String[] args) {
    int[] testArr = {3,7,42,8,0,5, 66, 3, 80, 11, 2};
    System.out.println(Arrays.toString(testArr));

    mergeSort(testArr,0, testArr.length - 1);

    System.out.println(Arrays.toString(testArr));
}

快速排序

在归并排序中，我们将一个数组分为两半，每一半又再分为两半，分到最后再一步步归并。

快速排序和归并排序是互补的：快速排序先选定一个元素，比这个元素小的放在左边，比这个元素大的放在右边，每一半，也都选一个元素，比它小的放左边，比它大的放右边。不断地选、分下去。

如何切分

假设我们选取数组的第一个元素为切分（partition）元素，如何把小于它的元素放在左边，大于它的元素放在右边呢？

选取第一个元素 arr[low] 为参考元素
从左边向右，每一个元素都跟参考元素做比较，直到找到比参考元素大的
从右边向左，每一个元素都跟参考元素做比较，直到找到比参考元素小的
交换第 2，3 步的两个元素（也就是把大的放右边、小的放左边）
重复 2、3、4，直到扫描完
将参考元素arr[low]放到中间位置

private static int partition(int[] arr, int low, int high) {
        // 1.选取第一个元素为参考元素
        int refer = arr[low];

        int left = low;
        int right = high + 1 ; // 这里要加一

        // 重复 2.3.4
        while (true){

            // 2.从左边向右，每一个元素都跟参考元素做比较，直到找到比参考元素大的
            while ( arr[++left] < refer ){
                // 如果到达最右了，不再向右
                if (left == high) break;
            }

            // 3.从右边向左，每一个元素都跟参考元素做比较，直到找到比参考元素小的
            while ( arr[--right] > refer ){
                // 如果到达最左了，不再向左
                if (right == low) break;
            }

            // 5. 检查是否扫描完
            if (left >= right) break;

            // 4. 交换刚刚两个元素
            Swap.swap(arr, left, right);

        }

        // 6. 将参考元素`arr[low]`放到中间位置
        Swap.swap(arr, low, right);
        return right;
    }

快速排序完整实现

先切分，再排序左半边，排序右半边
排序左半边的时候，又会切分，排序左半边右半边，排序右半边的时候，也会切分，排序左半边右半边
递归下去

package sort;

import Jutils.Swap;

import java.util.Arrays;

/**
 * 快速排序
 *
 * 思路：先选定一个元素，比这个元素小的放在左边，比这个元素大的放在右边
 *       挑出来的每一半，也都选一个元素，比它小的放左边，比它大的放右边。
 *       不断地选、分下去。
 */

public class QuickSort {

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

        if (high <= low) return;

        // 切分，refer 是参考元素
        int refer = partition(arr, low, high);

        // 将切分的左半部分快排
        quickSort(arr, low, refer - 1);

        // 将切分的右半部分快排
        quickSort(arr, refer + 1, high);
    }

    public static void main(String[] args) {
        int[] testArr = {3,7,4,8,0,1};
        System.out.println(Arrays.toString(testArr));

       quickSort(testArr, 0, 5);

        System.out.println(Arrays.toString(testArr));
    }

}

#数据结构和算法