Java 數據結構與算法系列精講之排序算法

Posted on by

概述

從今天開始, 小白我將帶大傢開啟 Java 數據結構 & 算法的新篇章.

冒泡排序

冒泡排序 (Bubble Sort) 是一種簡單的排序算法. 它重復地遍歷要排序的數列, 一次比較兩個元素, 如果他們的順序錯誤就把他們交換過來. 遍歷數列的工作是重復地進行直到沒有再需要交換, 也就是說該數列已經排序完成. 這個算法的名字由來是因為越小的元素會經由交換慢慢 “浮” 到數列的頂端.

冒泡排序流程:

  • 通過比較相鄰的元素, 判斷兩個元素位置是否需要互換
  • 進行 n-1 次比較, 結尾的元素就會是最大元素
  • 重復以上冒泡過程 n 次

代碼實現:

import java.util.Arrays;

public class bubble {

    public static void main(String[] args) {

        // 創建數據
        int[] array = {426,375474,8465,453};

        // 實現排序
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(bubbleSort(array)));
    }

    public static int[] bubbleSort(int[] array) {
        // 如果數組為空, 返回
        if (array.length == 0){
            return array;
        }

        // 執行冒泡過程n次, n為數組長度
        for (int i = 0; i < array.length; i++) {

            // 冒泡過程
            for (int j = 0; j < array.length - 1 - i; j++) {

                // 判斷j索引的元素是否比j+1索引的元素大
                if (array[j+1] < array[j]) {
                    // 交換位置
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
}

輸出結果：

[426, 375474, 8465, 453]
[426, 453, 8465, 375474]

插入排序

插入排序 (Insertion Sort) 是一種簡單直觀的排序算法. 它的工作原理是通過構建有序序列, 對於未排序數據, 在已排序序列中從後向前掃描，找到相應位置並插入. 插入排序在實現上, 在從後向前掃描過程中, 需要反復把已排序元素逐步向後挪位, 為最新元素提供插入空間.

插入排序流程:

  • 從第二個元素開始, 從後往前掃描
  • 逐個比較元素大小, 之道插入到合適的位置
  • 重復以上步驟 n-1 次

代碼實現:

import java.util.Arrays;

public class insert {

    public static void main(String[] args) {

        // 創建數據
        int[] array = {426,375474,8465,453};

        // 實現排序
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(insertionSort(array)));
    }

    public static int[] insertionSort(int[] array) {

        // 如果數組為空, 返回
        if (array.length == 0)
            return array;

        // 待排序元素
        int current;

        // 執行插入過程n-1次
        for (int i = 0; i < array.length - 1; i++) {

            // 指定待排序元素
            current = array[i + 1];

            int preIndex = i;

            // 執行插入過程, 往前一個個比對
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }

            // 插入元素
            array[preIndex + 1] = current;
        }
        return array;
    }
}

輸出結果:

​​​[426, 375474, 8465, 453]
[426, 453, 8465, 375474]

歸並排序

歸並排序 (Merge Sort) 是一種建立在歸並操作上的算法, 是分治的一個經典應用.

歸並排序流程:

  • 把數組拆分成兩個 n/2 長度的子序列
  • 對這兩個子序列分別采用歸並排序
  • 將排序好的序列合並成最終序列

代碼實現:

import java.util.Arrays;

public class merge {

    public static void main(String[] args) {

        // 創建數據
        int[] array = {426,375474,8465,453};

        // 實現排序
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(mergeSort(array)));
    }

    public static int[] mergeSort(int[] array) {

        // 如果數組長度小於2, 返回
        if (array.length < 2) {
            return array;
        }
        
        // 分治
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    public static int[] merge(int[] left, int[] right) {

        // 創建數組用於存放合並後的序列
        int[] result = new int[left.length + right.length];


        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            // 左序列取完
            if (i >= left.length)
                result[index] = right[j++];
            // 右序列取完
            else if (j >= right.length)
                result[index] = left[i++];
            // 左序列的第i個大於有序列的第j個
            else if (left[i] > right[j])
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }
}

輸出結果:

[426, 375474, 8465, 453]
[426, 453, 8465, 375474]

快速排序

快速排序 (Quicksort) 通過一趟排序將要排序的數據分割成獨立的兩部分, 其中一部分的所有數據都比另外一部分的所有數據都要小, 然後再按此方法對這兩部分數據分別進行快速排序, 整個排序過程可以遞歸進行, 以此達到整個數據變成有序序列.

​​

快速排序流程:

  • 從數組中挑出一個元素作為基準 (Pivot), 通常為第一個或者最後一個元素將比基準元素
  • 小的值放到基準前面, 比基準元素大的值放到基準後面
  • 遞歸進行分區操作

代碼實現:

import java.util.Arrays;

public class quick {

    public static void main(String[] args) {

        // 創建數據
        int[] array = {426, 375474, 8465, 453};

        // 實現排序
        System.out.println(Arrays.toString(array));
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }


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

        // 定義
        int p, i, j, temp;

        if (low >= high) {
            return;
        }
        
        // p就是基準數, 每個數組的第一個
        p = arr[low];
        i = low;
        j = high;

        while (i < j) {
            //右邊當發現小於p的值時停止循環
            while (arr[j] >= p && i < j) {
                j--;
            }

            //這裡一定是右邊開始，上下這兩個循環不能調換（下面有解析，可以先想想）

            //左邊當發現大於p的值時停止循環
            while (arr[i] <= p && i < j) {
                i++;
            }

            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }

        // 交換p和arr[i]
        arr[low] = arr[i];
        arr[i] = p;

        // 分別進行快排
        quickSort(arr, low, j - 1);
        quickSort(arr, j + 1, high);
    }
}

輸出結果:

[426, 375474, 8465, 453]
[426, 453, 8465, 375474]

總結

算法 時間復雜度 穩定性 適用場景
冒泡排序 O ( n 2 ) O(n^2) O(n2) 穩定 數組大致為從小到大
插入排序 O ( n 2 ) O(n^2) O(n2) 穩定 適用於數組較小的場景
歸並排序 O ( n l o g n ) O(nlogn) O(nlogn) 穩定 適用於數組較大的場景
快速排序 O ( n l o g n ) O(nlogn) O(nlogn) 不穩定 適用於數組較大的場景

到此這篇關於Java 數據結構與算法系列精講之排序算法的文章就介紹到這瞭,更多相關Java 排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：