1 //============================================================================ 2 // Name        : C++Basic.cpp 3 // Author      : Laughing 4 // Version     : 5 // Copyright   : All Right Reserved 6 // Description : 快速排序：采用分治法 7 //============================================================================ 8  9 #include 
     
      10 #include 
      
       11 #include 
       
        12 using namespace std;13 /**14  *快速排序：采用分治法15  */16 int partition(int array[], int start, int end) { //返回基准的下标17     if (array == NULL) {18         cout << "数组为空" << endl;19         throw new exception();20     }21     int base = rand() % (end - start + 1); //若基准为随机元素，则递归次数不定，即时间复杂度有差别！★22 //    int base = 0;//若基准为数组第一个元素或某个固定元素，则递归次数固定。23     cout << "基准为:" << base << endl;24     int basic = array[base];//basic为基准25     while (start < end) {26         while (start < end && array[end] > basic) {27             end--;28         }29         if (start < end) { //★30             array[base] = array[end];31             base = end; //改变基准指向的下标32         }33         while (start < end && array[start] < basic) {34             start++;35         }36         if (start < end) { //★37             array[base] = array[start];38             base = start; //改变基准指向的下标39         }40     }41     array[base] = basic;42     return base;43 }44 void QuickSort(int array[], int start, int end) {45     if (start < end) {46         int base = partition(array, start, end);47         QuickSort(array, 0, base - 1);48         QuickSort(array, base + 1, end);49     }50 }51 int main() {52 //    srand((int)time(0));//初始化随机种子：若不初始化，每次递归的随机种子不会变化，递归次数固定。53     int array[] = { 4, 3, 2, 1, 9, 7, 5, 8, 6 };54     int size = sizeof(array) / sizeof(*array); //求数组长度55     QuickSort(array, 0, size - 1);56     for (int i = 0; i < size; i++) {57         cout << array[i] << endl;58     }59     return 0;60 }