算法描述

1. 对于一个数组中的元素(有重复)进行排序
2. 如果数组元素个数大于一
3. 随机选取一个基准
   1. 将小于基准的元素放到基准的左边
   2. 将大于基准的元素放到基准的右边
4. [如果有重复元素]
   1. 将和基准相等的元素放到基准位置,连续排列
   2. 注意 :
      1. 在基准左侧找到的等值元素要,和放到基准左边
      2. 在右侧找到的要放到右边, 否则会使得小元素放到右边,大元素在左边的错误
5. 递归的对于基准左右的数组进行上述操作

   代码

   ```cpp

   include

   include

   include

   include

   //元素个数 const int N = 20; //元素范围 const int MAXVAU = 100; //数组 int a[N]; using namespace std;

//随机获取 int partitionRandom(int q,int r){ //随机获取基准下标 [q : r] 中的数字
int p = rand()%(r-q+1)+q; //将基准元素放到待序列最左边 int t = a[p]; a[p] = a[q]; a[q] = t; //x 为基准值 int i=q,j=r+1,x = a[q]; //将小于基准值的元素放到基准值 左边 , 大于的放到右边 while(1){ while(a[++i]x ); if(i>=j){ break; } t = a[i]; a[i] = a[j]; a[j] = t; }; //?????为什么选择j a[q] = a[j]; a[j] = x; return j; } void swap(int a[], int c, int d) { int t = a[c]; a[c] = a[d]; a[d] = t; }

//将和a[pivort]的值相同的元素集中 void Amass(int a[], int p, int r, int pivort, int& p1, int& pr) { int num1 = 0, num2 = 0;

for (int i = p; i <= r; i++) {
    if (a[i] == a[pivort] && i != pivort) {
        if (i < pivort - num1) {//左边重复的
            num1++;
            swap(a, i, pivort - num1);
        }
        else if (i > pivort + num2) {//右边重复的
            num2++;
            swap(a, i, pivort + num2);
        }
    }
}
p1 = pivort - num1;
pr = pivort + num2;

} //快速排序 void qsort(int q,int r){ if(q<r){ int pl,pr; //划分 int p = partitionRandom(q,r); //将和a[p]相等的元素聚集到p的两边 (针对有重复的元素) Amass(a,q,r,p,pl,pr); //对划分的子序列排序 qsort(q,pl-1);//左 qsort(pr+1,r);//右边 } }

int main() { srand(time(NULL)); int n = 0; while(1){ //生成随机生成数组 并且 输出原数组 printf(“原数组 : “); for(int i = 0;i0&&a[i]<a[i-1]){ printf(“illegal!\n”); } printf(“%3d “,a[i]); } printf(“\n”); system(“pause”); } return 0; }

```