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 }