最近在讀<<Algorithms 4th>>時(shí),了解到了很多常用的排序算法,故寫一篇讀書筆記記錄下這些排序算法的思路和實(shí)現(xiàn).

冒泡排序

冒泡排序是一種非常簡(jiǎn)單的初級(jí)排序算法,它每次比較相鄰的兩個(gè)元素,如果順序錯(cuò)誤就進(jìn)行交換.由于最小的元素是經(jīng)由不斷交換慢慢浮到頂端的,所以叫做冒泡排序.

冒泡排序?qū)個(gè)元素需要O(n^2)次的比較次數(shù),所以它對(duì)規(guī)模較大的數(shù)組進(jìn)行排序是效率低下的.

運(yùn)行過程

1. 比較相鄰的兩個(gè)元素,如果第二個(gè)元素小于第一個(gè)元素,則進(jìn)行交換(降序則相反).

2. 對(duì)每一對(duì)相鄰元素作同樣的工作,從開始第一對(duì)直到最后一對(duì).完成后,最后的元素將是最大的元素.

3. 針對(duì)所有的元素重復(fù)以上步驟,除了最后一個(gè)元素.

4. 持續(xù)地對(duì)每次越來越少的元素重復(fù)以上步驟,直到整個(gè)數(shù)組有序(即沒有任何一對(duì)元素需要比較).

代碼實(shí)現(xiàn)

    // less與exch函數(shù)見完整代碼
    public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (less(a[j + 1], a[j])) {
                    exch(a, j, j + 1);
                }
            }
        }
    }

完整代碼

/**
 * Bubble Sort
 * 
 * @author SylvanasSun
 *
 */
public class Bubble {

    // This class should not be instantiated.
    private Bubble() {
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * 
     * @param a
     *            a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (less(a[j + 1], a[j])) {
                    exch(a, j, j + 1);
                }
            }
        }
    }

    /**
     * Rearranges the array in ascending order, using a comparator.
     * 
     * @param a
     *            a the arry to be sorted
     * @param comparator
     *            comparator the comparator specifying the order
     */
    public static void sort(Object[] a, Comparator comparator) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (less(comparator, a[j + 1], a[j])) {
                    exch(a, j, j + 1);
                }
            }
        }
    }

    // a < b ?
    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    // a < b ?
    private static boolean less(Comparator comparator, Object a, Object b) {
        return comparator.compare(a, b) < 0;
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    // print array elements to console
    public static void print(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    // test
    public static void main(String[] args) {
        String[] s = new Scanner(System.in).nextLine().split("\\s+");
        Bubble.sort(s);
        Bubble.print(s);
    }
}

選擇排序

選擇排序也是一種非常簡(jiǎn)單直觀的初級(jí)排序算法,它的思想是不斷地選擇剩余元素之中的最小者.

它有以下兩個(gè)特點(diǎn).

1. 運(yùn)行時(shí)間與輸入模型無關(guān) 在選擇排序中,為了找出最小元素而掃描一遍數(shù)組并不能為下一輪掃描提供什么信息,即使輸入是一個(gè)已經(jīng)有序的數(shù)組或者是主鍵全部相等的數(shù)組和一個(gè)元素隨機(jī)排列無序的數(shù)組所用的排序時(shí)間是一樣長(zhǎng)的.

2. 數(shù)據(jù)移動(dòng)是最少的 如果元素處于正確的位置上,則它不會(huì)被移動(dòng).選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換.

運(yùn)行過程

1. 首先,找到數(shù)組中最小的那個(gè)元素

2. 其次,將它和數(shù)組的第一個(gè)元素交換位置(如果第一個(gè)元素就是最小元素則它就和自己交換)

3. 再次,在剩下的元素中找到最小的元素,將它與數(shù)組第二個(gè)元素交換位置.如此往復(fù),直到整個(gè)數(shù)組有序.

代碼實(shí)現(xiàn)

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

插入排序

插入排序與選擇排序一樣,當(dāng)前索引左邊的所有元素都是有序的,但它們的最終位置并不是確定的.它構(gòu)建了一個(gè)有序序列,對(duì)于未排序的元素,在有序序列中從后向前掃描,找到相應(yīng)的位置并插入.

插入排序所需的時(shí)間取決于輸入模型中元素的初始順序.當(dāng)輸入模型是一個(gè)部分有序的數(shù)組時(shí),插入排序的效率會(huì)高很多.

因此插入排序?qū)τ?strong>部分有序的數(shù)組十分高效,也很適合小規(guī)模的數(shù)組.

運(yùn)行過程

