Java中常見排序算法有哪些

這篇文章將為大家詳細講解有關Java中常見排序算法，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

Java是一門面向對象編程語言，是一種廣泛使用的計算機編程語言，擁有跨平臺、面向對象、泛型編程的特性，廣泛應用于企業(yè)級Web應用開發(fā)和移動應用開發(fā)。

算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制。也就是說，能夠對一定規(guī)范的輸入，在有限時間內獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優(yōu)劣可以用空間復雜度與時間復雜度來衡量。

我們可以使用java語言來實現(xiàn)不同的算法。

Java常見排序算法

1、冒泡排序

a、冒泡排序，是通過每一次遍歷獲取最大/最小值

b、將最大值/最小值放在尾部/頭部

c、然后除開最大值/最小值，剩下的數據在進行遍歷獲取最大/最小值

d、代碼實現(xiàn)

public static void main(String[] args) {

        int arr[] = {8, 5, 3, 2, 4};

        //冒泡
        for (int i = 0; i < arr.length; i++) {
            //外層循環(huán)，遍歷次數
            for (int j = 0; j < arr.length - i - 1; j++) {
                //內層循環(huán)，升序（如果前一個值比后一個值大，則交換）
                //內層循環(huán)一次，獲取一個最大值
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

e、排序過程（紅色：移動的數據）

5,3,2,4,8

3,2,4,5,8

2,3,4,5,8

2,3,4,5,8

2,3,4,5,8

2、選擇排序

a、將第一個值看成最小值

b、然后和后續(xù)的比較找出最小值和下標

c、交換本次遍歷的起始值和最小值

d、說明：每次遍歷的時候，將前面找出的最小值，看成一個有序的列表，后面的看成無序的列表，然后每次遍歷無序列表找出最小值。

e、代碼實現(xiàn)

public static void main(String[] args) {

        int arr[] = {6, 5, 3, 2, 4};

        //選擇
        for (int i = 0; i < arr.length; i++) {
            //默認第一個是最小的。
            int min = arr[i];
            //記錄最小的下標
            int index = i;
            //通過與后面的數據進行比較得出，最小值和下標
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    index = j;
                }
            }
            //然后將最小值與本次循環(huán)的，開始值交換
            int temp = arr[i];
            arr[i] = min;
            arr[index] = temp;
            //說明：將i前面的數據看成一個排好的隊列，i后面的看成一個無序隊列。每次只需要找無需的最小值，做替換
        }
    }

f、排序過程（紅色：移動的數據）

2,5,3,6,4

2,3,5,6,4

2,3,4,6,5

2,3,4,5,6

2,3,4,5,6

3、插入排序

a、默認從第二個數據開始比較。

b、如果第二個數據比第一個小，則交換。然后在用第三個數據比較，如果比前面小，則插入（狡猾）。否則，退出循環(huán)

c、說明：默認將第一數據看成有序列表，后面無序的列表循環(huán)每一個數據，如果比前面的數據小則插入（交換）。否則退出。

d、代碼實現(xiàn)

public static void main(String[] args) {

        int arr[] = {7, 5, 3, 2, 4};

        //插入排序
        for (int i = 1; i < arr.length; i++) {
            //外層循環(huán)，從第二個開始比較
            for (int j = i; j > 0; j--) {
                //內存循環(huán)，與前面排好序的數據比較，如果后面的數據小于前面的則交換
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                } else {
                    //如果不小于，說明插入完畢，退出內層循環(huán)
                    break;
                }
            }
        }
    }

e、排序過程（紅色：有序，黑色：無序）

5,7,3,2,4

3,5,7,2,4

2,3,5,7,4

2,3,4,5,7

4、希爾排序（插入排序變種版）

a、基本上和插入排序一樣的道理

b、不一樣的地方在于，每次循環(huán)的步長，通過減半的方式來實現(xiàn)

c、說明：基本原理和插入排序類似，不一樣的地方在于。通過間隔多個數據來進行插入排序。

d、代碼實現(xiàn)

public static void main(String[] args) {

        int arr[] = {7, 5, 3, 2, 4};

        //希爾排序（插入排序變種版）
        for (int i = arr.length / 2; i > 0; i /= 2) {
            //i層循環(huán)控制步長
            for (int j = i; j < arr.length; j++) {
                //j控制無序端的起始位置
                for (int k = j; k > 0  && k - i >= 0; k -= i) {
                    if (arr[k] < arr[k - i]) {
                        int temp = arr[k - i];
                        arr[k - i] = arr[k];
                        arr[k] = temp;
                    } else {
                        break;
                    }
                }
            }
            //j,k為插入排序，不過步長為i
        }
    }

e、排序過程(步長4/2/1)

4,1,3,2,6,5,8,9,7

3,1,4,2,6,5,7,9,8

1,2,3,4,5,6,7,8,9

5、快速排序

a、確認列表第一個數據為中間值，第一個值看成空缺（低指針空缺）。

b、然后在剩下的隊列中，看成有左右兩個指針（高低）。

