java版十大排序經典算法:完整代碼

Posted on by

十大排序算法對比

在這裡插入圖片描述

關於最後一列的穩定性，我稍微解釋下，例如對序列：1 2 4 2 6 排序，序列中存在兩個2，如果我們把這兩個2標記上（讓他倆不同），排序之後，前面的2還在前面，那麼就稱這種排序是穩定的，反之不穩定。

冒泡排序

簡單解釋： 原理就如算法名字一樣，就像水中的氣泡一樣，每次我都把最大的或最小的放到最後面，這樣總共需要n-1趟即可完成排序，這就是第一層循環，第二次循環就是遍歷未被固定的那些數（理解成數組左邊的數，因為每層循環都會把最大或最小的數升到最右邊固定起來，下次就不遍歷這些數瞭），兩層循環遍歷結束後，所有的數就排好序瞭。 兩層循環所以冒泡排序算法的時間復雜度是O( n 2 n^{2} n2)，是一個非常高的時間復雜度，我在下面的代碼進行瞭優化，加瞭一個標志位，如果上一次循環未發生交換，就說明已經是有序的瞭，就不繼續下去瞭，反之繼續進行下一輪。

完整代碼：

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: BubbleSort
 * @Description: 冒泡排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:31
 */
public class BubbleSort {
    //冒泡排序
    public static void bubbleSort(int[] arr, boolean ascending) { //exchange標志表示為升序排序還是降序排序
        boolean flag = true; //加一個標志位，記錄上一次是否發生瞭交換，如果是，我們則進行下一輪，如果沒有，說明已經冒泡好瞭
        for (int i = 1; i < arr.length && flag; i++) { //控制次數，第幾趟排序，隻需要n-1趟，有交換時進行，隻有flag=false就說明上一次一個元素都沒有進行交換
            /*System.out.print("第"+i+"次遍歷：");
            for (int i1 : arr) {
                System.out.print(i1+" ");
            }
            System.out.println();*/
            flag = false; //假定未交換
            for (int j = 0; j < arr.length - i; j++) {
                if (ascending ? arr[j] > arr[j + 1] : arr[j] < arr[j + 1]) { //控制升序還是降序
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
        }
    }
    //冒泡排序 -- 默認不傳參升序
    public static void bubbleSort(int[] arr) {
        bubbleSort(arr, true);
    }
}

測試代碼：

升序排序（從小到大）

package com.keafmd.Sequence;
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;
/**
 * Keafmd
 *
 * @ClassName: Sort
 * @Description: 十大排序算法
 * @author: 牛哄哄的柯南
 * @date: 2021-06-16 21:27
 */
public class Sort {
    public static void main(String[] args) {
        int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
        int[] temparr;
        //測試冒泡排序
        System.out.println("測試冒泡排序:");
        temparr = nums.clone();
        BubbleSort.bubbleSort(temparr);
        //逆序排序
        //BubbleSort.bubbleSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();
    }
}

運行結果：

測試冒泡排序: –66 –13 –1 1 4 9 12 25 25 26 34 47 58 99 162 10093

降序排序（從大到小）

//測試冒泡排序
System.out.println("測試冒泡排序:");
temparr = nums.clone();
BubbleSort.bubbleSort(temparr,false);
for (int i = 0; i < temparr.length; i++) {
    System.out.print(temparr[i] + " ");
}
System.out.println();

運行結果：

測試冒泡排序: 10093 162 99 58 47 34 26 25 25 12 9 4 1 –1 –13 –66

下面幾個算法的測試也就是換瞭下類名和方法名（換成相應的排序算法），如果想降序就在數組後面傳個false即可。我就不一一復制瞭，我在最下面給出含所有算法的測試類，需要的自取即可。

快速排序

簡單解釋：快速排序就是每次找一個基點（第一個元素），然後兩個哨兵，一個從最前面往後走，一個從最後面往前面走，如果後面那個哨兵找到瞭一個比基點大的數停下來，前面那個哨兵找到比基點大的數停下來，然後交換兩個哨兵找到的數，如果找不到最後兩個哨兵就會碰到一起就結束，最後交換基點和哨兵相遇的地方的元素，然後就將一個序列分為比基點小的一部分和比基點大的一部分，然後遞歸左半部分和右半部分，最後的結果就是有序的瞭。

完整代碼：

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: QuickSort
 * @Description: 快速排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:32
 */
public class QuickSort {
    //快速排序
    public static void quickSort(int[] arr) {
        quickSort(arr, true);
    }
    public static void quickSort(int[] arr, boolean ascending) {
        if (ascending) {
            quickSort(arr, 0, arr.length - 1, true);
        } else {
            quickSort(arr, 0, arr.length - 1, false);
        }
    }
    public static void quickSort(int[] arr, int begin, int end, boolean ascending) {
        if (ascending)
            quickSort(arr, begin, end);
        else
            quickSortDescending(arr, begin, end);
    }
    //快排序升序 -- 默認
    public static void quickSort(int[] arr, int begin, int end) {
        if (begin > end) { //結束條件
            return;
        }
        int base = arr[begin];
        int i = begin, j = end;
        while (i < j) { // 兩個哨兵（i左邊，j右邊）沒有相遇
            while (arr[j] >= base && i < j) { //哨兵j沒找到比base小的
                j--;
            }
            while (arr[i] <= base && i < j) { //哨兵i沒找到比base大的
                i++;
            }
            if (i < j) { //如果滿足條件則交換
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //最後將基準為與i和j相等位置的數字交換
        arr[begin] = arr[i];
        arr[i] = base;
        quickSort(arr, begin, i - 1); //遞歸調用左半數組
        quickSort(arr, i + 1, end); //遞歸調用右半數組
    }
    //快排序降序
    public static void quickSortDescending(int[] arr, int begin, int end) {
        if (begin > end) { //結束條件
            return;
        }
        int base = arr[begin];
        int i = begin, j = end;
        while (i < j) { // 兩個哨兵（i左邊，j右邊）沒有相遇
            while (arr[j] <= base && i < j) { //哨兵j沒找到比base大的
                j--;
            }
            while (arr[i] >= base && i < j) { //哨兵i沒找到比base小的
                i++;
            }
            if (i < j) { //如果滿足條件則交換
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //最後將基準為與i和j相等位置的數字交換
        arr[begin] = arr[i];
        arr[i] = base;
        quickSortDescending(arr, begin, i - 1); //遞歸調用左半數組
        quickSortDescending(arr, i + 1, end); //遞歸調用右半數組
    }
}

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：