快捷導(dǎo)航

java版十大排序經(jīng)典算法:完整代碼

更新時間：2021年07月27日 09:08:24 作者：牛哄哄的柯南

優(yōu)秀的文章也不少，但是Java完整版的好像不多，我把所有的寫一遍鞏固下，同時也真誠的希望閱讀到這篇文章的小伙伴們可以自己去從頭敲一遍，不要粘貼復(fù)制！希望我的文章對你有所幫助，每天進(jìn)步一點(diǎn)點(diǎn)

十大排序算法對比

在這里插入圖片描述

關(guān)于最后一列的穩(wěn)定性，我稍微解釋下，例如對序列：1 2 4 2 6 排序，序列中存在兩個2，如果我們把這兩個2標(biāo)記上（讓他倆不同），排序之后，前面的2還在前面，那么就稱這種排序是穩(wěn)定的，反之不穩(wěn)定。

冒泡排序

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

完整代碼：

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標(biāo)志表示為升序排序還是降序排序
        boolean flag = true; //加一個標(biāo)志位，記錄上一次是否發(fā)生了交換，如果是，我們則進(jìn)行下一輪，如果沒有，說明已經(jīng)冒泡好了
        for (int i = 1; i < arr.length && flag; i++) { //控制次數(shù)，第幾趟排序，只需要n-1趟，有交換時進(jìn)行，只有flag=false就說明上一次一個元素都沒有進(jìn)行交換
            /*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;
                }
            }
        }
    }
    //冒泡排序 -- 默認(rèn)不傳參升序
    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();
    }
}

運(yùn)行結(jié)果：

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

降序排序（從大到?。?/p>

//測試冒泡排序
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();

運(yùn)行結(jié)果：

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

下面幾個算法的測試也就是換了下類名和方法名（換成相應(yīng)的排序算法），如果想降序就在數(shù)組后面?zhèn)鱾€false即可。我就不一一復(fù)制了，我在最下面給出含所有算法的測試類，需要的自取即可。

快速排序

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

完整代碼：

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);
    }
    //快排序升序 -- 默認(rèn)
    public static void quickSort(int[] arr, int begin, int end) {
        if (begin > end) { //結(jié)束條件
            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;
            }
        }
        //最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換
        arr[begin] = arr[i];
        arr[i] = base;
        quickSort(arr, begin, i - 1); //遞歸調(diào)用左半數(shù)組
        quickSort(arr, i + 1, end); //遞歸調(diào)用右半數(shù)組
    }
    //快排序降序
    public static void quickSortDescending(int[] arr, int begin, int end) {
        if (begin > end) { //結(jié)束條件
            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;
            }
        }
        //最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換
        arr[begin] = arr[i];
        arr[i] = base;
        quickSortDescending(arr, begin, i - 1); //遞歸調(diào)用左半數(shù)組
        quickSortDescending(arr, i + 1, end); //遞歸調(diào)用右半數(shù)組
    }
}