c、開始高指針向左移動，如果遇到小于中間值的數據，則將這個數據賦值到低指針空缺，并且將高指針的數據看成空缺值（高指針空缺）。然后先向右移動一下低指針，并且切換低指針移動。

d、當低指針移動到大于中間值的時候，賦值到高指針空缺的地方。然后先高指針向左移動，并且切換高指針移動。重復c、d操作。

e、直到高指針和低指針相等時退出，并且將中間值賦值給對應指針位置。

f、然后將中間值的左右兩邊看成行的列表，進行快速排序操作。

g、代碼實現(xiàn)

public static void main(String[] args) {

        int arr[] = {7, 5, 3, 2, 4, 1, 8, 9, 6};

        //快速排序
        int low = 0;
        int high = arr.length - 1;
        quickSort(arr, low, high);  
    }

    public static void quickSort(int[] arr, int low, int high) {
        //如果指針在同一位置(只有一個數據時)，退出
        if (high - low < 1) {
            return;
        }
        //標記，從高指針開始，還是低指針（默認高指針）
        boolean flag = true;
        //記錄指針的其實位置
        int start = low;
        int end = high;
        //默認中間值為低指針的第一個值
        int midValue = arr[low];
        while (true) {
            //高指針移動
            if (flag) {
                //如果列表右方的數據大于中間值，則向左移動
                if (arr[high] > midValue) {
                    high--;
                } else if (arr[high] < midValue) {
                    //如果小于，則覆蓋最開始的低指針值，并且移動低指針，標志位改成從低指針開始移動
                    arr[low] = arr[high];
                    low++;
                    flag = false;
                }
            } else {
                //如果低指針數據小于中間值，則低指針向右移動
                if (arr[low] < midValue) {
                    low++;
                } else if (arr[low] > midValue) {
                    //如果低指針的值大于中間值，則覆蓋高指針停留時的數據，并向左移動高指針。切換為高指針移動
                    arr[high] = arr[low];
                    high--;
                    flag = true;
                }
            }
            //當兩個指針的位置相同時，則找到了中間值的位置，并退出循環(huán)
            if (low == high) {
                arr[low] = midValue;
                break;
            }
        }
        //然后出現(xiàn)有，中間值左邊的小于中間值。右邊的大于中間值。
        //然后在對左右兩邊的列表在進行快速排序
        quickSort(arr, start, low -1);
        quickSort(arr, low + 1, end);
    }

h、排序過程

6,5,3,2,4,1,7,9,8

1,5,3,2,4,6,7,9,8

1,5,3,2,4,6,7,9,8

1,4,3,2,5,6,7,9,8

1,2,3,4,5,6,7,9,8

1,2,3,4,5,6,7,9,8

1,2,3,4,5,6,7,8,9

6、歸并排序

a、將列表按照對等的方式進行拆分

b、拆分小最小快的時候，在將最小塊按照原來的拆分，進行合并

c、合并的時候，通過左右兩塊的左邊開始比較大小。小的數據放入新的塊中

d、說明：簡單一點就是先對半拆成最小單位，然后將兩半數據合并成一個有序的列表。

e、代碼實現(xiàn)

public static void main(String[] args) {

        int arr[] = {7, 5, 3, 2, 4, 1，6};

        //歸并排序
        int start = 0;
        int end = arr.length - 1;
        mergeSort(arr, start, end);
    }

    public static void mergeSort(int[] arr, int start, int end) {
        //判斷拆分的不為最小單位
        if (end - start > 0) {
            //再一次拆分，知道拆成一個一個的數據
            mergeSort(arr, start, (start + end) / 2);
            mergeSort(arr, (start + end) / 2 + 1, end);
            //記錄開始/結束位置
            int left = start;
            int right = (start + end) / 2 + 1;
            //記錄每個小單位的排序結果
            int index = 0;
            int[] result = new int[end - start + 1];
            //如果查分后的兩塊數據，都還存在
            while (left <= (start + end) / 2 && right <= end) {
                //比較兩塊數據的大小，然后賦值，并且移動下標
                if (arr[left] <= arr[right]) {
                    result[index] = arr[left];
                    left++;
                } else {
                    result[index] = arr[right];
                    right++;
                }
                //移動單位記錄的下標
                index++;
            }
            //當某一塊數據不存在了時
            while (left <= (start + end) / 2 || right <= end) {
                //直接賦值到記錄下標
                if (left <= (start + end) / 2) {
                    result[index] = arr[left];
                    left++;
                } else {
                    result[index] = arr[right];
                    right++;
                }
                index++;
            }
            //最后將新的數據賦值給原來的列表，并且是對應分塊后的下標。
            for (int i = start; i <= end; i++) {
                arr[i] = result[i - start];
            }
        }
    }

f、排序過程

5,7,3,2,4,1,6

5,7,2,3,4,1,6

2,3,5,7,4,1,6

2,3,5,7,1,4,6

2,3,5,7,1,4,6

1,2,3,4,5,6,7

關于Java中常見排序算法就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。