比如 2 1 4 3 排成1 2 3 4 最少要2次，如果输入n，输入的n个无序的数，最后输出1 2 3 4 5 。。。，并且次数最少。

那要看你的输入的无序数的具体顺序
比如 一开始就输入1234 那么 那你的说法 就是0次
但是输入4321 就要至少2次

LZ可以参考下各种排序算法的时间复杂度比较
n
方法     1K     10K     100K     200K     100K
                    正序     逆序
冒泡排序     0     0.422     44.790     188.462     0     31.459
冒泡排序2     0     0.281     30.335     131.771     0     27.568
快速排序     0     0     0.016     0.047     5.095     7.002
直接选择排序     0     0.141     16.878     79.332     16.785     33.242
堆排序     0     0     0.031     0.109     0.031     0.015
直接插入排序     0     0.047     8.705     57.800     0     24.865
Shell排序     0     0     0.047     0.110     0.015     0.015
归并排序     0     0     0.031     0.094     0.032     0.032
基数排序     0     0     0.47     0.109     0.047     0.046

只要能实现就行啦，越简单越好，最好解释下

[ 本帖最后由 zhanfffmmm 于 2010-8-26 16:11 编辑 ]

#define MAX 255
int R[MAX];

void Merge(int low,int m,int high)
{/* 将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的 */
/* 子文件R[low..high] */
int i=low,j=m+1,p=0; /* 置初始值 */
int *R1; /* R1是局部向量，若p定义为此类型指针速度更快 */
R1=(int *)malloc((high-low+1)*sizeof(int));
if(!R1) /* 申请空间失败 */
{
puts("Insufficient memory available!");
return;
}
while(i<=m&&j<=high) /* 两子文件非空时取其小者输出到R1[p]上 */
R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];
while(i<=m) /* 若第1个子文件非空，则复制剩余记录到R1中 */
R1[p++]=R[i++];
while(j<=high) /* 若第2个子文件非空，则复制剩余记录到R1中 */
R1[p++]=R[j++];
for(p=0,i=low;i<=high;p++,i++)
R[i]=R1[p];/* 归并完成后将结果复制回R[low..high] */
}

void Merge_SortDC(int low,int high)
{/* 用分治法对R[low..high]进行二路归并排序 */
int mid;
if(low<high)
{/* 区间长度大于1 */
mid=(low+high)/2; /* 分解 */
Merge_SortDC(low,mid); /* 递归地对R[low..mid]排序 */
Merge_SortDC(mid+1,high); /* 递归地对R[mid+1..high]排序 */
Merge(low,mid,high); /* 组合，将两个有序区归并为一个有序区 */
}
}

晕，程序都不能运行

。。。。。。。。。。。。。

要一个简单点的算法？

那就用快速排序吧；当要排序的数据无序时，快速排序的效率比其他的算法都高；当数据有序时，快速排序就和冒泡排序的效率是一样的，以下是代码：
#include<stdio.h>

#define N 5

void QuickSort(int a[],int low,int high)            //快速排序；
{
    int i,j;
    if (low<high)
    {
        i=low;
        j=high;
        a[0]=a[i];
        while (i<j)
        {
            while (i<j&&a[j]>a[0])
                j--;
            a[i]=a[j];
            while (i<j&&a[i]<a[0])
                i++;
            a[j]=a[i];
        }
        a[i]=a[0];
        QuickSort(a,low,i-1);            //递归调用；
        QuickSort(a,i+1,high);
    }
}

int main()
{
    int a[N+1];
    int i;
    for (i=1;i<N+1;i++)
        scanf("%d",&a[i]);
    QuickSort(a,1,N);
    for (i=1;i<N+1;i++)                //a[0]留空，作为哨兵；
        printf("%d\t",a[i]);
    printf("\n");
}