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;
	}
	
}