?算法導論第2版的7-6，首先理解題目就花了n久，從網上找了些思路，下面具體來說

題目內容：

考慮這樣的一種排序問題，即無法準確地知道待排序的各個數字到底是多少。對于其中的每個數字，我們只知道它落在實軸上的某個區間內。亦即，給定的是n個形如[ai, bi]的閉區間，其中ai<= bi。算法的目標是對這些區間進行模糊排序（fuzzy-sort），亦即，產生各區間的一個排列<i1, i2, ..., in>，使得存在一個cj屬于區間[aij, bij]，滿足c1 <= c2 <= ... <= cn。
a) 為n個區間的模糊排序設計一個算法。你的算法應該具有算法的一般結構，它可以快速排序左部端點（即各ai），也要能充分利用重疊區間來改善運行時間。（隨著各區間重疊得越來越多，對各區間進行模糊排序的問題會變得越來越容易。你的算法應能充分利用這種重疊。）

b) 證明：在一般情況下，你的算法的期望運行時間為Θ(nlgn)，但當所有的區間都重疊時，期望的運行時間為Θ(n)（亦即，當存在一個值x，使得對所有的i，都有x∈[ai, bi]）。你的算法不應顯式地檢查這種情況，而是應隨著重疊量的增加，性能自然地有所改善。

算法思路：這是對一組給定的區間序列來模糊排序，可以利用快速排序的思想，對區間序列進行劃分。但此時的主元區間元素是一個區間元素集合中所有區間元素的公共區間（交集），即是說該集合中的所有區間元素都是“相等的”或者說“任意序都是有序的”。初始時，算法任選一個區間元素作為主元（同快速排序的哨兵元素）。如果某個區間元素嚴格小于主元，則將其放到序列左邊；如果其嚴格大于主元，則將其放到序列右邊；否則，說明該區間元素與主元相交，則更新主元區間大小為該相交的區間部分，該區間元素放置在整個序列的中間部分(對這部分區間序列可以不作嚴格排序，因為只需要滿足<存在一個cj..>),然后遞歸的處理左邊和右邊區間序列即可

算法描述：

private static int[] patition(Interval[] Int, int p, int r)
{
      Interval pivot = new Interval(Int[r].begin,Int[r].end);
      int i = p;
      int j = p;
     int k = r;
      while (j < k)
      {
           if (Int[j].end <= pivot.begin)
          {
           Interval temp0 = Int[i];
            Int[i] = Int[j];
           Int[j] = temp0;
            i++;
           j++;
           }
         else if (Int[j].begin >=pivot.end)
        {
          Interval temp1 = Int[k];
            Int[k] = Int[j];
            Int[j] = temp1;
            k--;
        }
        else
        {
          pivot.begin=(Int[j].begin>pivot.begin?Int[j].begin:pivot.begin);
           pivot.end=(Int[j].end<pivot.end?Int[j].end:pivot.end);
           j++;
        }
       }
      return new int[] {i,k};
}

變量i和k的作用就是標識左區間的結束位置+1和右區間開始位置-1，返回一個{i，k}數組便于排序算法使用，下面是排序過程

public static void quickSort(Interval[] Int,int p,int r)
{
     if(p<r)
     {
          int[] q=patition(Int, p, r);
         quickSort(Int, p, q[0]-1);
         quickSort(Int, q[1]+1, r); 
      }
}

算法性能簡單分析：利用快速排序思想，分析每步運算期望時間復雜度為Θ(nlgn)，并充分利用的區間重疊減少運行時間，當所有區間都有相同重疊部分時，這時patition過程消耗Θ(n)，左右區間都為空，故不需要再作遞歸，整個時間復雜度滿足要求。當然，對中間重疊部分可以作排序處理(比如快排每個區間的左端點值)顯得更嚴謹，也可能是多此一舉吧，不然為什么稱為"模糊"排序呢？最后是Interval的定義和測試

class Interval

{
    public float begin;
    public float end;

   public Interval(float a, float b)
   {
       this.begin = a;
        this.end = b;
    }

    public static void main(String[] args)
   {
     Interval[] b = { new Interval(1, 2), new Interval(0.5f, 1), new Interval(3, 4),

                         new Interval(7.5f, 8.0f), new Interval(5, 8), new Interval(3, 4.5f) };

     quickSort(b, 0, 5);
   }
}