1. 從第一個(gè)元素開始,該元素可以認(rèn)為已是有序的

2. 取出下一個(gè)元素,在有序序列中從后向前進(jìn)行掃描

3. 如果該元素(已排序)大于新元素,則將該元素移到下一位置(右移)

4. 重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置

5. 將新元素插入到該位置后

6. 重復(fù)步驟2~5

代碼實(shí)現(xiàn)

public static void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            // a[i] insert to a[i-1]尖飞、a[i-2]性置、a[i-3]...
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }

優(yōu)化

插入排序還有很多可以優(yōu)化的地方,這里例舉兩個(gè)案例.

• 采用二分查找法來減少比較操作的次數(shù).

  public static void sort(Comparable[] a) {
      int length = a.length;
      for (int i = 1; i < length; i++) {
          // binary search to determine index j at which to insert a[i]
          Comparable v = a[i];
          int lo = 0, hi = i;
          while (lo < hi) {
              int mid = lo + (hi - lo) / 2;
              if (less(v, a[mid]))
                  hi = mid;
              else
                  lo = mid + 1;
          }
  
          // insertion sort with "half exchanges"
          // (insert a[i] at index j and shift a[j], ..., a[i-1] to right)
          for (int j = i; j > lo; --j)
              a[j] = a[j - 1];
          a[lo] = v;
      }
  }
  

• 在內(nèi)循環(huán)中將較大的元素都向右移動(dòng)而不總是交換兩個(gè)元素(訪問數(shù)組的次數(shù)能夠減半)

  public static void sort(Comparable[] a) {
      int length = a.length;
  
      // put smallest element in position to serve as sentinel
      int exchanges = 0;
      for (int i = length - 1; i > 0; i--) {
          if (less(a[i], a[i - 1])) {
              exch(a, i, i - 1);
              exchanges++;
          }
      }
      if (exchanges == 0)
          return;
  
      // insertion sort with half-exchanges
      for (int i = 2; i < length; i++) {
          Comparable v = a[i];
          int j = i;
          while (less(v, a[j - 1])) {
              a[j] = a[j - 1];
              j--;
          }
          a[j] = v;
      }
  }
  

希爾排序

希爾排序,也稱遞減增量排序算法,它是基于插入排序的一種更高效的改進(jìn)版本.

由于插入排序?qū)τ诖笠?guī)模亂序數(shù)組效率并不高,因?yàn)樗粫?huì)交換相鄰的元素,因此元素只能一點(diǎn)一點(diǎn)地從數(shù)組的一端移動(dòng)到另一端.

而希爾排序?yàn)榱思涌焖俣群?jiǎn)單地改進(jìn)了插入排序,交換不相鄰的元素以對(duì)數(shù)組的局部進(jìn)行排序,并最終用插入排序?qū)?strong>局部有序的數(shù)組排序.

希爾排序的思想是使數(shù)組中任意間隔為h的元素都是有序的,可以說一個(gè)h有序的數(shù)組就是h個(gè)互相獨(dú)立的有序數(shù)組編織在一起組成的一個(gè)數(shù)組.

以23, 10, 4, 1的步長(zhǎng)序列進(jìn)行希爾排序

代碼實(shí)現(xiàn)

public static void sort(Comparable[] a) {
        int h = 1;
        while (h < a.length / 3) {
            // h sequence 1,4,13,40,121,364,1093,...
            h = h * 3 + 1;
        }
        while (h >= 1) {
            for (int i = h; i < a.length; i++) {
                // a[i] insert to a[i-h],a[i-2*h],a[i-3*h]...
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }

歸并排序

歸并排序是分治算法的典型應(yīng)用.所謂歸并即是將兩個(gè)有序的數(shù)組歸并成一個(gè)更大的有序數(shù)組.

它有一個(gè)主要的缺點(diǎn)就是它需要額外的空間(輔助數(shù)組)并且所需的額外空間和N成正比.

合并過程

1. 申請(qǐng)空間,使其大小為兩個(gè)已有序序列之和,該空間用于存放合并后的序列

2. 聲明兩個(gè)指針,最初位置分別為兩個(gè)有序序列的起始位置

3. 比較兩個(gè)指針?biāo)赶虻脑?選擇相對(duì)小的元素放入合并空間中,并移動(dòng)指針到下一個(gè)位置

4. 重復(fù)步驟3直到某一指針到達(dá)序列尾部

5. 將另一序列剩下的所有元素直接放入合并序列尾

自頂向下的歸并排序

自頂向下即是從頂部化整為零地遞歸解決問題.

例如:要對(duì)數(shù)組a[lo..hi]進(jìn)行排序,需要先將它切分為a[lo..mid]與a[mid+1..hi]兩部分,分別通過遞歸調(diào)用將它們單獨(dú)排序,最后將有序的子數(shù)組歸并為最終的排序結(jié)果.

// 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) {
        // copy a[] 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++];
            }
        }
    }
    
