java排序算法（二）-归并排序、快速排序

排序算法-归并排序

• 前言
• 归并排序
• 快速排序

前言

此文内容纯手写，为了记录学习中的一些算法逻辑，如有错误请指出。

归并排序

归并排序，顾名思义就是先拆分，再合并。

归并排序的要点：先拆分，然后合并。

（下面的left right mid 都为下标位置。）

拆分：每次将数组拆分为左右两部分，一直拆分到左边的下标等于右边的下标时就不再拆分，开始返回。

合并：将左右两边的数组合并，合并时依次按左右两边下标的首个位置开始比较，数值小的按顺序赋值到temp数组。

一直到左右两边下标达到mid或right的位置则停止，然后将没到达mid或right的下标重新遍历，然后依次加入到

temp数组（这里加入时肯定是有序的，因为左右两边的下标表示的区间内的数肯定是有序的），都遍历进temp后，

再依次将temp中的数一一赋值进原数组arr对应的当次递归的left到right的位置，则此次递归的left到right位置就排好序了。

例如：

4,2,3,1

拆分：

4,2 3,1

拆分：

4 2 3 1

合并：

2<4 temp = {2}

左边还剩4，直接加入到temp = {2,4}

1<3 temp = {1}

左边还剩3，直接加入到temp = {1,3}

2,4 1,3

合并：

1<2则 temp = {1}

2,4 3 temp = {1}

2<3则 temp = {1,2}

4 3 temp = {1,2}

3<4则 temp = {1,2,3}

右边都加入完了，左边的2,4中还剩一个4，那么直接加入到temp = {1,2,3,4}

这样就排序完了。

下面见代码，会比文字描述好理解一些。

package com.example.demo;

public class SortTest {

    public static void main(String[] args) {
//        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        int[] arr = {8, 7, 6, 5, 4, 3, 2, 1};
//        int[] arr = {7, 4, 1, 5, 2, 8, 4,0};
        gbSort(arr);
//        quickSort(arr);
    }
	/*
	 * 归并排序
	 * 时间复杂度：O(n*logN)
     * 空间复杂度：O(n)
     * 原地排序算法：否
     * 稳定：是
     * @param arr 要排序的数组
     */
	public static void gbSort(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        int[] temp = new int[arr.length];
        splitArr(arr, left, right, temp);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    /**
     * 拆分逻辑
     *
     * @param arr   原数组
     * @param left  拆分成两份后的左下标
     * @param right 拆分成两份后的右下标
     * @param temp  用于临时存储数据的数组
     */
    public static void splitArr(int[] arr, int left, int right, int[] temp) {
        // 递归的终止条件。
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        splitArr(arr, left, mid, temp);
        splitArr(arr, mid + 1, right, temp);
        mergeArr(arr, left, mid, right, temp);
    }
    
	/**
     * 合并逻辑
     * 递归到最深时，第一次合并的必定是数组中只有一个值的数组。
     * 这样就是直接开始比较大小然后合并
     *
     * @param arr   原数组
     * @param left  拆分成两份后的左下标
     * @param mid   中间位置下标
     * @param right 拆分成两份后的右下标
     * @param temp  用于临时存储数据的数组
     */
    public static void mergeArr(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        // 从left和right的最左边开始比较。更小的放入temp
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 上面没完全放入temp的，这里直接放入
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 上面没完全放入temp的，这里直接放入
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        k = 0;
        // 将temp里面排好序的直接放到arr的left到right的下标位置
        // 增加temp是为了临时存放合并的数值，最后直接插入arr的位置，
        // 只改变了arr中需要合并的数值，对其他下标位置不影响，降低了空间复杂度
        while (left <= right) {
            arr[left++] = temp[k++];
        }
    }
}
           

快速排序

快速排序理解起来还是稍微有点难度的，不过如果不在原地交换处理的话，那么理解难度会大大降低，下面的做法是原地交换处理的做法，具体的分析逻辑都写在了注释上，可以进行查看。

这里再分析一下非原地的做法：

找到端点point后，将左右两边的数分别用临时数组存起来，然后再依次复制到原数组到位置，这样也可以达到排序到效果，不过会增加一些空间复杂度。

例如：7,4,2,4,6,8,2,5

第一轮拆分后分别存在2个数组中 [4,2,4,2] 与 [7,6,8]，5为端点值然后将2个数组的值分别复制到原数组中，先复制小于端点的，再复制端点，再复大于端点的。

public class HelloWorld {

    public static void main(String []args) {
		int[] arr = {7,4,2,4,6,8,2,5};
		// 以下数组经过第一次分区就会体现出是一个不稳定的排序算法。
		// 因为第一个6会与3交换位置，这样就改变了顺序。
		int[] arr = {6,7,9,7,6,8,3,5};
        quickSort(arr);
		for(int i : arr){
			System.out.println(i);	
		}
    }
	
	/**
     * 快速排序
	 * 核心是：
	 * 先确定一个端点（以数组中任意一个下标都行），这里以当前数组范围最后一个下标为端点。
	 * 然后依次用数组中除开端点下标都值与端点下标都值比较，小于端点的放在左边，大于端点的放在右边
	 * 下面使用的是交换的方式，例如：
	 * 6,2,4,6,3,5
	 * 交换后为2,4,3,5,6,6
	 * 然后再让端点左右两边的数再次进行此操作
	 * 左边：2,3,4  右边6,6 这样就排序完成了
	 *
     * 时间复杂度：O(n*logN)
     * 空间复杂度：O(n)
     * 原地排序算法：是
     * 稳定：否
     * @param arr 原数组
     */
	public static void quickSort(int[] arr){
			chaifen(arr,0,arr.length-1);
	}
	
	/**
	 * 将数组以point位置拆分分组，这里point默认取right位置。
	 * 拆分后找到比point大与比point小大数，分别又数2部分，再进行递归拆分调用。
	 * 最后拆分到left>=right时， 就把最后到数组通过patition排好序了。
	 * @param arr 原数组
 	 * @param left 数组首个下标
 	 * @param right 数组末尾下标
	 */
	public static void chaifen(int[] arr,int left,int right){
			if(left >= right){
				return;
			}
		int q = patition(arr,left,right);
		chaifen(arr,left,q-1);
		chaifen(arr,q+1,right);
	}
	
	public static int patition(int[] arr,int left,int right){
		// 默认以最后到下标作为比较到端点point
		int point = arr[right];
		// i 是比point小的数要放入的位置，放入方式为与j交换位置，这样保证了是原地排序算法。
		int i = left;
		// j 是需要用来循环与point比较的下标位置，除了最后一个right下标的数不需要比较以外，
		// 所有大于left、小于right的数都需要进行依次比较。
		int j = left;
		for(;j<right;j++){
			if(arr[j]<point){
				// 要比较都j下标的值如果小于point说明是要交换到i到位置。
				// 那么让i和j交换，交换后i已经被插入小于point到数了，那么i需要++，
				// 移动到下一个待要交换待位置
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				i++;
			}
		}
		// 经过上面待循环，所有的小于point的数都交换到了<i下标到位置，
		// 当前i的位置肯定数大于或等于point的值，所以让i与point位置的值交换。
		// 交换后point左边的数小于point，point右边的数大于point，这样就进行完了一轮排序。
		int t = point;
		arr[right] = arr[i];
		arr[i] = point;
		return i;
	}
	
}