两种快速排序和找第k大数

快速排序和找第k大数几乎用的是相同代码片段。

和二分查找一样，快速排序也很容易出错。

void swap(int *a,int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void quick_sort1(int *a,int l,int r)
{
    if (l >= r) return;
    int k = a[l];
    int i = l; int j = r + 1;
    for (;;)
    {
        do i++; while (i <= r && a[i] < k);
        do j--; while (a[j] > k);
        if ( i > j ) break;
        swap(a+i,a+j);
    }
    swap(a+l,a+j);
    quick_sort1(a,l,j-1);
    quick_sort1(a,j+1,r);
}


void quick_sort2(int *a,int r)
{
    if (l >= r) return;
    int k = a[l];
    int i = l;
    for (int j = l + 1; j <= r; j++)
    {
        if (a[j] < k)
        {
            i++;
            swap(a+i,a+j);
        } 
    }
    swap(a+l,a+i);
    quick_sort2(a,i-1);
    quick_sort2(a,i+1,r);
}


int find_kth2(int *a,int r,int k)
{
   if (l == r) 
   {
       return a[l];
   }
   int m = a[l];
   int i = l;
   for (int j = l + 1; j <= r; j++)
   {
       if (a[j] < m)
       {
           i++;
           swap(a+j,a+i);
        }
   }
   swap(a+l,a+i);
   if (k <= i - l) return find_kth2(a,i-1,k);
   else if ( k == i - l + 1) return find_kth2(a,i,1);
   else return find_kth2(a,r,k-(i-l+1));
}

int find_kth1(int *a,int k)
{
    if ( l == r ) return a[l];
    int m = a[l];
    int i = l; int j = r + 1;
    for (;;)
    {
        do i++; while (i <= r&& a[i] < m);
        do j--; while ( a[j] > m);
        if ( i > j) break;
        swap(a+i,a+j);
    if ( k <= j - l) return find_kth1(a,j-1,k);
    else if ( k == j - l + 1) return find_kth1(a,j,1);
    else return find_kth1(a,k-(j-l+1));

}