java實現幾種常見排序算法

silentoy 8年前發布 | 21K 次閱讀 排序算法 Java開發

 

本文介紹幾種常見排序算法（選擇排序，插入排序，希爾排序，歸并排序，快速排序，堆排序），對算法的思路、性質、特點、具體步驟、java實現以及trace圖解進行了全面的說明。最后對幾種排序算法進行了比較和總結。

寫在前面

基礎介紹

java: Interface Comparable<T>

Java中很多類已經實現了 Comparable<T> 接口，用戶也可自定義類型實現該接口

total order:

  • Antisymmetry(反對稱性): if v ≤ w and w ≤ v, then v = w.

  • Transitivity(傳遞性): if v ≤ w and w ≤ x, then v ≤ x.

  • Totality: either v ≤ w or w ≤ v or both.

注意： The <= operator for double is not a total order ，violates totality: (Double.NaN <= Double.NaN) is false

通用代碼：

// Less. Is item v less than w ?
private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

//Exchange. Swap item in array a[] at index i with the one at index j
private static void exch(Comparable[] a,, int i, int j) {
    Comparable swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

初級排序算法

selection sort(選擇排序)

思路：

  • 在第i次迭代中，在剩下的(即未排序的)元素中找到最小的元素

  • 將第i個元素與最小的元素交換位置

現象：

  • 設已排序的和未排序的交界處為 ↑，則每次循環， ↑ 從左往右移動一個位置

  • ↑ 左邊的元素（包括↑）固定了，且升序

  • ↑ 右邊的任一元素全部比左邊的所有元素都大

步驟：

  • move the pointer to the right

  • indentify index of minimun entry on right

  • exchange into positon

java實現：

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int min = i;
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        exch(a, i, min);
    }
}

特點：

  • 運行時間和輸入無關，無論輸入是已排序，時間復雜度都是O(n^2)

  • 數據移動最少，交換的次數和數組大小是線性關系

insertion sort(插入排序)

思路：

  • 在第i次迭代中，將第i個元素與每一個它左邊且比它大的的元素交換位置

現象：

  • 設已排序的和未排序的交界處為 ↑，則每次循環， ↑ 從左往右移動一個位置

  • ↑ 左邊的元素（包括↑）且升序，但位置不固定(因為后續可能會因插入而移動)

  • ↑ 右邊的元素還不可見

步驟：

  • Move the pointer to the right.

  • Moving from right to left, exchange a[i] with each larger entry to its left.

java實現：

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);
        }
    }
}

inversion（倒置）：An inversion is a pair of keys that are out of order

部分有序：An array is partially sorted if the number of inversions is ≤ c N.

特點：

  • 運行時間和輸入有關，當輸入已排序時，時間復雜度是O(n);

  • For partially-sorted arrays, insertion sort runs in linear time.(交換的次數等于輸入中倒置(inversion)的個數)

  • 插入排序適合部分有序數組，也適合小規模數組

ShellSort(希爾排序)

希爾排序是基于插入排序的。

思路：

  • Move entries more than one position at a time by h-sorting the array

  • 按照h的步長進行插入排序

現象：

  • 數組中任意間隔為h的元素都是有序的

  • A g-sorted array remains g-sorted after h-sorting it.

性質：

  • 遞增數列一般采用3x+1：1,4,13,40,121,364.....，使用這種遞增數列的希爾排序所需的比較次數不會超過N的若干倍乘以遞增數列的長度。

  • 最壞情況下，使用3x+1遞增數列的希爾排序的比較次數是O(N^(3/2))

java實現：

public static void sort(Comparable[] a) {
    int N = a.length;

    // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
    int h = 1;
    while (h < N/3) h = 3*h + 1; 

    while (h >= 1) {
        // h-sort the array
        for (int i = h; i < N; i++) {
            for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                exch(a, j, j-h);
            }
        }
        h /= 3;
    }
}

shuffing(不是排序算法)

目標：Rearrange array so that result is a uniformly random permutation

shuffle sort思路

  • 為數組的每一個位置生成一個隨機實數

  • 排序這個生成的數組

