八種排序算法及Java實現(xiàn)

1. 冒泡排序

image
private static void bubbleSort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }

        int length = a.length;

        for (int i = 0; i < length - 1; i++) {
            for (int j = i; j < length - 1 - i; j++) {
                if (a[j] > a[j + 1])
                    swap(a, j, j + 1);
            }
        }
    }

2. 快排

①. 從數(shù)列中挑出一個元素，稱為”基準(zhǔn)”（pivot）。
②. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素擺在基準(zhǔn)后面（相同的數(shù)可以到任一邊）。在這個分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
③. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。


  /**
     * 快排
     * @param arr
     * @param low
     * @param high
     */
    public static void quickSort(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;
        int temp = arr[left]; //挖坑1：保存基準(zhǔn)的值

        while (left < right) {
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right]; //坑2：從后向前找到比基準(zhǔn)小的元素，插入到基準(zhǔn)位置坑1中
            while (left < right && arr[left] <= temp) {
                left++;
            }
            arr[right] = arr[left]; //坑3：從前往后找到比基準(zhǔn)大的元素，放到剛才挖的坑2中
        }
        arr[left] = temp; //基準(zhǔn)值填補(bǔ)到坑3中，準(zhǔn)備分治遞歸快排
        System.out.println("Sorting: " + Arrays.toString(arr));
        quickSort(arr, low, left - 1);
        quickSort(arr, left + 1, high);
    }

3. 簡單選擇排序

每次選取最大的一個數(shù)字，放在數(shù)組未排序的最后一個，直到排序結(jié)束。

/**
     * 選擇排序
     *
     */
    private static void selectSort2(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        int n = a.length;

        while (n > 1) {
            int pos = findMaxIndex(a, n);
            swap(a, pos, n - 1);
            n--;
        }

    }

    /**
     * 獲取數(shù)組中最大數(shù)字的index
     */
    public static int findMaxIndex(int[] a, int n) {
        int max = a[0];
        int pos = 0;
        for (int i = 1; i < n; i++) {
            if (a[i] > max) {
                max = a[i];
                pos = i;
            }
        }
        return pos;
    }

4. 堆排序

堆排序是一種樹形選擇排序方法，特點(diǎn)是在排序過程中將L[1···n]看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（或最?。┰亍?/p>

  • 父節(jié)點(diǎn) parent = (i-1)/2;
  • 左子節(jié)點(diǎn) c1 = 2i+1;
  • 右子節(jié)點(diǎn) c2 = 2i+2;

數(shù)字：87 45 78 32 17 65 53 09

①從上到下，從左到右建堆

int parent = (last_node - 1) / 2;
根據(jù)數(shù)組最后一位可以得出【09】的根節(jié)點(diǎn)為【32】
倒著進(jìn)行heapify

② 從倒數(shù)第二層左節(jié)點(diǎn)開始，與左右子樹進(jìn)行比較交換

③ 從第二步max位置依次遞歸直到頂端為最大數(shù)

④ 將根節(jié)點(diǎn)【87】與最后一位【09】交換，移出最后一位【87】，最后對根節(jié)點(diǎn)進(jìn)行重新heapfy，將【09】與【78】進(jìn)行交換……直到排序完成

 /**
     * 堆排序
     *
     * @param a
     */
    private static void heapSort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        int n = a.length;
        buildHeap(a, n);

        for (int i = n - 1; i >= 0; i--) {
            swap(a, i, 0); // 交換根節(jié)點(diǎn)和最后一個節(jié)點(diǎn)
            heapify(a, i, 0); // 重新heapify
        }
    }

    /**
     * 父節(jié)點(diǎn) parent = (i-1)/2;
     * 左子節(jié)點(diǎn) c1 = 2i+1;
     * 右子節(jié)點(diǎn) c2 = 2i+2;
     */
    private static void heapify(int[] tree, int n, int i) {
        if (i >= n)
            return;
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;

        /*
         * 左中右三個節(jié)點(diǎn)找最大值
         */
        int max = i;

        if (c1 < n && tree[c1] > tree[max])
            max = c1;
        if (c2 < n && tree[c2] > tree[max])
            max = c2;
        if (max != i) {
            // 將最大值與i進(jìn)行交換
            swap(tree, max, i);
            heapify(tree, n, max);
        }

    }

    private static void buildHeap(int[] tree, int n) {
        int last_node = n - 1;
        int parent = (last_node - 1) / 2;
        for (int i = parent; i >= 0; i--) {
            heapify(tree, n, i);
        }
    }

