快速排序 求第k大数

1. 快排利用标兵的思想，但每一次都是比较范围大小，没有精确排序。
2. 同样适用于快速求解 需要定性的范围问题，例如：第k大(将前后定性大小，但不用排序).
3. 求解第k大：通过判断下标，只计算有k的那一半。
4. 快排是从广到窄的递归。

5. 快排：a.枢轴要回归.b.i总是指向偏大的值.

   void quick_sort(int *A,int x,int y)//左闭右闭
   {
   if(x < y)//当有1或0个元素是退出
   {
     int i = x;
     int j = y;
   //取中值，优化快排速度,优化效果明显，4%~5%。
     int m = x + (y-x)/2;
     if(A[x] > A[m])
         if(A[x] > A[y])
             if(A[m] > A[y])
                 swap(A[m],A[y]);
         else
             swap(A[x],A[y]);
     else//A[x]<A[m]
         if(A[x] > A[y])
             swap(A[x],A[y]);
         else
             if(A[y] > A[m])
                 swap(A[m],A[y]);
   //优化结束
     int key = A[y];
   
     while(true)
     {
         while(i < j && A[i] <= key)//因为先从左开始遍历，所以A[i]一定是偏大的值
             ++i;
         while(i < j && A[j] >= key)
             --j;
         if(i < j)
             swap(A[i],A[j]);
         else
             break;
         ++i;//不能同时--j,否则会有bug。
     }
     swap(A[i],A[y]);//将枢纽归位
   
     quick_sort( A,x,i-1);
     quick_sort( A,i+1,y);
   }
   }

（编辑：厦门网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!