// 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);
    }

自底向上的歸并排序

自底向上則是循序漸進(jìn)地解決問題.

實(shí)現(xiàn)思路是先歸并那些微型數(shù)組,然后再成對(duì)歸并得到的子數(shù)組,直到將整個(gè)數(shù)組歸并在一起.

可以先進(jìn)行兩兩歸并(每個(gè)元素想象成一個(gè)大小為1的數(shù)組),然后進(jìn)行四四歸并(將兩個(gè)大小為2的數(shù)組歸并成一個(gè)有四個(gè)元素的數(shù)組),然后是八八歸并.....(一直下去)在每一輪歸并中,最后一次歸并的第二個(gè)子數(shù)組可能比第一個(gè)子數(shù)組要小,如果不是的話所有歸并中兩個(gè)數(shù)組大小都應(yīng)該一致.

//merge函數(shù)與自頂向下中的一致
public static void sort(Comparable[] a) {
        int N = a.length;
        Comparable[] aux = new Comparable[N];
        for (int len = 1; len < N; len *= 2) {
            for (int lo = 0; lo < N - len; lo += len + len) {
                int mid = lo + len - 1;
                int hi = Math.min(lo + len + len - 1, N - 1);
                merge(a, aux, lo, mid, hi);
            }
        }
    }

優(yōu)化

• 如果數(shù)組很小,那么頻繁的遞歸調(diào)用效率會(huì)很差,所以可以使用插入排序(或選擇排序等)來處理小規(guī)模的子數(shù)組.

  private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
      int i = lo, j = mid + 1;
      for (int k = lo; k <= hi; k++) {
          if (i > mid) {
              dst[k] = src[j++];
          } else if (j > hi) {
              dst[k] = src[i++];
          } else if (less(src[j], src[i])) {
              dst[k] = src[j++];
          } else {
              dst[k] = src[i++];
          }
      }
  }
  
  private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
      // if (hi <= lo) return;
      if (hi <= lo + CUTOFF) {
          insertionSort(dst, lo, hi);
          return;
      }
      int mid = lo + (hi - lo) / 2;
      sort(dst, src, lo, mid);
      sort(dst, src, mid + 1, hi);
  
      // using System.arraycopy() is a bit faster than the above loop
      if (!less(src[mid + 1], src[mid])) {
          System.arraycopy(src, lo, dst, lo, hi - lo + 1);
          return;
      }
  
      merge(src, dst, lo, mid, hi);
  }
  
  // using insertion sort handle small array
  private static void insertionSort(Comparable[] a, int lo, int hi) {
      for (int i = lo; i <= hi; i++) {
          for (int j = i; j > lo && less(a[j], a[j - 1]); j--) {
              exch(a, j, j - 1);
          }
      }
  }
  
  public static void sort(Comparable[] a) {
      Comparable[] aux = a.clone();
      sort(aux, a, 0, a.length - 1);
  }
  

快速排序

快速排序又稱劃分交換排序,它也是一種分治的排序算法.

快速排序有一個(gè)潛在的缺點(diǎn),在切分不平衡時(shí)這個(gè)程序可能會(huì)極為低效,所以需要在快速排序前將數(shù)組隨機(jī)排序來避免這種情況.

它將一個(gè)數(shù)組切分成兩個(gè)子數(shù)組,將兩部分獨(dú)立地排序.它與歸并排序不同的地方在于:

• 歸并排序?qū)?shù)組分成兩個(gè)子數(shù)組分別排序,最終將有序的子數(shù)組歸并以致整個(gè)數(shù)組排序.

• 快速排序?qū)?shù)組排序的方式則是當(dāng)兩個(gè)子數(shù)組都有序時(shí),整個(gè)數(shù)組也就是有序的了.

• 在歸并排序中,遞歸調(diào)用發(fā)生在處理整個(gè)數(shù)組之前;而在快速排序中,遞歸調(diào)用發(fā)生在處理整個(gè)數(shù)組之后.

• 在歸并排序中,一個(gè)數(shù)組會(huì)被等分為兩半,而在快速排序中,切分的位置取決于數(shù)組的內(nèi)容.

運(yùn)行過程

1. 先從數(shù)列中挑選出一個(gè)基準(zhǔn),可以為a[lo],它是被確認(rèn)為排定的元素.

