基本的快速排序和高级的快速排序--（使用递归）

?

/*插入排序*/void insertSort(int * a,int begin,int end){int tmp;for(int j = begin + 1;j<= end;j++){tmp = a[j];int i = j -1;//while(a[i] < a[j]) //不能这么写，因为a[i] 会被覆盖掉，此时的a[i]已不是彼时的a[i]while(tmp < a[i]){a[i + 1] = a[i];i --;}a[i + 1] = tmp;}}/*这个算法来自sgi stl*/int middle(int a,int b,int c) {if(a < b) //其实就是在这个大的条件下，依次return b ,c a{if(b < c) // a < b < creturn b;else if(a < c) // a < b ; b > = c ; a < creturn c;else    // a < b ; a >= c return a;}else {if(b > c) // a > b > creturn b;else if(a > c) // a > b ;b <= c;return c;else             // a > b ; a　< creturn a;}}/*首先，分划元素k 取得是a[begin],a[middel],a[end]的中值其次，如果分得的子数组长度小于等于3，则调用insertSort*/void AdvancedQSort(int * a,int begin,int end){if(begin >= end)return ;if(end - begin <= 3)insertSort(a,begin,end);else{int i = begin,j = end,k = middle(a[i],a[j],a[(i + i) / 2]),tmp;while(i < j) //{i = i + 1;while(a[i] < k)i ++;j = j - 1;while(a[j] > k)j --;if(i < j){tmp = a[i];a[i] = a[j];a[j] = tmp;}}tmp = a[begin]; //注意此时a[begin] 与 a[j] 交换a[begin] = a[j];a[j] = tmp;AdvancedQSort(a,begin,j - 1);AdvancedQSort(a,j + 1,end);}}