区间模糊排序---快排思路的应用

  1 #include<iostream>
  2 #include<ctime>
  3 using namespace std;
  4 #define max(a,b) (a>b)?a:b
  5 #define min(a,b) (a>b)?b:a
  6 class Interval
  7 {
  8 public:
  9     double leftbound;
 10     double rightbound;
 11     Interval(int a, int b) :leftbound(a), rightbound(b){}
 12     Interval(Interval &i){ leftbound = i.leftbound; rightbound = i.rightbound; }
 13     Interval(){}
 14 };
 15 void swap(Interval &a, Interval &b)
 16 {
 17     Interval temp = a;
 18     a = b;
 19     b = temp;
 20 
 21 }
 22 void display(Interval a[], int begin, int end)
 23 {
 24     for (int i = begin; i <= end; ++i)
 25         cout << "[" << a[i].leftbound << "," << a[i].rightbound << "]" << ",";
 26     cout << endl;
 27 }
 28 void partition(Interval a[], int begin, int end, int &ini, int &ter)   //参数ini、ter是引用，是为了作为返回值
 29 {
 30 
 31     Interval pivot = a[begin];        //主元区间
 32     ini = begin;
 33     ter = end + 1;            //注意，这里ter从数组外部开始
 34 
 35     int cur = begin + 1;
 36     while (cur < ter && cur<end)
 37     {
 38         if (a[cur].rightbound <= pivot.leftbound && ini<end)        //小于主元区间
 39         {
 40             ++ini;
 41             swap(a[cur], a[ini]);
 42             ++cur;
 43             //cout << "1: ";
 44             //display(a, begin, end);
 45         }
 46         else if (a[cur].leftbound >= pivot.rightbound && ter>begin) //大于主元区间
 47         {
 48             --ter;
 49             swap(a[cur], a[ter]);
 50             //cout << "2: ";
 51             //display(a, begin, end);
 52 
 53         }
 54         else            //和主元区间相等， 所以取交集作为新的主元
 55         {
 56             pivot.leftbound = max(pivot.leftbound, a[cur].leftbound);
 57             pivot.rightbound = min(pivot.rightbound, a[cur].rightbound);
 58             //cout << "pivot: " << pivot.leftbound<<" ,"<<pivot.rightbound << endl;
 59             ++cur;
 60             //cout << "3: ";
 61             //display(a, begin, end);
 62         }
 63     }
 64     swap(a[ini], a[begin]);    //调整
 65 
 66     --ini;
 67     //cout << "ini: " << ini <<"  "<< "ter: " << ter << endl;
 68     //display(a, begin,end);
 69 
 70 
 71 }
 72 void fuzzySortingOfInterval(Interval a[], int begin, int end)
 73 {
 74     if (begin < end)
 75     {
 76         int ini, ter;
 77         partition(a, begin, end, ini, ter);
 78         fuzzySortingOfInterval(a, begin, ini);
 79         fuzzySortingOfInterval(a, ter, end);
 80     }
 81 }
 82 int main()
 83 {
 84     srand(time(NULL));
 85     const int size = 8;
 86     Interval a(28508, 31359), b(4712, 30466), c(23267, 30245), d(7134, 8098), e(25400, 26351), f(8079, 29052), g(31163, 31738), h(6346, 24352);
 87     Interval array[size] = { a, b, c, d, e, f, g, h };
 88     Interval *array = new Interval[size];
 89     for (int i = 0; i < size; ++i)
 90     {
 91     array[i].leftbound = rand() % 100;
 92     array[i].rightbound = rand() % 100;
 93     while (array[i].rightbound < array[i].leftbound)
 94     array[i].rightbound = rand() % 100;
 95     }
 96     display(array, 0, size - 1);
 97     fuzzySortingOfInterval(array, 0, size - 1);
 98     display(array, 0, size - 1);
 99     system("pause");
100 }

关于算法呢，其实很简单，区间的比较结果有三种：小于，等于（有交集），大于，这里的优化在于，每次有等于情况时都取交集作为新的主元，这样的好处在于：扩大中间等于的区域，减少递归深度。

关于代码呢，这里partition函数我们要返回一个区间，是要返回其左右的数字，而C++只能有一个返回值，因此这里借助了引用返回的技巧来实现，另一方面，我们可以借助STL 的pair类型

pair<int,int>& partition(int begin,int end)

{　　
　　.....

　　

　　return pair<int,int>(ini,ter);

}

调用时 ini=partiton(begin,end).first;ter=partition(begin,end).second;