5. 直接插入排序

從第二個數(shù)字開始，依次把數(shù)字插入到合適的位置。


   /**
     * 插入排序
     */
    private static void insertSort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        int length = a.length;

        for (int i = 1; i < length; i++) {
            insert(a, i);
        }
    }

    /**
     * 把第n個數(shù)插入到數(shù)組a合適的位置
     */
    private static void insert(int[] a, int n) {
        int key = a[n];
        int i = n;
        while (a[i - 1] > key) {
            a[i] = a[i - 1];
            i--;
            if (i == 0)
                break;
        }
        a[i] = key;

    }

6. 希爾排序

將待排序數(shù)組按照步長gap進(jìn)行分組，然后將每組的元素利用直接插入排序的方法進(jìn)行排序；每次再將gap折半減小，循環(huán)上述操作；當(dāng)gap=1時，利用直接插入，完成排序。


/**
     * 希爾排序
     */
    public static void shellSort(int a[]) {
        if (a == null || a.length == 0) {
            return;
        }

        int n = a.length;

        for (int gap = n / 2; gap >= 1; gap = gap / 2) {
            for (int i = 0; i + gap < n; i++) {
                for (int j = 0; j + gap < n; j += gap) {
                    if (a[j] > a[j + gap]) {
                        swap(a, j, j + gap);
                    }
                }
            }
        }
    }

7. 歸并排序

/**
     * 歸并
     * 2, 8, 9, 10, 4, 5, 6, 7
     *
     * @param a
     */

    public static void mergeSort(int[] a, int l, int r) {
        if (l == r)
            return;
        int mid = (l + r) / 2;
        // 左歸并，右歸并
        mergeSort(a, l, mid);
        mergeSort(a, mid + 1, r);
        merge(a, l, mid + 1, r);
    }

    /**
     * 合并一個從l-mid,r-mid排好序的數(shù)組
     * 2, 8, 9, 10, 4, 5, 6, 7
     * l = 0,mid=4,r=7
     */
    private static void merge(int[] a, int l, int mid, int r) {
        int leftSize = mid - l;
        int rightSize = r - mid + 1;
        int left[] = new int[leftSize];
        int right[] = new int[rightSize];
        /*
         * 1. 構(gòu)建兩個數(shù)組
         * left [2,8,9,10]
         * right[4,5,6,7]
         */
        for (int i = l; i < mid; i++) {
            left[i - l] = a[i];
        }
        for (int i = mid; i <= r; i++) {
            right[i - mid] = a[i];
        }

        /**
         * 2.合并成1個
         * i指向左數(shù)組第一個
         * j指向右數(shù)組第一個
         * k 指向空數(shù)組最左邊
         */
        int i = 0;
        int j = 0;
        int k = l;

        while (i < leftSize && j < rightSize) {
            if (left[i] < right[j]) {
                a[k] = left[i];
                i++;
                k++;
            } else {
                a[k] = right[j];
                j++;
                k++;
            }
        }


        /**
         * 如果上面循環(huán)完畢，i仍舊沒到達(dá)頂部，則把剩下的數(shù)字抄一下
         */
        while (i < leftSize) {
            a[k] = left[i];
            i++;
            k++;
        }


        /**
         * 如果上面循環(huán)完畢，j仍舊沒到達(dá)頂部，則把剩下的數(shù)字抄一下
         */
        while (j < rightSize) {
            a[k] = right[j];
            j++;
            k++;
        }
    }

8. 基數(shù)排序

  • ① 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
  • ② arr為原始數(shù)組，從最低位開始取每個位組成radix數(shù)組；

  • ③ 對radix進(jìn)行計數(shù)排序（利用計數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；


整理自https://juejin.im/post/5b95da8a5188255c775d8124#heading-0

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容