Knuth shuffle demo

  • In iteration i, pick integer r between 0 and i uniformly at random.

  • Swap a[i] and a[r] .

correct variant: between i and N – 1

  • Mergesort--Java sort for objects.

  • Quicksort--Java sort for primitive types.

下面看看這兩種排序算法

merge sort(歸并排序)

思路：

  • Divide array into two halves.

  • Recursivelysort each half.

  • Merge two halves.

Abstract in-place merge(原地歸并的抽象方法)

Given two sorted subarrays a[lo] to a[mid] and a[mid+1] to a[hi],replace with sorted subarray a[lo] to a[hi]

步驟：

  • 先將所有元素復制到 aux[] 中，再歸并回 a[] 中。

  • 歸并時的四個判斷：

    • 左半邊用盡(取右半邊元素)

    • 右半邊用盡(取左半邊元素)

    • 右半邊的當前元素 小于 左半邊的當前元素(取右半邊的元素)

    • 右半邊的當前元素 大于/等于 左半邊的當前元素(取左半邊的元素)

merging java實現：

 // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }
}

Top-down mergesort(自頂向下的歸并排序)

mergesort java實現：

// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);  //將左邊排序
    sort(a, aux, mid + 1, hi);  //將右邊排序
    merge(a, aux, lo, mid, hi); //歸并結果
}

自頂向下的歸并排序的軌跡圖

由圖可知，原地歸并排序的大致趨勢是，先局部排序，再擴大規模；先左邊排序，再右邊排序；每次都是左邊一半局部排完且merge了，右邊一半才開始從最局部的地方開始排序。

改進

  • 對小規模子數組使用插入排序

  • 測試數組是否已經有序（左邊最大<右邊最小時，直接返回）

  • 不將元素復制到輔助數組(節省時間而非空間)

Bottom-up mergesort(自底向上的歸并排序)

思路：

  • 先歸并微型數組，從兩兩歸并開始(每個元素理解為大小為1的數組)

  • 重復上述步驟，逐步擴大歸并的規模，2,4,8.....

java實現：

public class MergeBU{
   private static void merge(...){ /* as before */ }

   public static void sort(Comparable[] a){
     int N = a.length;
     Comparable[] aux = new Comparable[N];
     for (int sz = 1; sz < N; sz = sz+sz)
     for (int lo = 0; lo < N-sz; lo += sz+sz)
     merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
   }
}

自底向上的歸并排序的軌跡圖

由圖可知，自底向上歸并排序的大致趨勢是，先局部排序，逐步擴大到全局排序；步調均勻，穩步擴大

quicksort

思路：

  • Shufflethe array.

  • Partition(切分)so that, for some j

  • entry a[j] is in place

  • no larger entry to the left of j

  • no smaller entry to the right of j

  • Sorteach piece recursively.

其中很重要的一步就是 Partition(切分) ，這個過程使得滿足以下三個條件:

  • 對于某個j,a[j]已經排定;

  • a[lo]到a[j-1]中的所有元素都不大于a[j];

  • a[j+1]到a[hi]中的所有元素都不小于a[j];

partition java實現

// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    Comparable v = a[lo];
    while (true) { 

        // find item on lo to swap
        while (less(a[++i], v))
            if (i == hi) break;

        // find item on hi to swap
        while (less(v, a[--j]))
            if (j == lo) break;      // redundant since a[lo] acts as sentinel

        // check if pointers cross
        if (i >= j) break;

        exch(a, i, j);
    }

    // put partitioning item v at a[j]
    exch(a, lo, j);

    // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
    return j;
}

快排java實現：

public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);
    sort(a, 0, a.length - 1);
}

// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int j = partition(a, lo, hi);
    sort(a, lo, j-1);
    sort(a, j+1, hi);
    assert isSorted(a, lo, hi);
}

快排的軌跡圖

由圖可知，和歸并排序不同，快排的大致趨勢是，先全局大體有個走勢——左邊比右邊小，逐步細化到局部；也是先左后右；局部完成時全部排序也就完成了。

