快捷導(dǎo)航

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

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

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

快速排序

簡(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右邊）沒有相遇
            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) { // 兩個(gè)哨兵（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ù)組
    }
}

直接選擇排序

簡(jiǎn)單解釋：數(shù)組分為已排序部分（前面）和待排序序列（后面）第一次肯定所有的數(shù)都是待排序的從待排序的序列中找到最大或最小的那個(gè)元素，放到前面的已排序部分，然后一直找，不斷縮小待排序的范圍，直到所有的數(shù)都是已排序的了

完整代碼：

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: SelectSort
 * @Description: 選擇排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:33
 */
public class SelectSort {
    //直接選擇排序
    public static void selectSort(int[] arr, boolean ascending) {
        for (int i = 0; i < arr.length; i++) {
            int m = i; //最小值或最小值的下標(biāo)
            for (int j = i + 1; j < arr.length; j++) {
                if (ascending ? arr[j] < arr[m] : arr[j] > arr[m]) {
                    m = j; //找到待排序的數(shù)中最小或最大的那個(gè)數(shù)，記錄下標(biāo)
                }
            }
            //交換位置
            int temp = arr[i];
            arr[i] = arr[m];
            arr[m] = temp;
        }
    }
    public static void selectSort(int[] arr) {
        selectSort(arr, true);
    }
}

堆排序

先理解下大頂堆和小頂堆，看圖

大頂堆，雙親結(jié)點(diǎn)的值比每一個(gè)孩子結(jié)點(diǎn)的值都要大。根結(jié)點(diǎn)值最大

小頂堆，雙親結(jié)點(diǎn)的值比每一個(gè)孩子結(jié)點(diǎn)的值都要小。根結(jié)點(diǎn)值最小

簡(jiǎn)單解釋：構(gòu)建好大頂堆或小頂堆結(jié)構(gòu)，這樣最上面的就是最大值或最小值，那么我們?nèi)〕龆秧斣?，然后重新?gòu)建結(jié)構(gòu)，一直取，一直重新構(gòu)建，那么最后達(dá)到排序的效果了。

完整代碼：

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: HeapSort
 * @Description: 堆排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:34
 */
public class HeapSort {
    //堆排序
    public static void heapSort(int[] arr) {
        //對(duì)傳入的數(shù)組進(jìn)行建立堆，這里默認(rèn)建立大頂堆，進(jìn)行升序排列
        heapSort(arr, true);
    }
    public static void heapSort(int[] arr, boolean maxheap) {
        //1.構(gòu)建大頂堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //從第一個(gè)非葉子結(jié)點(diǎn)從下至上，從右至左調(diào)整結(jié)構(gòu)
            sift(arr, i, arr.length , maxheap);
        }
        //2.調(diào)整堆結(jié)構(gòu)+交換堆頂元素與末尾元素
        for (int j = arr.length - 1; j > 0; j--) {
            //現(xiàn)在的數(shù)組第一個(gè)就是根結(jié)點(diǎn)，最小值所在，進(jìn)行交換，把它放到最右邊
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            //重新建立堆
            sift(arr, 0, j , maxheap); //重新對(duì)堆進(jìn)行調(diào)整
        }
    }
    //建立堆的方法
    /**
     * 私有方法，只允許被堆排序調(diào)用
     *
     * @param arr     要排序數(shù)組
     * @param parent  當(dāng)前的雙親節(jié)點(diǎn)
     * @param len     數(shù)組長(zhǎng)度
     * @param maxheap 是否建立大頂堆
     */
    private static void sift(int[] arr, int parent, int len, boolean maxheap) {
        int value = arr[parent]; //先取出當(dāng)前元素i
        for (int child = 2 * parent + 1; child < len; child = child * 2 + 1) { //從parent結(jié)點(diǎn)的左子結(jié)點(diǎn)開始，也就是2*parent+1處開始
            if (child+1 < len && (maxheap ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1])) { //如果左子結(jié)點(diǎn)小于右子結(jié)點(diǎn)，child指向右子結(jié)點(diǎn)
                child++; //右孩子如果比左孩子大，我們就將現(xiàn)在的孩子換到右孩子
            }
            //判斷是否符合大頂堆的特性， 如果右孩子大于雙親，自然左孩子也大于雙親，符合
            //如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)，將子節(jié)點(diǎn)值賦給父節(jié)點(diǎn)（不用進(jìn)行交換)
            if (maxheap ? value < arr[child] : value > arr[child]) {
                arr[parent]=arr[child];
                parent = child;
            }
            else {//如果不是，說明已經(jīng)符合我們的要求了。
                break;
            }
        }
        arr[parent] =value; //將value值放到最終的位置

    }
}