挑战数组腾挪大法

thinkeryy

我的方法：

#include <stdio.h>;
main()
{
        int l, i ,j,k,tmp;
        int n = 10；
           int objnum = 4;
        int flag = 0;
        int array[10] = {1,4,7,5,4,2,6,4,3,0};
       
        i=0; j=9;
        for(k = 0; k <n;k++)
        {
                if(array[k] == objnum)
                {
                        flag = 1;
                        break;
                }
        }
        if(flag == 0)
        {
                printf("the objnum %d not exist in array!\n",objnum);
                exit(0);
        }
       
                while(j>;i)
        {
//                printf("array:";
//                for(l = 0;l<10;l++)       
//                        printf("% 3d",array[l]);
                for(;array <objnum;i++);
                for(;array[j] >;objnum;j--);
//                printf("  array[%d]=%d",i,array);
//                printf("  array[%d]=%d\n",j,array[j]);
//                getchar();

                if((array == objnum)&&(array[j] ==objnum))
                {
                        for( k=i;k<=j;k++)
                        {       
                                if(array[k] <objnum)
                                {
                                        tmp =array;
                                        array = array[k];
                                        array[k] =tmp;
                                        break;
                                }
                                if(array[k] >;objnum)
                                {
                                        tmp =array[j];
                                        array[j] = array[k];
                                        array[k] =tmp;
                                        break;
                                }
                                if(k == j)
                                        goto end;
                        }
                       
                }
                else
                {
                        tmp=array;
                        array=array[j];
                        array[j] = tmp;
                }
       
        }       
end:
        for(l = 0;l<10;l++)       
                printf("array[%d]=%d\n",l,array[l]);
        printf("objetnum at %d to %d\n",i,j);
}
在sco 5.05 下编译运行。
运行结果：
array[0]=1
array[1]=0
array[2]=3
array[3]=2
array[4]=4
array[5]=4
array[6]=4
array[7]=6
array[8]=5
array[9]=7
objetnum at 4 to 6

说明：
1、先判断数组中是否存在需要查找的数字；
2、从数组头开始寻找>;=目标数字的数字；
3、从数组尾开始寻找<=目标数字的数字；
4、如果这两个数字不等，交换这两个数字的位置；继续查找；
   如果这两个数字相等，则从位于这两个数字之间的数字中找出一个进行交换（如找到的数字小于目标数字，则和前面的目标数字交换，如大于目标数字则和后面的交换，如没有则查找完成）；继续查找。

webskywang

来这里就是想回复这个帖子，如有问题欢迎探讨。

解决方法：
  首先设定数组L[N],长度为N；
  然后设定需要比较的数为X
  我们设定4个参数：a\b\c\d，a、b作为数组L[N]左边开始的指针，c、d作为数组L

[N]右边开始的指针；那么设定a=b=0;c=d=N-1;(c语言中数组下标N-1)
  接着开始进行循环比较
    while(b<c)
    {
      while(L<=X)
      {
      if (L<X) {L[a]=L;a++;}
      b++;
      if (b>;=c) exit(0);
      }
     //
     while(L[c]>;=X)
     {
      if (L[c]>;X) {L[d]=L[c];d--;}
      c--;
      if (b>;=c) exit(0);
      }
     //
     //这时说明L>;X而且L[c]<X
     chage(L,L[c]);//交换L,L[c]中存放的数据，此处还可以部分改进
     }
     for(int i=a+1;i<d;i++;L=X);//从a到d间的数据是X


到这里为止，全部算法完成，最快速解决此问题。

demiurge

#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
void partition(int*, int);
#define swap(x,y) \
        do { \
                int t=x; \
                x = y; \
                y = t; \
        } while (0);
      
int main()
{
        int a[10] = {3,13,41,1,3,4,1,13,1};
        int l=5;
        partition(a, l);
        for (l=0;l<10;l++) printf("%d ", a[l]);

        return 0;
}
void partition(int *a, int x)
{
        int i;
        int n=0;
        int k=0;

        for (i=0;i<10;i++)
                if (a[i]<a[x])
                        n++;


        swap(a[n], a[x]);
        x = n;

        for (i=0; i<10 && k<n;i++) {
                if (i != n)
                        if (a[i] < a[x] ) {
                                if (i!=k) swap(a[k], a[i]);
                                k++;
                        }
        };
      
}

lisp

原帖由 demiurge 于 2006-2-17 18:47 发表
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
void partition(int*, int);
#define swap(x,y) \
        do { \
                int t=x; \
                x = y; \ ...

你强，2002的帖子！

fsilence

这不就是快速排序算法走一遍就行了吗，时间复杂性O(n)，空间复杂性O(1)
想不明白有什么可讨论的

lisp

原帖由 fsilence 于 2006-2-17 20:18 发表
这不就是快速排序算法走一遍就行了吗，时间复杂性O(n)，空间复杂性O(1)
想不明白有什么可讨论的

emacsnw

原帖由 fsilence 于 2006-2-17 04:18 发表
这不就是快速排序算法走一遍就行了吗，时间复杂性O(n)，空间复杂性O(1)
想不明白有什么可讨论的

就是阿~
偶忍了很久没说。。。