2. 從數(shù)組的左端(左指針)開始向右掃描直到找到一個(gè)大于等于基準(zhǔn)的元素.

3. 從數(shù)組的右端(右指針)開始向左掃描直到找到一個(gè)小于等于基準(zhǔn)的元素.

4. 這兩個(gè)元素即是沒有排定的,交換它們的位置(保證了左指針i的左側(cè)元素都不大于基準(zhǔn),右指針j的右側(cè)元素都不小于基準(zhǔn)).

5. .當(dāng)兩個(gè)指針相遇時(shí),將基準(zhǔn)和左子數(shù)組最右側(cè)的元素(a[j])交換然后返回j即可.

代碼實(shí)現(xiàn)

// 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; // left point
        int j = hi + 1; // right point
        Comparable v = a[lo]; // partition element

        while (true) {
            // scan left point
            while (less(a[++i], v)) {
                if (i == hi)
                    break;
            }

            // scan right point
            while (less(v, a[--j])) {
                if (j == lo)
                    break;
            }

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

            exch(a, i, j);
        }

        // put partition element v to a[j]
        exch(a, lo, j);
        // now a[lo..j-1] <= a[j] <= a[j+1..hi]
        return j;
    }
    
    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);
    }
    
    public static void sort(Comparable[] a) {
        shuffle(a);
        sort(a, 0, a.length - 1);
    }
    
    // random sort an array
    private static void shuffle(Object[] a) {
        if (a == null)
            throw new IllegalArgumentException("array is null.");
        Random random = new Random();
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int j = i + random.nextInt(N - i);
            Object temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

三向切分的快速排序

當(dāng)存在大量重復(fù)元素的情況下,快速排序的遞歸性會(huì)使元素全部重復(fù)的子數(shù)組經(jīng)常出現(xiàn),這就有很大的改進(jìn)潛力,將當(dāng)前快速排序從線性對(duì)數(shù)級(jí)別的性能提升至線性級(jí)別.

一個(gè)簡(jiǎn)單的思路是將數(shù)組切分為三部分,分別對(duì)應(yīng)小于、等于蚕苇、大于切分元素的數(shù)組元素.

在實(shí)現(xiàn)中,維護(hù)一個(gè)左指針lt使得a[lo..lt-1]的元素都小于基準(zhǔn),右指針gt使得a[gt+1..hi]中的元素都大于基準(zhǔn),一個(gè)指針i使得a[lt..i-1]中的元素都等于基準(zhǔn),a[i..gt]中的元素都還未確定.

1. a[i]小于基準(zhǔn),將a[lt]和a[i]交換,lt++&i++.

2. a[i]大于基準(zhǔn),將a[gt]和a[i]交換,gt--.

3. a[i]等于基準(zhǔn),i++.

以上操作都會(huì)保證數(shù)組元素不變且縮小gt-i的值(這樣循環(huán)才會(huì)結(jié)束).除非和切分元素相等,其他元素都會(huì)被交換.

// 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, i = lo + 1, gt = hi;
        Comparable v = a[lo]; // partition element

        // a[lo..lt-1] < a[lt..gt] < a[gt+1..hi]
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0) {
                exch(a, i++, lt++);
            } else if (cmp > 0) {
                exch(a, i, gt--);
            } else {
                i++;
            }
        }
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

堆排序

堆排序是基于堆的優(yōu)先隊(duì)列實(shí)現(xiàn)的一種排序算法.

優(yōu)先隊(duì)列

優(yōu)先隊(duì)列是一種支持刪除最大(最小)元素和插入元素的數(shù)據(jù)結(jié)構(gòu),它的內(nèi)部是有序的,任意優(yōu)先隊(duì)列都可以變成一種排序方法.

堆

堆是一種數(shù)據(jù)結(jié)構(gòu),它通痴饣。可以被看作為一棵樹的數(shù)組對(duì)象.將根節(jié)點(diǎn)作為最大數(shù)的叫做最大堆,反之,將根節(jié)點(diǎn)作為最小數(shù)的叫做最小堆.

堆是一個(gè)近似完全二叉樹的結(jié)構(gòu),同時(shí)又滿足了堆的性質(zhì):每個(gè)元素都要保證大于(小于)等于它的子節(jié)點(diǎn)的元素.

在一個(gè)堆中,根據(jù)根節(jié)點(diǎn)的索引位置不同,計(jì)算父節(jié)點(diǎn)與子節(jié)點(diǎn)位置的算法也不同.

• 當(dāng)數(shù)組起始位置為0時(shí),位置k的節(jié)點(diǎn)的父節(jié)點(diǎn)為(k - 1)/2,它的兩個(gè)子節(jié)點(diǎn)為2k+1,2k+2.

