快排和归并排序概述

一、快排

1.1 基本思想

​ 快排是冒泡排序的升级，它们都属于交换排序类。

​ 快排的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序的目的。（参考自《大话数据结构》）

1.2 代码实现

//快排
class Solution {
    public int[] sortArray(int[] nums) {
        if(nums.length == 0 || nums.length == 1) return nums;
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    void quickSort(int[] nums, int left, int right) {
        if(left <= right) {
            //1. 分割
            int pivotpos = partition(nums, left, right);
            //2. 对分割好的左边的数据再进行分割
            quickSort(nums, left, pivotpos - 1);	
            //3. 对分割好的右边的数据再进行分割
            quickSort(nums, pivotpos + 1, right);
        }
    }

    //分割，实现左半部分的数据都小于右半部分的数据
    int partition(int[] nums, int left, int right) {
        int pivotpos = left;
        swap(nums, left, (left + right) / 2);

        for(int i = left; i <= right; i++) {
            if(nums[i] < nums[left]) {
                pivotpos++;
                if(i != pivotpos)	swap(nums, pivotpos, i);
            }
        }

        swap(nums, left, pivotpos);
        return pivotpos;
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

1.3 复杂度分析

1.3.1 时间复杂度

​ 快排的时间性能取决于递归的深度，可以用递归树来描述递归算法的执行情况。

​ 在最优的情况下，partition 每次都划分的很均匀，其递归树的深度就是 log2(n)，即仅需递归 log2(n) 次，每层需要比较的次数是 n，所以快排的时间复杂度最优是 n * log(n)；

​ 最坏的情况下，partition 划分的极不均匀，即树是一棵斜树，这时需要递归的深度是 n，每层需要比较的次数是 n，所以最坏的时间复杂度是 O(n^2)。

​ 平均情况：

​ T(n) = 2 T(n/2) + n;

​ 两边同时除以 n ==> T(n) / n = T(n / 2) / (n / 2) + 1

​ T(n / 2) / (n / 2) = T(n / 4) / (n / 4) + 1

​ …

​ T(2) / 2 = T(1) / 1 + 1

​ ==> T(n) / n = T(1) / 1 + log(n) ==> T(n) = n * log(n) + n ==> T(n) ≈ n * log(n)

1.3.2 空间复杂度

​ 空间复杂度主要是递归造成的栈空间的使用，最好的情况下是 log(n)，最坏的情况下 n。

1.4 稳定性分析

​ 因为快排的关键字的比较和交换都是跳跃进行的，所以快排是一种不稳定的排序算法。

​ 举例很简单：

​ 用手推到一下对 6，6，7，6，6，6， 使用快排进行排序

二、归并排序

2.1 基本思想

​ 归并排序就是利用归并的思想实现的排序算法，它的原理是假设初始序列含有 n 个记录，则可以堪称是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到 [n/2] 个长度为 2 或 1 的有序序列；再两两归并，…，如此重复，直到得到一个长度为 n 的有序序列为止，这种排序的方法称为 2 路归并。

2.2 代码分析

//归并递归实现
class Solution {
    public int[] sortArray(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(nums, temp, 0, nums.length - 1);

        return nums;
    }

    void mergeSort(int[] nums, int[] temp, int left, int right) {
        //一直到只有一个元素才进行合并
        if(left < right) {
            int mid = (left + right) / 2;
            //对左半部分进行归并排序
            mergeSort(nums, temp, left, mid);
            //对右半部分进行归并排序
            mergeSort(nums, temp, mid + 1, right);
            //两部分合并
            merge(nums, temp, left, mid, right);
        }
        
    }

    void merge(int[] nums, int[] temp, int left, int mid, int right) {
        //用来保存 num 的当前值，下面的 num 将保存归并后的值
        for(int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
    
        int i = left, j = mid + 1;
        int k = left;

        while(i <= mid && j <= right) {
            if(temp[i] < temp[j]) nums[k++] = temp[i++];
            else nums[k++] = temp[j++];
        }

        for( ; i <= mid; i++) nums[k++] = temp[i];
        for( ; j <= right; j++) nums[k++] = temp[j];

    }
}

//归并排序非递归实现
class Solution {
    public int[] sortArray(int[] nums) {
        int[] tempArray = new int[nums.length];
        int len = 1;	//len 代表当前每次合并的个数
        while(len < nums.length) {
            //把 nums 中的元素合并到 tempArray
            mergeSort(nums, tempArray, len); len *= 2;	
            //再把 tempArray 中的元素合并到 nums
            mergeSort(tempArray, nums, len); len *= 2;
        }

        return nums;
    }

    void mergeSort(int[] initArray, int[] tempArray, int len) {
        int i = 0;
        while(i + 2 * len < initArray.length) {
            //i 是合并的起点，(i + 2 * len - 1) 是合并的终点，(i + len - 1) 是中间的元素
            merge(initArray, tempArray, i, i + len - 1, i + 2 * len - 1);
            i += 2 * len;
        }

        if(i + len <= initArray.length) {	// 如果剩下的两个数组长度不一样了
            merge(initArray, tempArray, i, i + len - 1, initArray.length - 1);
        } else {	// 如果只剩下一个数组
            for(int j = i; j < initArray.length; j++) {
                tempArray[j] = initArray[j];
            }
        }
    }

    void merge(int[] initArray, int[] tempArray, int begin, int beforeEnd, int latterEnd) {
        int i = begin, j = beforeEnd + 1;
        int k = begin;

        //合并
        while(i <= beforeEnd && j <= latterEnd) {
            if(initArray[i] <= initArray[j]) {
                tempArray[k++] = initArray[i++];
            } else {
                tempArray[k++] = initArray[j++];
            }
        }

        for( ; i <= beforeEnd; i++) {
            tempArray[k++] = initArray[i];
        }

        for( ; j <= latterEnd; j++) {
            tempArray[k++] = initArray[j];
        }

    }
    
}

2.3 复杂度分析

2.3.1 时间复杂度

​ 时间复杂度为合并的深度 × 比较次数，合并深度是 log(n)，比较次数是 n，所以时间复杂度为 n * log(n)，而且归并排序不像快排一样存在斜树，所以归并排序最坏的时间复杂度也是 n * log(n)

2.3.2 空间复杂度

​ 归并排序中用到了一个辅助数组，所以递归情况的空间复杂度为 O(n + logN)，非递归的空间复杂度为 O(n)，所以在使用归并排序时要优先考虑非递归实现。

2.4 稳定性分析

合并深度是 log(n)，比较次数是 n，所以时间复杂度为 n * log(n)，而且归并排序不像快排一样存在斜树，所以归并排序最坏的时间复杂度也是 n * log(n)

2.3.2 空间复杂度

​ 归并排序中用到了一个辅助数组，所以递归情况的空间复杂度为 O(n + logN)，非递归的空间复杂度为 O(n)，所以在使用归并排序时要优先考虑非递归实现。

2.4 稳定性分析

​ 归并排序是基于两两比较的，不存在条约，所以归并排序是一种稳定的排序算法。