求数组中最小的k个数

 考虑一个数组，或者更一般的一个字数组A[l...r](0≤l≤r≤n-1),该数组由连续的3段组成。这3段按顺序排在中轴p的后面：一段为已知小于p的元素，一段为已知大于或等于p的元素，还有一段未同p比较过的元素。这些段可以为空，在算法开始时，前两段通常是空的。
在i= l+1开始，算法从左到右扫面字数组A[l...r],并保持这个结构直到划分完成。在每一次迭代中，它把未知段中的第一个元素与中轴p进行对比。如果A[i] >= p,则只要i+1就扩大了大于等于p元素的段，而同时缩小了未处理的段。  求数组中最小的k个数(c代码如下)

#include<stdio.h>
#include<stdlib.h>
#define swap(t,x,y) (t = (x),x = (y),y = (t))
int position = 0;
int lomutopartition(int *a,int lo,int hi)
{
    int p =a[lo];
    int i = lo+1,s = lo,temp = 0;
    for (i = lo+1;i < hi;i++)
    {
        if (a[i] < p)
        {
            s = s+1;
            swap(temp,a[i],a[s]);
        }
    }
    swap(temp,a[lo],a[s]);
    return s;
}
int quickselect(int *a,int lo,int hi,int k)
{
    int s = lomutopartition(a,lo,hi);
    if (s == lo+k-1){ position=s; return a[s];}
    else if (s > lo+k-1) quickselect(a,lo,s-1,k);
    else quickselect(a,s+1,hi,lo+k-1-s);

}//这里lo很重要，不写会出现段错误
int main()
{
    int len = 0;
    scanf("%d",&len);


    int a[len];
    int i = 0;
    for (i = 0;i < len;i++)
    {
        printf("请输入第%d个元素",i+1);
        scanf("%d",&a[i]);
    }
    int k = 0;
    printf("请输入k的值");
    scanf("%d",&k);
//    int a[5] = {1,2,3,4,5};
    int result = quickselect(a,0,len-1,k);
    for (i = 0;i < position+1;i++)
    {
        printf("%d\n",a[i]);
    }
//int i = 0;
/*    do{
        printf("a[%d] = %d\n",i,a[i]);
        i++;
    }while(i < position);*/
//    printf("position = %d\n",position);
//    printf("result = %d\n",result);
    return 0;
}

如果A[i] < p,则小于p元素的段需要扩大，这将通过s +1来实现。s是指向第一段中最后一个元素，再交换A[i]与A[s]，然后i+1,使i指向缩小后的未处理段的第一个元素，在未处理元素为空时，算法把中轴与A[s]交换,就得到了一个我们所要求的划分。（快排的另一种划分）
运行如下(centos5.5)
[root@localhost ~]# ./a.out
5
请输入第1个元素3
请输入第2个元素2
请输入第3个元素1
请输入第4个元素4
请输入第5个元素5
请输入k的值3
1
2
3

2)奇数偶数排序：
    给定一个整数数组，请调整数组中暑的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分，要求时间复杂度唯一
划分三部分
奇数部分 偶数部分 未处理部分，与上一题如出一辙
c代码如下：

#include<stdio.h>
#include<stdlib.h>
#define swap(t,x,y) (t = (x),x = (y),y = (t))
/*int evenOrOdd(int i)//判断奇数 偶数
{
    if (i % 2 != 0)
        return 1;
    else
        return 0;
}*/
int evenOrOdd(int i)//这种方式比上一种快许多
{
    if ( (data  & 1) == 1)
        return 1;
    else
        return 0;
}
void sort(int *a,int lo,int hi)
{
    int pivot = a[0];//是奇数还是偶数不重要
    int i = lo+1;
    int s = 0;
    int temp = 0;
    for (i = lo+1;i < hi;i++)
    {
        if (evenOrOdd(a[i]))
        {
            s = s+1;
            swap(temp,a[s],a[i]);
        }
//        printf("%d\n",a[i]);
    }
    swap(temp,a[lo],a[s]);
    // i = 0;
//    printf("%d",a[0]);
}
int main()
{
    int a[] = {1,2,3,4,5};
    sort(a,0,5);
    int i = 0;
    for (i = 0;i < 5;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

[root@localhost ~]# ./a.out
5 3 1 4 2 
[root@localhost ~]#