• 當(dāng)數(shù)組起始位置為1時(shí)(即不使用索引0),位置k的節(jié)點(diǎn)的父節(jié)點(diǎn)為k/2,它的兩個(gè)子節(jié)點(diǎn)為2k,2k+1.

為了保證堆有序,需要支持兩個(gè)操作用于打破堆的狀態(tài),然后再遍歷堆并按照要求將堆的狀態(tài)恢復(fù),這個(gè)過程叫做堆的有序化.

• 由下至上的堆有序化(上浮) : 如果堆的有序狀態(tài)因?yàn)槟硞€(gè)節(jié)點(diǎn)變得比它的父節(jié)點(diǎn)更大而被打破時(shí),那么就需要通過交換它和它的父節(jié)點(diǎn)來修復(fù)堆,將這個(gè)節(jié)點(diǎn)不斷向上移動(dòng)直到遇到了一個(gè)更大的父節(jié)點(diǎn).(如果是最小堆,比較的邏輯相反).

  // 在本文中,均不使用數(shù)組的0索引
   private void swim(int k) {
    while (k > 1 && less(k/2, k)) {
        exch(a,k, k/2);
        k = k/2;
     }
  }
  

• 由上至下的堆有序化(下沉) : 如果堆的有序狀態(tài)因?yàn)槟硞€(gè)節(jié)點(diǎn)變得比它的兩個(gè)子節(jié)點(diǎn)或是其中之一更小了而被打破時(shí),需要通過將它和它的兩個(gè)子節(jié)點(diǎn)中的較大者交換來修復(fù)堆,將這個(gè)節(jié)點(diǎn)向下移動(dòng)直到它的子節(jié)點(diǎn)都比它更小或是到達(dá)了堆的底部.(如果是最小堆,比較的邏輯想法)

    // n為數(shù)組長(zhǎng)度
    private void sink(int k) {
      while (2*k <= n) {
          int j = 2*k;
          if (j < n && less(j, j+1)) j++;
          if (!less(a[k],a[j])) break;
          exch(a,k, j);
          k = j;
      }
  }
  

運(yùn)行過程

堆排序可以分為兩個(gè)階段.

1. 堆的構(gòu)造階段,將原始數(shù)組重新組織安排進(jìn)一個(gè)堆中.從右至左用sink()函數(shù),構(gòu)造子堆,數(shù)組的每個(gè)位置都已經(jīng)是一個(gè)子堆的根節(jié)點(diǎn).只需要掃描數(shù)組中的一半元素,因?yàn)槲覀兛梢蕴^大小為1的子堆.最后在位置1上調(diào)用sink()函數(shù),結(jié)束掃描.

2. 下沉排序階段,從堆中按遞減順序取出所有元素并得到排序結(jié)果.將堆中的最大元素刪除,然后放入堆縮小后數(shù)組中空出的位置.

代碼實(shí)現(xiàn)

public static void sort(Comparable[] a) {
        int N = a.length;
        // construction max heap
        for (int k = N / 2; k >= 1; k--) {
            sink(a, k, N);
        }
        // sink sort
        while (N > 1) {
            // the biggest element (root) swap smallest element then heap shrink
            exch(a, 1, N--);
            // new root element sink
            sink(a, 1, N);
        }
    }
    
    private static void sink(Comparable[] pq, int k, int n) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(pq, j, j + 1))
                j++;
            if (!less(pq, k, j))
                break;
            exch(pq, k, j);
            k = j;
        }
    }

    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i - 1].compareTo(pq[j - 1]) < 0;
    }

    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i - 1];
        pq[i - 1] = pq[j - 1];
        pq[j - 1] = swap;
    }   

總結(jié)

在大多數(shù)實(shí)際情況中,快速排序是最佳選擇.如果穩(wěn)定性很重要而空間又不是問題的情況下,歸并排序可能是最好的.但是在運(yùn)行時(shí)間至關(guān)重要的任何排序應(yīng)用中應(yīng)該認(rèn)真地考慮使用快速排序.

在JDK中,Arrays.sort()選擇了根據(jù)不同的參數(shù)類型,來使用不同的排序算法.如果是原始數(shù)據(jù)類型則使用三向切分的快速排序,對(duì)引用類型則使用歸并排序.

end

• Author : SylvanasSun

• Email : sylvanassun_xtz@163.com

• 文中的完整實(shí)現(xiàn)代碼見我的GitHub & Gist

• 本文參考資料引用自<<Algorithms,4th>> & WikiPedia