C语言学习，算法设计，线性时间选择

Question

我在学习线性时间选择算法，编写如下程序，算法要求是找到n个元素中第k小的元素：

//线性时间选择
#include <stdio.h>
void bubbleSort(int *a,int p,int r);
int Partition(int *a,int p,int r,int val);
int Select(int *a,int p,int r,int k);
void swap(int *u,int *v);

void swap(int *u,int *v)
{
   int temp;
   temp=u;
   u=v;
   v=temp;
}
void bubbleSort(int *a,int p,int r)
{ 
    int i,j;
    for(i=p; i<r; i++)
    {
        for( j=i+1; j<=r; j++)
        {
            if(a[j]<a[i]) swap(a[i],a[j]);
        }
    }
}

int Partition(int *a,int p,int r,int val)
{
    int pos;
    int q,i,j,x;
    for( q=p; q<=r; q++)
    {
        if(a[q]==val)
        {
            pos=q;
            break;
        }
    }
    swap(a[p],a[pos]);

    i=p; j=r+1; x=a[p];
    while(1)
    {
        while(a[++i]<x && i<r);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a[i],a[j]);
    }
    a[p]=a[j]; a[j]=x;
    return j;
}

int Select(int *a,int p,int r,int k)
{
    int s,t;
    int i,j,n,x;
    if(r-p<75)
    {
        bubbleSort(a,p,r);
        return a[p+k-1];
    }
    //找中位数的中位数，r-p-4即上面所说的n-5
    for( i=0; i<=(r-p-4)/5; i++) //把每个组的中位数交换到区间[p,p+(r-p-4)/4]
    {
        s=p+5*i; t=s+4;
        for( j=0; j<3; j++) //冒泡排序，从后开始排，结果使得后三个数是排好顺序的（递增）
        {
            for( n=s; n<t-j; n++)
            {
                if(a[n]>a[n+1]) swap(a[n],a[n+1]);
            }
        }
        swap(a[p+i],a[s+2]);//交换每组中的中位数到前面
    }
    //(r-p-4)/5表示组数-1，则[p,p+(r-p-4)/5]的区间长度等于组数
    x=Select(a,p,p+(r-p-4)/5,(r-p+1)/10);//求中位数的中位数
    /*
    (r-p+1)/10 = (p+(r+p-4)/5-p+1)/2
    */
    i=Partition(a,p,r,x); j=i-p+1;
    if(k<=j) return Select(a,p,i,k);
    else return Select(a,i+1,r,k-j);
}
int main(void)
{
    int x,i;
    //数组a存了0-79
    int a[80]= {3,1,7,6,5,9,8,2,0,4,13,11,17,16,15,19,18,12,10,14,23,21,27,26,25,29,28,22,20,24,33,31,37,36,35,39,38,32,30,34,43,41,47,46,45,49,48,42,40,44,53,51,57,56,55,59,58,52,50,54,63,61,67,66,65,69,68,62,60,64,73,71,77,76,75,79,78,72,70,74,
               };
    scanf("%d",&x); 
    printf("The %d smallest number is %d\n",x,Select(a,0,79,x));
    return 0;
}

运行结果如下：

请问是哪有问题，应该怎么修改。

Answer 1

swap函数有问题啊，int指针和int值怎么能直接相等呢。修改如下

void swap(int *u,int *v)
{
   int temp;
   temp=*u;
   *u=*v;
   *v=temp;
}

22行的 swap(a[i], a[j]); 改成 swap(&a[i], &a[j]);
下面swap交换的地方，都需要加&
修改后运行结果：

完整代码修改如下：

//线性时间选择
#include <stdio.h>
void bubbleSort(int* a, int p, int r);
int Partition(int* a, int p, int r, int val);
int Select(int* a, int p, int r, int k);
void swap(int* u, int* v);

void swap(int* u, int* v)
{
    int temp;
    temp = *u;
    *u = *v;
    *v = temp;
}
void bubbleSort(int* a, int p, int r)
{
    int i, j;
    for (i = p; i < r; i++)
    {
        for (j = i + 1; j <= r; j++)
        {
            if (a[j] < a[i]) swap(&a[i], &a[j]);
        }
    }
}

int Partition(int* a, int p, int r, int val)
{
    int pos;
    int q, i, j, x;
    for (q = p; q <= r; q++)
    {
        if (a[q] == val)
        {
            pos = q;
            break;
        }
    }
    swap(&a[p], &a[pos]);

    i = p; j = r + 1; x = a[p];
    while (1)
    {
        while (a[++i] < x && i < r);
        while (a[--j] > x);
        if (i >= j) break;
        swap(&a[i], &a[j]);
    }
    a[p] = a[j]; a[j] = x;
    return j;
}

int Select(int* a, int p, int r, int k)
{
    int s, t;
    int i, j, n, x;
    if (r - p < 75)
    {
        bubbleSort(a, p, r);
        return a[p + k - 1];
    }
    //找中位数的中位数，r-p-4即上面所说的n-5
    for (i = 0; i <= (r - p - 4) / 5; i++) //把每个组的中位数交换到区间[p,p+(r-p-4)/4]
    {
        s = p + 5 * i; t = s + 4;
        for (j = 0; j < 3; j++) //冒泡排序，从后开始排，结果使得后三个数是排好顺序的（递增）
        {
            for (n = s; n < t - j; n++)
            {
                if (a[n] > a[n + 1]) swap(&a[n], &a[n + 1]);
            }
        }
        swap(&a[p + i], &a[s + 2]);//交换每组中的中位数到前面
    }
    //(r-p-4)/5表示组数-1，则[p,p+(r-p-4)/5]的区间长度等于组数
    x = Select(a, p, p + (r - p - 4) / 5, (r - p + 1) / 10);//求中位数的中位数
    /*
    (r-p+1)/10 = (p+(r+p-4)/5-p+1)/2
    */
    i = Partition(a, p, r, x); j = i - p + 1;
    if (k <= j) return Select(a, p, i, k);
    else return Select(a, i + 1, r, k - j);
}
int main(void)
{
    int x, i;
    //数组a存了0-79
    int a[80] = { 3,1,7,6,5,9,8,2,0,4,13,11,17,16,15,19,18,12,10,14,23,21,27,26,25,29,28,22,20,24,33,31,37,36,35,39,38,32,30,34,43,41,47,46,45,49,48,42,40,44,53,51,57,56,55,59,58,52,50,54,63,61,67,66,65,69,68,62,60,64,73,71,77,76,75,79,78,72,70,74,
    };
    scanf("%d", &x);
    printf("The %d smallest number is %d\n", x, Select(a, 0, 79, x));
    return 0;
}

这里有个详细的解答：

算法：线性时间选择_顾道长生'的博客-CSDN博客_线性时间选择算法 定义：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。（1）在某些特殊情况下，很容易设计出解选择问题的线性时间算法。如：当要选择最大元素或最小元素时，显然可以在O(n)时间完成。（一趟比较即可）（2）一般的选择问题，特别是中位数的选择问题似乎比最小（大）元素要难。但实际上，从渐近阶的意义上，它们是一样的。也可以在O(n)时间完成。步骤：（1）将n个输入元... https://blog.csdn.net/wl1780852311/article/details/101000722