一些實現的細節：

  • 原地切分：不使用輔助數組

  • 別越界：測試條件(j == lo)是冗余的(a[lo]不可能比自己小)；

  • 保持隨機性：初始時的隨機打亂跟重要

  • 終止循環

  • 處理切分元素值有重復的情況：這里可能出問題

性質：

  • 快排是in-place的

  • 快排不穩定

改進

  • 對小規模子數組使用插入排序

  • 三取樣切分

三向切分的快速排序

思路：

  • Let v be partitioning item a[lo].

  • Scan i from left to right.

  • (a[i] < v): exchange a[lt] with a[i]; increment both lt and i

  • (a[i] > v): exchange a[gt] with a[i]; decrement gt

  • (a[i] == v): increment i

主要是通過增加一個指針來實現的。普通的快拍只有lo和high兩個指針，故只能記錄 大于 (high右邊)和 小于 (lo左邊)兩個區間， 等于 只能并入其中一個；這里增加了使用了lt,i,gt三個指針，從而達到記錄 大于 (gt右邊)、 小于 (lt左邊)和 等于 (lt和i之間)三個區間。

三切分的示意圖

三向切分的java實現：

// quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if      (cmp < 0) exch(a, lt++, i++);
        else if (cmp > 0) exch(a, i, gt--);
        else              i++;
    }

    // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
    sort(a, lo, lt-1);
    sort(a, gt+1, hi);
}

Heapsort(堆排序)

思路：

  • Create max-heap with all N keys.

  • Repeatedly remove the maximum key.

  • swim:由下至上的堆有序化

  • sink:由上至下的對有序化

堆排序主要分為兩個階段：

  1. 堆的構造

  2. 下沉排序

java實現如下：

public static void sort(Comparable[] pq) {
    int N = pq.length;
    //堆的構造
    for (int k = N/2; k >= 1; k--)
        sink(pq, k, N);

    //下沉排序
    while (N > 1) {
        exch(pq, 1, N--);
        sink(pq, 1, N);
    }
}

堆排序的軌跡圖

由圖看出，堆排序的趨勢是，堆構造階段，大致是降序的走勢，到了下沉階段，從右到左（或者說從后往前）逐步有序

Significance： In-place sorting algorithm with N log N worst-case.

  • Mergesort: no, linear extra space.

  • Quicksort: no, quadratic time in worst case

缺點

  • Inner loop longer than quicksort’s.

  • Makes poor use of cache memory.

  • Not stable(不穩定)

總結和比較

排序算法總結表

最好情況和最壞情況：參見上面的表格

關于穩定性：

  • 穩定性，插入排序，歸并排序

  • 不穩定：選擇排序，快排，希爾排序，堆排序

  • 原因： Long-distance exchange

關于額外空間：除了歸并排序需要線性的額外空間，其他都是in-place的

命題

  • 對于長度為N的數組，選擇排序需要N^2/2次比較和N次交換(pf見P156)

  • 對于隨機排列的長度為N的且主鍵不重復的數組（pf見P157）

    • 平均情況下插入排序需要~N^2/4次比較和~N^2/4次交換

    • 最壞情況下需要~N^2/2次比較和~N^2/2次交換，

    • 最好情況下需要N-1次比較和0次交換。

  • Mergesort uses at most N lg N compares and 6 N lg N array accesses to sort any array of size N. (pf見P173)

  • Mergesort uses extra space proportional to N.(The array aux[] needs to be of size N for the last merge.)

  • Any compare-based sorting algorithm must use at least lg ( N ! ) ~ N lg N compares in the worst-case.(pf見P177)

  • 長度為N的無重復數組排序，快速排序平均需要~2N ln N 次比較（以及1/6即1/3 N ln N的交換）

    • 最多需要約N^2/2次比較

    • 最少需要~N lg N 次比較

  • 用下沉操作由N個元素構造堆只需少于2N次比較以及少于N次交換(pf見P206)

  • 將N個元素排序，堆排序只需少于（2NlgN+2N）次比較以及一半次數的交換(pf見P208)

來自： https://segmentfault.com/a/1190000005082467

 本文由用戶 silentoy 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！