快捷導(dǎo)航

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

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

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

十大排序算法對(duì)比

在這里插入圖片描述

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

冒泡排序

簡(jiǎn)單解釋：原理就如算法名字一樣，就像水中的氣泡一樣，每次我都把最大的或最小的放到最后面，這樣總共需要n-1趟即可完成排序，這就是第一層循環(huán)，第二次循環(huán)就是遍歷未被固定的那些數(shù)（理解成數(shù)組左邊的數(shù)，因?yàn)槊繉友h(huán)都會(huì)把最大或最小的數(shù)升到最右邊固定起來(lái)，下次就不遍歷這些數(shù)了），兩層循環(huán)遍歷結(jié)束后，所有的數(shù)就排好序了。兩層循環(huán)所以冒泡排序算法的時(shí)間復(fù)雜度是O( n 2 n^{2} n2)，是一個(gè)非常高的時(shí)間復(fù)雜度，我在下面的代碼進(jìn)行了優(yōu)化，加了一個(gè)標(biāo)志位，如果上一次循環(huán)未發(fā)生交換，就說(shuō)明已經(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; //加一個(gè)標(biāo)志位，記錄上一次是否發(fā)生了交換，如果是，我們則進(jìn)行下一輪，如果沒(méi)有，說(shuō)明已經(jīng)冒泡好了
        for (int i = 1; i < arr.length && flag; i++) { //控制次數(shù)，第幾趟排序，只需要n-1趟，有交換時(shí)進(jìn)行，只有flag=false就說(shuō)明上一次一個(gè)元素都沒(méi)有進(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);
    }
}

測(cè)試代碼：

升序排序（從小到大）

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;
        //測(cè)試冒泡排序
        System.out.println("測(cè)試冒泡排序:");
        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é)果：

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

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

//測(cè)試冒泡排序
System.out.println("測(cè)試冒泡排序:");
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é)果：

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

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

快速排序

簡(jiǎn)單解釋：快速排序就是每次找一個(gè)基點(diǎn)（第一個(gè)元素），然后兩個(gè)哨兵，一個(gè)從最前面往后走，一個(gè)從最后面往前面走，如果后面那個(gè)哨兵找到了一個(gè)比基點(diǎn)大的數(shù)停下來(lái)，前面那個(gè)哨兵找到比基點(diǎn)大的數(shù)停下來(lái)，然后交換兩個(gè)哨兵找到的數(shù)，如果找不到最后兩個(gè)哨兵就會(huì)碰到一起就結(jié)束，最后交換基點(diǎn)和哨兵相遇的地方的元素，然后就將一個(gè)序列分為比基點(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) { // 兩個(gè)哨兵（i左邊，j右邊）沒(méi)有相遇
            while (arr[j] >= base && i < j) { //哨兵j沒(méi)找到比base小的
                j--;
            }
            while (arr[i] <= base && i < j) { //哨兵i沒(mé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) { // 兩個(gè)哨兵（i左邊，j右邊）沒(méi)有相遇
            while (arr[j] <= base && i < j) { //哨兵j沒(méi)找到比base大的
                j--;
            }
            while (arr[i] >= base && i < j) { //哨兵i沒(mé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ù)組
    }
}