|
|
[这个贴子最后由samhoo在 2002/10/28 12:04pm 编辑]
问题：给定一个数组long L[1000],且已知X是其中的一个元素，如何使得小于X的元素位于数组左边，大于X的元素位于数组右边，并得到X在数组中的下标。
要求：1）如何不使用额外的数组；2）时间复杂度不大于O(n)
有没有办法做到呢？
--------------------------修改--------------------------------------------------
题目：给定一个数组long L[n],且已知X是其中的一个元素(等于X的元素可能不止一个)，如何使得小于X的元素位于数组左边，大于X的元素位于数组右边，并得到X在数组中的下标。
要求：1）如何不使用额外的数组；2）时间复杂度不大于O(n)
提示:
A）为了能使讨论能集中于算法本身，而不是无关主旨的细节，下面附上模板程序，只需实现Partition函数即可验证程序是否正确。
B）如果大家能遵守一定的“八股”，我们沟通的效率会高些。(事实上,没有多少人可以有耐心看别人的代码，能看看算法以及测试结果就不错了,下面的“八股”直面这一事实)
八股：
一）算法说明
二）编译运行平台，机器类型/主频
三）Partition函数代码
四）至少给出前4组测试数据的结果
i )L[]={5,5,5,5,5,5,7,1,6,8}; n=10; X=5; （在main函数提供，注释掉其中一些语句即可）
ii )n=10的随机数组
iii)n=10,000,000的随机数组
iv )n=50,000,000的随机数组(小心，别影响别人工作)
v ）其他自己认为具有“边界”特性的数组。
模板程序：
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define DISPLAY \
{ \
int i; \
printf("L[]="); \
for (i = 0; i < num; i++){ \
if (i > 20 ){ \
printf("...(too much number, ignore)"); \
break; \
} \
printf("%d ", L[i]); \
} \
printf("\n"); \
}
int Partition(long *L, int n, long X); /* 实现这个函数 */
long *MakeRandomList(int *num);
long *CreateList(int n);
int Check(long *L, int num, int X, int position);
int SWAP(long *L, int a, int b);
int main()
{
long X;
long *L;
//long L[]={5,5,5,5,5,5,7,1,6,8};
int num = 10;
int pos = 0;
clock_t start_time, end_time;
double duration;
L=MakeRandomList(&num);
X = L[(num - 1) / 2];
printf("X=%ld\n", X);
DISPLAY
printf("-----------------------------------------------------------------\n");
start_time=clock();
pos = Partition(L, num, X);
end_time=clock();
printf("Check :");
if (Check(L, num, X, pos))
printf("incorrect.\n");
else
printf("correct.\n");
duration = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("Time : %.3f seconds.\n", duration);
printf("-----------------------------------------------------------------\n");
printf("position=%ld\n", pos);
DISPLAY
free(L);
return 0;
}
/*
* L：输入数组
* n：数组大小
* X：X元素
* 返回X在数组中的下标
*/
int Partition(long *L, int n, long X)
{
//在这里插入你的代码
}
long *CreateList(int n)
/* Allocates memory for an array of n longs */
{
long *L;
L = (long *) malloc( n * sizeof(long) );
if( L == NULL) { /* Exit program if memory cannot be allocated */
printf("\nCannot allocate enough memory for list.\n");
exit(0);
}
return (L);
}
long *MakeRandomList(int *num)
{
long *L; /* pointer to List */
unsigned int seed; /* seed for random number generator */
int i; /* index of for loop */
printf("\nNumber of elements to sort=>");
scanf("%d",num);
printf("Seed for random number generator (integer)=>");
scanf("%d",&seed);
srand(seed);
/* Allocate memory for # of elements. If memory cannot be allocated,
display message and terminate program. Read in the elements. */
L = CreateList(*num);
if (L == NULL) {
printf("\nCannot allocate enough memory for number list.\n");
exit(0);
}
for (i = 0; i < *num; ++i)
L[i] = rand();
return(L); /* Return the List */
}
int Check(long *L, int num, int X, int position)
{
int i, lpos = -1, rpos = -1;
for (i = 0; i < num; i++)
if (L[i] == X){
lpos = i;
break;
}
else if (L[i] > X)
return -1;
for (i = num - 1; i >= 0; i--)
if (L[i] == X){
rpos = i;
break;
}
else if (L[i] < X)
return -1;
if ((lpos == -1) || (rpos == -1) || (position < lpos) || (position >rpos))
return -1;
for (i = lpos; i <=rpos; i++)
if (L[i] != X)
return -1;
return 0;
}
int SWAP(long *L, int a, int b)
{
long temp;
temp = L[a];
L[a] = L[b];
L[b] = temp;
return 0;
}
| superhoo 回复于：2002-10-23 09:08:44
| 将数组进行排序不就行了吗！
| | samhoo 回复于：2002-10-23 10:55:22
| 题目没有强调效率，而只是空间要求，确实是漏洞。但如果加上条件：时间复杂度为O(n)。
如何？
| | beggar 回复于：2002-10-23 14:36:17
| 想了一天了.想不出什么办法.
binary tree 吧相当于用了空间.时间复杂度也不是O(n)
Shell排序可能可以完成,不过也要在原始数据分步比较合你的意思的时候才有可能达到O(n).
你有什么算法拿来看看.不要卖关子了..
要是没有....................哼哼...哼哼哼......哼哼哼哼.......................................拿弹弓打你们家玻璃.
| | samhoo 回复于：2002-10-23 15:04:23
| 我没有解决这个问题，
也许我把问题的来源说出来更能让各位拓宽思路：这个问题是在我替在米国的朋友捉刀的时候，衍生出来的问题：实现Selection in Worst-Case Linear Time(不知道中文译名)。算法描述见http://www.cs.fsu.edu/~burmeste/slideshow/chapter10/10-3.html
其中说的modified version of Partition算法和我出的题目也一样了。
当时时间紧迫，就用了与原数组一样大的空间，但无也须排序：
int Partition(long *L, int first, int last, long X)
{
long *P;
int i;
int iLeft = 0;
int iRight = last - first;
P = CreateList(last - first + 1);
for (i = first; i <= last; i++){
if (L[i] < X){
comparison_count++;
P[iLeft] = L[i];
iLeft++;
}
else if (L[i] > X){
comparison_count++;
P[iRight] = L[i];
iRight--;
}
}
for (i = iLeft; i <= iRight; i++)
P[i] = X;
for (i = first; i <= last; i++)
L[i] = P[i - first];
free(P);
return iRight + first;
}
| | wwjxjtu 回复于：2002-10-23 19:26:39
| 可以办得到啊！
void specsort(long L[],int pos){
int i,j,tmp1,tmp2=999;
for(i=0;i<1000;i++){
if(L[i]>X){
for(j=tmp2;j<i;j--){
if(L[j]<x){
tmp=L[j];
L[j]=L[i];
L[i]=tmp;
tmp2=j;
break;
}
}
if(j==i) break;
}
else if(L[i]==x) pos=i;
}
}
}
| | wwjxjtu 回复于：2002-10-23 19:28:07
| 有点问题！改后！：
void specsort(long L[],long X,int pos){
int i,j,tmp1,tmp2=999;
for(i=0;i<1000;i++){
if(L[i]>X){
for(j=tmp2;j<i;j--){
if(L[j]<x){
tmp=L[j];
L[j]=L[i];
L[i]=tmp;
tmp2=j;
break;
}
}
if(j==i) break;
}
else if(L[i]==x) pos=i;
}
}
}
| | samhoo 回复于：2002-10-23 20:51:16
| wwjxjtu:
你的思路其实和插入排序无异，时间复杂度为O(n^2)，难以接受。
而且实现也是有问题的：
如： L[]=2 7 9 6 4
最后调整后的L[]=2 7 4 6 9, pos = 1;
不符合要求。
| | beggar 回复于：2002-10-23 23:30:29
| samhoo
我觉得你的算法反正要用空间,还不如用bintree实现来得容易
| | samhoo 回复于：2002-10-24 09:33:42
| 我的想法是：该题目要求的信息其实只是分开大小这样的弱信息，而排序这样的强信息对它来说确实是太浪费。
有解吗？条件是：1)不能分配随n增加而增大的空间；2)算法复杂度不超过O(n)
| | fenglsh 回复于：2002-10-24 10:42:33
| 可以用快速排序法得到
| | fenglsh 回复于：2002-10-24 11:09:10
| //说明，定义另一个变量k，并假设k为数组L的一个元素，即数组L的总共长度为1001，
//而且k为最后一个元素，并假设元素X就放在那(k相当于L[1000])，
//那么就可以使用快速排序法得到:
i=0;
j=1000 -1;
while(X>=L[i])i++;
k=L[i];
while(i<j)
{
while(X<=L[j])j--;
L[i]=L[j];
while(X>=L[i])i++;
L[j]=L[i];
}
| | samhoo 回复于：2002-10-24 14:52:54
| fenglsh,快速排序法的时间复杂度为O(nlogn)，代价太大。
而且排序问题的时间复杂度不可能再比O(nlogn)更优，这是已被证明的命题。
所以我觉得思路不能往这上面靠，我们无需如此强的的信息--排序。
| | 离了水的蛤蟆 回复于：2002-10-25 09:07:28
| #include <stdio.h>
#include <fcntl.h>
#include <sys/errno.h>
extern int errno;
#define MAX_SIZE 10
#define OBJECT_NUMBER 7
#define INT_EXCHANGE(a,b) \
{\
int temp_int; \
temp_int = my_array[a]; \
my_array[a] = my_array[b]; \
my_array[b] = temp_int; \
}
main ()
{
int my_array[MAX_SIZE] = {3,5,7,1,8,4,6,9,2,0};
int last_less_room, last_more_room,
object_current_room;
for (last_less_room = 0, last_more_room = MAX_SIZE -1 ;
last_less_room < last_more_room;)
{
while (my_array[last_less_room] < OBJECT_NUMBER) last_less_room ++;
while (my_array[last_more_room] > OBJECT_NUMBER) last_more_room --;
if (last_less_room == last_more_room)
{
break;
}
if (my_array[last_less_room] == OBJECT_NUMBER)
{
object_current_room = last_less_room;
while (((last_less_room + 1) < (MAX_SIZE - 1))
&& (my_array[last_less_room + 1] < OBJECT_NUMBER))
{
last_less_room ++;
}
INT_EXCHANGE (last_less_room, object_current_room);
if (((last_less_room + 1) < MAX_SIZE)
&& (my_array[last_more_room] < OBJECT_NUMBER))
{
INT_EXCHANGE (last_less_room + 1, last_more_room);
}
}
if (my_array[last_more_room] == OBJECT_NUMBER)
{
object_current_room = last_more_room;
while (((last_more_room - 1) > 0)
&& (my_array[last_more_room - 1] > OBJECT_NUMBER))
{
last_more_room --;
}
INT_EXCHANGE (last_more_room, object_current_room);
if ((last_more_room > 0)
&& (my_array[last_less_room] > OBJECT_NUMBER))
{
INT_EXCHANGE (last_more_room - 1, last_less_room);
}
}
}
{
int i;
for (i=0; i<MAX_SIZE; i++) printf ("%d ", my_array[i]);
printf ("\n");
}
}
| | aegis 回复于：2002-10-25 16:05:23
| 菜鸟啊菜鸟，一群菜鸟！谭笨蛋的书看多了吧？只会照抄，没有一点脑子！
无论干什么，都要先考虑算法！
比 x 小的放在前面，比 x 大的放到后面！算法都告诉你们了，还不会？！
从前面开始，比 x 小，则跳过，比 x 大，和“最后”的那个交换，
反复进行；直到 ok。
int MyCode () // return x position
{
long L [ 1000 ], l;
int s, e;
for ( s = 0, e = 999; s < e;)
{
if ( L [ s ] > X )
{
l = L [ e ];
L [ e -- ] = L [ s ];
L [ s ] = l;
}
else
s ++;
}
return s;
}
上面假定数组里没有其他和 X 相同的数值
简单吧？一群菜鸟
当然还可以有更好的算法，不是菜鸟的自己做吧
| | samhoo 回复于：2002-10-25 17:07:10
| [这个贴子最后由samhoo在 2002/10/25 07:12pm 编辑]
这是aegis的算法得出的结果：
X=5
原始：2 7 3 1 5 6
-----交换过程--------
2 7 3 1 5 6
2 7 3 1 5 6
2 6 3 1 5 7
2 5 3 1 6 7
2 5 3 1 6 7
-----交换过程--------
结果：2 5 3 1 6 7
很遗憾，牛哥您没能达到题目的要求。不仅仅是“假定数组里没有其他和 X 相同的数值
”这个条件没满足。不过还是谢谢你的关注。
| | aegis 回复于：2002-10-25 17:56:42
| x ？
| | samhoo 回复于：2002-10-25 19:12:05
| x=5
| | wwjxjtu 回复于：2002-10-25 19:54:24
| void specsort(long L[],long X,int pos){
int i,j,tmp1,tmp2=999;
for(i=0;i<1000;i++){
if(L[i]>X){
for(j=tmp2;j<i;j--){
if(L[j]<x){
tmp=L[j];
L[j]=L[i];
L[i]=tmp;
tmp2=j;
break;
}
}
if(j==i) break;
}
else if(L[i]==x) pos=i;
}
}
tmp=L[pos];
L[pos]=L[tmp2-1];
L[tmp2-1]=tmp;
pos=tmp2-1;
}
| | samhoo 回复于：2002-10-25 23:36:25
| [这个贴子最后由samhoo在 2002/10/26 12:13pm 编辑]
实在是愚钝，费了牛劲才把它实现出来。
MoveIt是完成交换的核心函数。
Check用于检验结果的正确性。
MakeRandomList生成随机数组
CreateList分配内存。
它们无关主题，图省事直接从别的书抄过来了。
不知道还有没有更明了的算法。
wwjxjtu算法复杂度为O(n^2)，代价太高。
蛤蟆兄不如简单说明一下思路。
#include<stdio.h>
/*
* 问题：给定一个数组long L[n],且已知X是其中的一个元素, 请调整该数组
* 使得所有小于X的元素位于数组左边, 大于X的元素位于数组右边, 并得到X
* 在数组中的下标.
*
* 要求：1)如何不使用额外的数组; 2)时间复杂度不大于O(n)
*
* 算法: left = 0; right = n - 1;
* 1)比较L[left]和X, 如果小于X, left加1, 重复本步骤;
* 如果等于X跳到步骤2; 如果大于X, 跳到步骤3.
* 2)比较L[left]以右的数, 如果小于X,交换之, left加1, 重复本步骤
* 如果等于X, left加1, 重复本步骤; 如果大于X, 跳到步骤3.
* 3)做法与步骤1相似, right向左移动.
* 4)做法与步骤2相似, right向左移动.
* 5)交换L[left], L[right];
*/
#define DISPLAY \
{ \
int i; \
printf("L[]="); \
for (i = 0; i < num; i++) \
printf("%d ", L[i]); \
printf("\n"); \
}
int Check(long *L, int num, int X, int position);
int SWAP(long *L, int a, int b);
long *MakeRandomList(int *num);
long *CreateList(int n);
int MoveIt(long *L, int n, long X)
{
int left = 0, left_ep = 0, right = n -1, right_ep = n - 1;
/* 大数:大于X的数; 小数:小于X的数 */
while(left < right){
/* 找到左边用于交换的大数 */
while( (L[left] <= X) && (left < right) ){
if (L[left] < X){ /* 如果是小数,向右移动 */
left++;
left_ep++;
}
else{
while((L[left] == X) && (left <= right))
left++;
if (left > right)
break;
SWAP(L, left, left_ep);
if (L[left] < X){
left++;
left_ep++;
}
else
left = left_ep;
}
}
/* 找到右边用于交换的小数 */
while( (L[right] >= X) && (left < right) ){
if (L[right] > X){
right--;
right_ep--;
}
else{
while((L[right] == X) && (left <= right))
right--;
if (left > right)
break;
SWAP(L, right, right_ep);
if (L[right] > X){
right--;
right_ep--;
}
else
right = right_ep;
}
}
/* 交换 */
if (left < right){
SWAP(L, left, right);
left++;
left_ep++;
right--;
right_ep--;
}
}
return left_ep;
}
int main()
{
long X;
long *L;
//long L[]={5,5,5,5,5,5,7,1,6,8};
int num = 10;
int pos = 0;
L=MakeRandomList(&num);
X = L[(num - 1) / 2];
printf("X=%ld\n", X);
DISPLAY
printf("--------------------------------------------------------------------\n");
pos = MoveIt(L, num, X);
if (Check(L, num, X, pos))
printf("incorrect.\n");
else
printf("correct.\n");
printf("--------------------------------------------------------------------\n");
printf("position=%ld\n", pos);
DISPLAY
return 0;
}
long *CreateList(int n)
/* Allocates memory for an array of n longs */
{
long *L;
L = (long *) malloc( n * sizeof(long) );
if( L == NULL) { /* Exit program if memory cannot be allocated */
printf("\nCannot allocate enough memory for list.\n");
exit(0);
}
return (L);
}
long *MakeRandomList(int *num)
{
long *L; /* pointer to List */
unsigned int seed; /* seed for random number generator */
int i; /* index of for loop */
printf("\nNumber of elements to sort=>");
scanf("%d",num);
printf("\nSeed for random number generator (integer)=>");
scanf("%d",&seed);
srand(seed);
/* Allocate memory for # of elements. If memory cannot be allocated,
display message and terminate program. Read in the elements. */
L = CreateList(*num);
if (L == NULL) {
printf("\nCannot allocate enough memory for number list.\n");
exit(0);
}
for (i = 0; i < *num; ++i)
L[i] = rand();
return(L); /* Return the List */
}
int Check(long *L, int num, int X, int position)
{
int i, lpos, rpos;
for (i = 0; i < num; i++)
if (L[i] == X)
break;
lpos = i;
for (i = num - 1; i >= 0; i--)
if (L[i] == X)
break;
rpos = i;
for (i = lpos; i <= rpos; i++)
if (L[i] != X)
return -1;
for (i = 0; i < lpos; i++)
if (L[i] > X)
return -1;
for (i = num - 1; i > rpos; i--)
if (L[i] < X)
return -1;
if ( (position < lpos) || (position > rpos) )
return -1;
return 0;
}
int SWAP(long *L, int a, int b)
{
long temp;
temp = L[a];
L[a] = L[b];
L[b] = temp;
return 0;
}
这是几组输出结果：
X=5
L[]=5 5 5 5 5 5 7 1 6 8
--------------------------------------------------------------------
correct.
--------------------------------------------------------------------
position=1
L[]=1 5 5 5 5 5 5 7 6 8
Number of elements to sort=>10
Seed for random number generator (integer)=>1
X=31051
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086
--------------------------------------------------------------------
correct.
--------------------------------------------------------------------
position=9
L[]=16838 5758 10113 17515 5627 23010 7419 16212 4086 31051
欢迎给出反例子（如果有的话）
| | 离了水的蛤蟆 回复于：2002-10-26 02:34:32
| 您的高程调试过吗？
| | aegis 回复于：2002-10-26 10:50:36
| sorry, 少打了一个符号...
int MyCode () // return x position
{
long L [ 1000 ], l;
int s, e;
for ( s = 0, e = 999; s < e;)
{
if ( L [ s ] >= X ) // !!!!!!!! should be >= X
{
l = L [ e ];
L [ e -- ] = L [ s ];
L [ s ] = l;
}
else
s ++;
}
return s;
}
| | aegis 回复于：2002-10-26 10:51:59
| 菜鸟！知道思路了还弄那么复杂，绝对菜鸟！
| | aegis 回复于：2002-10-26 11:03:48
| 对比一下 samboo 和 aegis 的程序……
什么叫 c 语言的简洁美？
所谓菜鸟，就是把简单的事情越搞越复杂
所谓高手，就是把看似复杂的事情弄简单
还有 samboo 你的 swap 实现不是 c 程序员的，是标准的谭笨蛋的 basic
要不要我教教你？
| | samhoo 回复于：2002-10-26 11:44:28
| aegis，拜托你把程序调过了，再来充大佬，行吗？
别以为记住了几个运算符的优先级，就可以跳来跳去，娱乐大众。
你的两个错误结果：
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086
--------------------------------------------------------------------
incorrect.
--------------------------------------------------------------------
position=8
L[]=16838 5758 10113 17515 4086 5627 23010 7419 16212 31051
X=5
L[]=7 9 5 1 5 5 5 8 5 1
--------------------------------------------------------------------
incorrect.
--------------------------------------------------------------------
position=2
L[]=1 1 5 5 5 5 8 5 9 7
| | aegis 回复于：2002-10-26 13:37:55
| 你是一个大笨蛋，没看我说的吗？这个程序适用于 L [1000] 中没有重复的 X;
问题：给定一个数组long L[1000],且已知X是其中的 ！一个！ 元素，如何使得
小于X的元素位于数组左边，大于X的元素位于数组右边，并得到X在数组中的下标。
7 9 5 1 5 5 5 8 5 1 里面有几个 5 ?
你不识数啊？
| | aegis 回复于：2002-10-26 13:46:18
| 你的算法的 时间复杂度是多少？ O(n)? 呸！
| | beggar 回复于：2002-10-26 19:06:50
| [quote][b]下面引用由[u]aegis[/u]在 [i]2002/10/25 04:05pm[/i] 发表的内容：[/b]
菜鸟啊菜鸟，一群菜鸟！谭笨蛋的书看多了吧？只会照抄，没有一点脑子！
无论干什么，都要先考虑算法！
比 x 小的放在前面，比 x 大的放到后面！算法都告诉你们了，还不会？！
从前面开始，比 x 小，则跳过，比 x ...
[/quote]
这位非菜鸟,你好
谭笨蛋?你说的是谭浩强谭老先生吗?谭老先生的书怎么了?你看过吗?你知道谭老先生的书的目的是什么吗?我记得我看的第一本C语言的书就是谭老先生的书.是他让我认识了C,试问这里有几位没有看过谭老先生的书?又有几个不知道谭老先生呢?单这点.老先生让我敬佩.他的书是给初学者认识C接解C而不是要把读者培养成为工程师或程序员.网上许多人说老先生的书看后什么都懂,但就是不会编程.这说明老先生的目的已经达到了.懂而不会编程?我不知道哪个人能把什么东西看会的.我也不知道为什么那么多学校为什么要把老先生的书作为学生学习C的第一本教材.如果说有一本书可以适用于一个程序员的各个阶段,我很想要这本书,你有吗?望借我一看.如果你根本没有看过老先生的书我想你没有资格对老先生的书作任何评价.
话说远了,就以这个贴子来说吧.我很欣慰你还知道有算法.我也很高兴又认识了你这么一位"非菜鸟".更高兴的是你居然也知道你的算法对原始数据有要求,而且是要求X在这么多数中不能重复.
你的程式是以1000个数的数组.1000个数中不能有重复的数?是原始数据要求算法还是算法来决定原始数据.我这个菜鸟不太清楚,忘点明.如果就为了1000个数就要用算法,还要考虑时间空间复杂度? 我不知道你脑子里有没有时间空间的概念. 不知道你的"算法"是否有实用价值.上万,百万个数有没有可能不重复?是否还要求原始数据已经排好序你直接找就行了???
说起来好象很容易啊.菜鸟们随便改改就行了,要解决上面说的问题你觉得随便改改就行吗?
我很想听听"高手"的"高见".你如何解决这个问题.希望你只是随便改改而没有浪费你太多的时间.
| | wwjxjtu 回复于：2002-10-26 19:21:31
| 声明一下，我的算法的复杂度不是O(n^2),而是O(n),如果写成下面这样，将更明显些(不过以前写的是有些问题(int pos应为int *pos)，在网吧上网有些匆忙,现在改一下)：
int specsort(long L[],long X){
int i,j,tmp1,tmp2=999,pos;
for(i=0;i<tmp2;i++){
if(L[i]>X){
for(j=tmp2;j<i;j--){
if(L[j]<x){
tmp=L[j];
L[j]=L[i];
L[i]=tmp;
tmp2=j;
break;
}
}
if(j==i) break;
}
else if(L[i]==x) pos=i;
}
}
tmp=L[pos];
L[pos]=L[tmp2-1];
L[tmp2-1]=tmp;
pos=tmp2-1;
return pos;
}
| | 离了水的蛤蟆 回复于：2002-10-26 22:01:42
| #include <stdio.h>
#include <fcntl.h>
#include <sys/errno.h>
extern int errno;
#define MAX_SIZE 10
#define OBJECT_NUMBER 7
#define INT_EXCHANGE(a,b) \
{\
int temp_int; \
temp_int = my_array[a]; \
my_array[a] = my_array[b]; \
my_array[b] = temp_int; \
}
main ()
{
int my_array[MAX_SIZE] = {3,5,7,1,8,7,6,7,2,0};
int last_less_room, last_more_room,
object_current_room, temp_room;
for (last_less_room = 0, last_more_room = MAX_SIZE -1 ;
last_less_room < last_more_room;)
{
{
int i;
for (i=0; i<MAX_SIZE; i++) printf ("%d ", my_array[i]);
printf ("\n");
}
while (my_array[last_less_room] < OBJECT_NUMBER) last_less_room ++;
while (my_array[last_more_room] > OBJECT_NUMBER) last_more_room --;
if (last_less_room >= last_more_room)
{
break;
}
if (my_array[last_less_room] == my_array[last_more_room])
{
for (temp_room = last_less_room+1;
(temp_room<(last_more_room-1))
&& (my_array[temp_room] == OBJECT_NUMBER); temp_room++);
if (my_array[temp_room] == OBJECT_NUMBER)
{
break;
}
else if (my_array[temp_room] > OBJECT_NUMBER)
{
INT_EXCHANGE (temp_room, last_more_room);
}
else if (my_array[temp_room] < OBJECT_NUMBER)
{
INT_EXCHANGE (temp_room, last_less_room);
}
continue;
}
if (my_array[last_less_room] == OBJECT_NUMBER)
{
object_current_room = last_less_room;
while (((last_less_room + 1) < (MAX_SIZE - 1))
&& (my_array[last_less_room + 1] < OBJECT_NUMBER))
{
last_less_room ++;
}
INT_EXCHANGE (last_less_room, object_current_room);
if (((last_less_room + 1) < MAX_SIZE)
&& (my_array[last_more_room] < OBJECT_NUMBER))
{
INT_EXCHANGE (last_less_room + 1, last_more_room);
}
}
if (my_array[last_more_room] == OBJECT_NUMBER)
{
object_current_room = last_more_room;
while (((last_more_room - 1) > 0)
&& (my_array[last_more_room - 1] > OBJECT_NUMBER))
{
last_more_room --;
}
INT_EXCHANGE (last_more_room, object_current_room);
if ((last_more_room > 0)
&& (my_array[last_less_room] > OBJECT_NUMBER))
{
INT_EXCHANGE (last_more_room - 1, last_less_room);
}
}
}
{
int i;
for (i=0; i<MAX_SIZE; i++) printf ("%d ", my_array[i]);
printf ("\n");
}
}
输出的结果是：
3 5 7 1 8 7 6 7 2 0
3 5 1 7 0 7 6 7 2 8
3 5 1 0 7 2 6 7 7 8
3 5 1 0 2 7 6 7 7 8
3 5 1 0 2 6 7 7 7 8
3 5 1 0 2 6 7 7 7 8
| | 离了水的蛤蟆 回复于：2002-10-26 22:11:57
| 我的算法是从两头向中间找不属于那个位置的数据，从左边开始找到的是大于目标数据（X）的位置，从右边开始找到的是小于X的位置，把他们互换。
如果遇到等于X的数，找出其后最后一个顺序适合的数，将他们进行互换。
这样向中间逼近，就能吧X放到合适的位置上。
早上贴的程序不能处理数组中有多个等于X的数的情况，所以我又进行了改进。
（if (my_array[last_less_room] == my_array[last_more_room]) ......这一段）
如果两头都停止在等于X的数的位置，那么从它们之间找到一个不等于X的数,
与两端的数进行互换，这样循环就能够继续下去，直至last_less_room和last_more_room之间全部都是X。
| | aegis 回复于：2002-10-27 11:15:07
| 首先，先要说明一下，本贴的前几个 aegis 回复不是我写的
是谁写的呢？就是看谭浩强的书学 c， 不得其法的那个朋友，
他和我在一个单位工作，知道我的账号；当然了，把谭浩强封为笨蛋，
也是从我这里学的。现在他的 c/c++ 写得很不错了，自然对谭好强
没什么好印象。请不要误会，这里没有推卸责任的意思，他的措辞虽然
太激烈了一点，但观点我还是赞同的。
先回答第一个问题：谭好强的编程书我看过 basic, fortran, c 这三本看得都
非常仔细，其它的也草草看过。对 basic 那本, 好像是和田淑清合作的吧，
印象还可以，fortran 一般，c 那一本纯粹是误人子弟。为什么这么说呢？
我当然知道这些都是针对初学者的书。我们知道，每种语言，都只不过是对
算法的表述。如何表述特定算法，表现了语言创造者对计算机系统核算法语义
的基本看法和理解，以及他们的个性和编程习惯。我们面向的环境不同，任务不同，
当然，个人的理解也不同，所以 basic, c, pascal, sql, smalltalk ...
各种语言都有其存在价值和适用范围，也各有其特点。我的观点，谭的书
对各种语言的理解没有表现出来，看得越多，越发现作者本人恐怕是不太
了解这些语言的。当然也就写得千篇一律，全都 basic 了。初学者如果学习
basic, fortran 我会让他去看谭的书，因为这两本书的思想是 basic 和
fortran 的。
当然，看他的书学习 c 是不行的。为什么呢？如果从 basic 程序员的角度，
使用 c 语法，写出来的东西会怎么样呢？当然，c 编译是能通过的，程序是
可以使用的。但这样的程序，能称为 c 程序吗？所以说，c 初学者学习他的书,
坏处很大。学得慢、学得累倒也罢了，学歪了再想纠正是很困难的。tom
swan 的 c 还是不错的，c++ 也还行。当然，学习 c 最好还是清高手讲，蛤蟆
老兄给你讲三天，什么书都可以扔了。另外一点，就是要多读别人的程序，
不要怕累，多比较同一问题不同 programer 的实现，进步是很快的。
关于谭嘛，他自己理解还不够，就写了那么多 《* 语言编程》，至少有点
不负责任吧？如果我是他，宁愿被人骂是笨蛋，这样不过是年纪大了，理解
不到了，水平不够了。否则，不成了为了赚钱出垃圾产品，成品德问题了。
| | aegis 回复于：2002-10-27 13:55:09
| 第二，对于这个问题的解法
对于 L 中只有一个 x 的情况，他贴出的程序（修改过 >= 的）是一个比较简洁的算法。
也符合时间复杂度的要求，即使是在最不利情况下。他跟我说题目中要求指出 x 位置，
所以认为 x 只有一个
对于 L 中有多个 x 的情况，有两种比较简单，比较容易理解的方法
第一个，是从他的思路出发进行修改，程序长了一点，但效率比较高
第二个，其实很简单，不要把思路限制在 one pass 的范围内就知道了
效率虽然低一些，但容易理解：
0) 先数出比 x 小的数和比 x 大的数的个数
当然也就知道 x 的个数了，也就知道 小数、x、大数 的位置范围了，
for ( sm = gm = l = 0; l < 1000; l ++ )
{
if ( X > L [ l ] ) sm ++;
if ( X < L [ l ] ) gm ++;
}
em = 1000 - sm - gm;
以后的事情就简单了
1) 从 0 开始遍历到 sm - 1; 发现 >= X 的就和 sm 后面的小数交换
for ( i = sm, s_s = 0; s_s < sm; s_s ++ )
if ( X <= L [ s_s ] )
{
while ( X <= L [ i ] ) i ++;
l = L [ i ]; L [ i ] = L [ s_s ]; L [ s_s ] = l;
}
2) 从 sm 开始遍历 em 个; 发现 != X 的就和 sm + em 后面的 X 交换
for ( i = sm + em, e_s = sm; e_s < sm + em; e_s ++ )
if ( X != L [ e_s ] )
{
while ( X != L [ i ] ) i ++;
L [ i ] = L [ e_s ]; L [ e_s ] = X;
}
0), 1), 2) 时间复杂度都 O(n)
以上步骤是一个算法说明，没有经过编译验证 (目前手头没有 c compiler)
对于 假 aegis 算法的改进，让他自己写吧 (他有 compiler)
| | aegis 回复于：2002-10-27 14:28:24
| 对于 beggar 的意见：
第一，真正具有开设计算机系能力的大学，其计算机系一般不讲授 c 语言，
是由学生自学的；其计算机系作为公共课程讲授的计算机语言，使用谭的书
作教材的也不多。请不要凭想象猜测。
第二，从来没人说有一本书可以适用于一个程序员的各个阶段。但一般来说，
作为程序员，学习一门语言只需要一本书就够了，了解其思路、特性和语法特点，
其它可以查手册和联机文档。
就以这个贴子来说吧：不能否认，题目本身措辞并不是很严格，我的朋友
将其理解为数组中没有 X 重复值也可理解：
1）题目中要求给出 x 下标；
2）他的程序目的是提供一个思路，而不是严格的实现
当然，题目要求决定算法。有重复 x 的算法我想并不难，即使对于初学者，
自己动脑子想想也能解决
对于算法，我不想多说，在我们概念里，不仅“快速傅氏变换”是算法，
for (i=0;i<10;i++) L[i]=0; 这也是一个算法。
当然要考虑空间复杂度和时间复杂度，因为这是题目里明确提出了要求的。
另外，如果要求时间复杂度 O(n)，不仅交换的次数要 O(n)，比较的次数
也要 O(n)，并且在最不利的情况下也保证 O(n)，这样才算符合题目要求。
beggar 老兄，说了这么多，其实对你我都没什么用处。我们还是可以坚持
自己的看法。也许，多针对具体问题讨论讨论更加实际，我很想听听你对
这个题目的看法
| | aegis 回复于：2002-10-27 14:53:04
| 下面是 假aegis 的算法：
#deinfe LL 1000
const int x = X;
long L [ LL ];
int s, e, s0, e0, l;
for ( s = 0, e = LL - 1; s < e; )
{
while ( x > L [ s ] ) s ++; // 左面跳过小数
while ( x < L [ e ] ) e ++; // 右面跳过大数
if ( s >= e ) break;
if ( x < L [ s ] ) // 大数交换到最右面
{ l = L [ e ]; L [ e -- ] = L [ s ]; L [ s ] = l; }
else if ( x > L [ e ] ) // 小数交换到最左面
{ l = L [ e ]; L [ e ] = L [ s ]; L [ s ++ ] = l; }
else // 左、右端都是 x, 中间可能有小数或大数
{ // 进行交换将两端的 x 移至中间
for ( s0 = s, e0 = e; s0 < e0 )
{ // s0, e0 为非 x 数位置范围
while ( x == L [ s0 ] ) s0 ++;
while ( x == L [ e0 ] ) e0 --;
if ( s0 > e0 ) break;
if ( x > L [ s0 ] ) // 发现小数
{ // 交换至左端
L [ s ++ ] = L [ s0 ];
L [ s0 ++ ] = x;
}
else // 发现大数
{ // 当前位置 右端数字(e位置) e0位置，三个数字向右轮换
L [ e -- ] = L [ s0 ];
L [ s0 ] = L [ e0 ];
L [ e0 -- ] = x;
}
}
break; // 这样交换完就满足要求了
}
}
// s, e 分别指向 x 的起始和终止位置
以上程序手工录入，可能有错，欢迎指正
| | beggar 回复于：2002-10-27 19:52:01
| [这个贴子最后由beggar在 2002/10/28 10:07am 编辑]
怎么那时我们学校开设的课程第一学期就有<C程序设计>?
我不知道你那个"朋友"就是你本人,一人作事一人当.老套了.不过这样的人太多了.我想如果没有这些垃圾存在的话.现在中国的软件产业一定会非常发达.
再次声明.谭老先生的书面向没有一点儿基础的学习者,如果你目前还在看他的书我在想我有没有必要来和你计论这个数组问题.听道说没有一本书可以便随一个程序员的各个阶段.我还以为有一本书可以让人看了之后再也不用看其它书了.谢谢又让我明白一件事.
引用你的原文"...明一下，本贴的前几个 aegis 回复不是我写的.是谁写的呢？就是看谭浩强的书学 c， 不得其法的那个朋友.."
引用你所说的假aegis的原文"菜鸟啊菜鸟，一群菜鸟！谭笨蛋的书看多了吧？只会照抄，没有一点脑子"
你认为有这种白痴吗?自相茅盾.
再次,对原始数据的要求把责任归于命题不严??我不知道你有没有脑子.引用原文" ...元素，如何使得小于X的元素位于数组左边，大于X的元素位于数组右边，并得...",我想人家已经说得很清楚了.要说到分厘不差.有专门的行业----律师去作这些事情.
呵呵.你说的理论好复杂啊.我听不懂哦.看起来是个高手哦.
不过我可以告诉你或你朋友.你的程序是垃圾.写程式或你说的"算法"应该避免的问题你全用上了.不知道是否真的写过程序.还不知道能不能编译.
再次.请不要说用你这种"算法"来处理数据重复问题很容易.让菜鸟"随便"改,我希望你能把你的"算法"完整实现拿来学习一下.在此先表示感谢
| | beggar 回复于：2002-10-27 19:52:40
| [这个贴子最后由beggar在 2002/10/28 01:09pm 编辑]
#include <sys/types.h>
#include <stdio.h>
#define DATA_LEN 10
main()
{
int total_mov_time=0; //this value used for count the exchange times by program.
int loop,loopstart,looplen,tmp,found_loc;
int big_count,equ_count,big_loc,equ_loc,test_num;//the location of ori data.
int ori_data[DATA_LEN]={16838,5758,10113,17515,31051,5627,23010,7419,16212,4086};
looplen=DATA_LEN; //e.g: here is 10.
test_num=31051; //try to find 31051
printf("===ori data===\n");
for(loop=0;loop<looplen;loop++)
printf("%d ",ori_data[loop]);
printf("\n");
loopstart=big_count=equ_count=big_loc=0;
for(loop=loopstart;loop<looplen;loop++){
if(test_num>ori_data[loop]){
if(big_count!=0){
//exchange small to big locate.
tmp=ori_data[big_loc];
ori_data[big_loc]=ori_data[loop];
ori_data[loop]=tmp;
total_mov_time++;
}
big_loc++;
continue;
}
if(test_num<ori_data[loop]){
big_count++;
continue;
}
if(test_num==ori_data[loop]){
tmp=ori_data[loop];
ori_data[loop]=ori_data[looplen-1];
ori_data[looplen-1]=tmp;
equ_count++;
looplen--;
loop--;
total_mov_time++;
}
}
if(equ_count==0){
printf("ERROR:test number not found.\n");
exit(1);
}else{
found_loc=big_loc+1;
equ_loc=DATA_LEN-equ_count;
if(equ_count<big_count){
looplen=DATA_LEN;
tmp=equ_loc;
loopstart=big_loc;
}else{
looplen=big_loc+big_count;
tmp=big_loc;
loopstart=DATA_LEN-big_count;
}
for(loop=tmp;loop<looplen;loop++){
tmp=ori_data[loop];
ori_data[loop]=ori_data[loopstart];
ori_data[loopstart]=tmp;
loopstart++;
total_mov_time++;
}
}
printf("\n===Total===\n");
printf("find data:%d location:%d foundtimes:%d total exchage:%d\nok\n",
test_num,found_loc,equ_count,total_mov_time);
printf("\n===Last array===\n");
for(loop=0;loop<DATA_LEN;loop++)
printf("%d ",ori_data[loop]);
printf("\n");
exit(0);
}
| | beggar 回复于：2002-10-27 19:54:43
| [这个贴子最后由beggar在 2002/10/28 00:56am 编辑]
看得懂吗?不要说看不懂.
程序先把原始数据分成三部分,用下标将这三部分分开.
[ 比X小的 ] [ 比X大的 ] [ X ]
再将第三部分移到第二部分之前,完成处理.
[ 比X小的 ] [ X ] [ 比X大的 ]
这样作在处理数据较多时可以减少数据比较和移动的次数.
你可以把你那个"算法"和我的作1000个数time测试.
以上程式在FB上cc编译通过.
我希望你不要只是说叫菜鸟随便改改.贴出你的源程序来time test试试,让我们看看"高手"的算法实现啊
| | samhoo 回复于：2002-10-28 11:51:11
| 感谢各位的关注!
1）关于这个帖子的一些意气之争，这不是本贴、也不是本坛所感兴趣的范围，有兴趣的网友看前面的帖子即可，这里不再做评论。
2）为了大家有一个集中主题、高效的交流平台，下面的以及随后的帖子将试图重新给出一个良好的讨论前提，并总结前面各位的发言。
3）欢迎任何有对题目表述，解答模板有建设性的批评与建议。
题目：给定一个数组long L[n],且已知X是其中的一个元素(等于X的元素可能不止一个)，如何使得小于X的元素位于数组左边，大于X的元素位于数组右边，并得到X在数组中的下标。
要求：1）如何不使用额外的数组；2）时间复杂度不大于O(n)
提示:
A）为了能使讨论能集中于算法本身，而不是无关主旨的细节，下面附上模板程序，只需实现Partition函数即可验证程序是否正确。
B）如果大家能遵守一定的“八股”，我们沟通的效率会高些。(事实上,没有多少人可以有耐心看别人的代码，能看看算法以及测试结果就不错了,下面的“八股”直面这一事实)
八股：
一）算法说明
二）编译运行平台，机器类型/主频
三）Partition函数代码
四）至少给出前4组测试数据的结果
i )L[]={5,5,5,5,5,5,7,1,6,8}; n=10; X=5; （在main函数提供，注释掉其中一些语句即可）
ii )n=10的随机数组
iii)n=10,000,000的随机数组
iv )n=50,000,000的随机数组(小心，别影响别人工作)
v ）其他自己认为具有“边界”特性的数组。
模板程序：
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define DISPLAY \
{ \
int i; \
printf("L[]="); \
for (i = 0; i < num; i++){ \
if (i > 20 ){ \
printf("...(too much number, ignore)"); \
break; \
} \
printf("%d ", L[i]); \
} \
printf("\n"); \
}
int Partition(long *L, int n, long X); /* 实现这个函数 */
long *MakeRandomList(int *num);
long *CreateList(int n);
int Check(long *L, int num, int X, int position);
int SWAP(long *L, int a, int b);
int main()
{
long X;
long *L;
//long L[]={5,5,5,5,5,5,7,1,6,8};
int num = 10;
int pos = 0;
clock_t start_time, end_time;
double duration;
L=MakeRandomList(&num);
X = L[(num - 1) / 2];
printf("X=%ld\n", X);
DISPLAY
printf("-----------------------------------------------------------------\n");
start_time=clock();
pos = Partition(L, num, X);
end_time=clock();
printf("Check :");
if (Check(L, num, X, pos))
printf("incorrect.\n");
else
printf("correct.\n");
duration = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("Time : %.3f seconds.\n", duration);
printf("-----------------------------------------------------------------\n");
printf("position=%ld\n", pos);
DISPLAY
free(L);
return 0;
}
/*
* L：输入数组
* n：数组大小
* X：X元素
* 返回X在数组中的下标
*/
int Partition(long *L, int n, long X)
{
//在这里插入你的代码
}
long *CreateList(int n)
/* Allocates memory for an array of n longs */
{
long *L;
L = (long *) malloc( n * sizeof(long) );
if( L == NULL) { /* Exit program if memory cannot be allocated */
printf("\nCannot allocate enough memory for list.\n");
exit(0);
}
return (L);
}
long *MakeRandomList(int *num)
{
long *L; /* pointer to List */
unsigned int seed; /* seed for random number generator */
int i; /* index of for loop */
printf("\nNumber of elements to sort=>");
scanf("%d",num);
printf("Seed for random number generator (integer)=>");
scanf("%d",&seed);
srand(seed);
/* Allocate memory for # of elements. If memory cannot be allocated,
display message and terminate program. Read in the elements. */
L = CreateList(*num);
if (L == NULL) {
printf("\nCannot allocate enough memory for number list.\n");
exit(0);
}
for (i = 0; i < *num; ++i)
L[i] = rand();
return(L); /* Return the List */
}
int Check(long *L, int num, int X, int position)
{
int i, lpos = -1, rpos = -1;
for (i = 0; i < num; i++)
if (L[i] == X){
lpos = i;
break;
}
else if (L[i] > X)
return -1;
for (i = num - 1; i >= 0; i--)
if (L[i] == X){
rpos = i;
break;
}
else if (L[i] < X)
return -1;
if ((lpos == -1) || (rpos == -1) || (position < lpos) || (position >rpos))
return -1;
for (i = lpos; i <=rpos; i++)
if (L[i] != X)
return -1;
return 0;
}
int SWAP(long *L, int a, int b)
{
long temp;
temp = L[a];
L[a] = L[b];
L[b] = temp;
return 0;
}
| | Chinajiji 回复于：2002-10-28 11:51:54
| 原题是:问题：给定一个数组long L[1000],且已知X是其中的一个元素，如何使得小于X的元素位于数组左边，大于X的元素位于数组右边，并得到X在数组中的下标。
要求：1）如何不使用额外的数组；2）时间复杂度不大于O(n)
注意:1)原题中没有要求数组每个元素必须唯一,因此数组中可能存在重复的元素.
2)原题中没有交待如何处理与X相等的情况,因此等于X的元素可以全放在它的前面,也可以全放在它的后面,如果将全部的X放在一起当然更好,但强化了原条件,如同原题并没有要求排序一样,如果得出的结果是排了序的,就强化了原条件,等于多做了无用功.
3)从属于2)可以看出,原题条件太不正规.
我是菜鸟叽叽,下面是我给出的程序,在VC6.0下通过,将大于等于X的元素都放在X的后面.欢迎大家叫我菜鸟.
#include <iostream>
using namespace std;
const int ARRAY_SIZE=10;
inline void doSwap(int *v,int i,int j){
int temp=v[i];
v[i]=v[j];
v[j]=temp;
}
inline int findFirstPosition(int *v,int size,const int value){
int i=0;
for(i=0;i<size;i++)
if (v[i]==value)
return i;
if(i==size)
cout<<"Error! The vaule:"<<value<<" does NOT in the array!"<<endl;
exit(1);
}
inline int sortArray(int *v,int size,const int value){
if(size<1){
cout<<"Error! array size:"<<size<<" must >0!"<<endl;
exit(2);
}
int firstPosition=findFirstPosition(v,size,value);
if(size<2)
return firstPosition;
int last=0;
int i=0;
doSwap(v,0,firstPosition);
for(i=0;i<size;i++)
if(v[i]<value)
doSwap(v,i,++last);
doSwap(v,0,last);
return last;
}
main(){
int testArray[ARRAY_SIZE]={56,6,56,678,45,546,88,56,345,577};
int const compareValue=56;
int foundPosition=sortArray(testArray,ARRAY_SIZE,compareValue);
int i=0;
cout<<"Now,output the array!"<<endl;
for(i=0;i<ARRAY_SIZE;i++)
cout<<testArray[i]<<",";
cout<<"\nThe position of compareValue:"<<compareValue<<" is "<<foundPosition<<endl;
return 0;
}
/*
Now,output the array!
45,6,56,678,56,546,88,56,345,577,
The position of compareValue:56 is 2
*/
算法简述:
1)首先找到X在数组中的位置:firstPosition=findFirstPosition(v,size,value);
2)将X与数组首元素交换:doSwap(v,0,firstPosition);
3)
for(i=0;i<size;i++)
if(v[i]<value)
doSwap(v,i,++last);
小于X(即:value)的元素:doSwap(v,i,++last);
大于等于X的元素只作:i++;
last初值为0,表示所有小于X且已经调整过位置的元素中的最后面的一个.
4)最后做一次交换: doSwap(v,0,last);将首元素v[0]=X与v[last]交换.
5)函数返回last,就是X的位置.
| | samhoo 回复于：2002-10-28 11:53:04
| 下面几个贴子将整理参与该题目，且已给出的可编译执行代码的解答。
可以编译执行的有：samhoo, 离了水的蛤蟆, beggar
wwjxjtu和(fake)aegis的代码无法编译通过，暂无法整理
| | samhoo 回复于：2002-10-28 11:53:53
| samhoo的解答。
一)算法说明
left = 0; right = n - 1;
1)比较L[left]和X, 如果小于X, left加1, 重复本步骤; 如果等于X跳到步骤2; 如果大于X, 跳到步骤3.
2)比较L[left]以右的数, 如果小于X,交换之, left加1, 重复本步骤; 如果等于X, left加1, 重复本步骤; 如果大于X, 跳到步骤3.
3)做法与步骤1相似, right向左移动.
4)做法与步骤2相似, right向左移动.
5)交换L[left], L[right];跳到步骤1）
上述步骤都会对边界进行检查。
二）编译器/运行平台，机器类型
cc/sco OpenServer 5.05, intel 1.2GMhz
三）Partition函数代码
/*
* L：输入数组
* n：数组大小
* X：X元素
* 返回X在数组中的下标
*/
int Partition(long *L, int n, long X)
{
int left = 0, left_ep = 0, right = n -1, right_ep = n - 1;
/* 大数:大于X的数; 小数:小于X的数 */
while(left < right){
/* 找到左边用于交换的大数 */
while( (L[left] <= X) && (left < right) ){
if (L[left] < X){ /* 如果是小数,向右移动 */
left++;
left_ep++;
}
else{
while((L[left] == X) && (left <= right)) left++;
if (left > right)
break;
SWAP(L, left, left_ep);
if (L[left] < X){
left++;
left_ep++;
}
else
left = left_ep;
}
}
/* 找到右边用于交换的小数 */
while( (L[right] >= X) && (left < right) ){
if (L[right] > X){ /* 如果是大数,向左移动 */
right--;
right_ep--;
}
else{
while((L[right] == X) && (left <= right)) right--;
if (left > right) break;
SWAP(L, right, right_ep);
if (L[right] > X){
right--;
right_ep--;
}
else
right = right_ep;
}
}
/* 交换 */
if (left < right){
SWAP(L, left, right);
left++;
left_ep++;
right--;
right_ep--;
}
}
return left_ep;
}
long *CreateList(int n)
/* Allocates memory for an array of n longs */
{
long *L;
L = (long *) malloc( n * sizeof(long) );
if( L == NULL) { /* Exit program if memory cannot be allocated */
printf("\nCannot allocate enough memory for list.\n");
exit(0);
}
return (L);
}
long *MakeRandomList(int *num)
{
long *L; /* pointer to List */
unsigned int seed; /* seed for random number generator */
int i; /* index of for loop */
printf("\nNumber of elements to sort=>");
scanf("%d",num);
printf("Seed for random number generator (integer)=>");
scanf("%d",&seed);
srand(seed);
/* Allocate memory for # of elements. If memory cannot be allocated,
display message and terminate program. Read in the elements. */
L = CreateList(*num);
if (L == NULL) {
printf("\nCannot allocate enough memory for number list.\n");
exit(0);
}
for (i = 0; i < *num; ++i)
L[i] = rand();
return(L); /* Return the List */
}
int Check(long *L, int num, int X, int position)
{
int i, lpos = -1, rpos = -1;
for (i = 0; i < num; i++)
if (L[i] == X){
lpos = i;
break;
}
else if (L[i] > X)
return -1;
for (i = num - 1; i >= 0; i--)
if (L[i] == X){
rpos = i;
break;
}
else if (L[i] < X)
return -1;
if ((lpos == -1) || (rpos == -1) || (position < lpos) || (position >rpos))
return -1;
for (i = lpos; i <=rpos; i++)
if (L[i] != X)
return -1;
return 0;
}
int SWAP(long *L, int a, int b)
{
long temp;
temp = L[a];
L[a] = L[b];
L[b] = temp;
return 0;
}
四）至少给出前4组测试数据的结果
i )L[]={5,5,5,5,5,5,7,1,6,8}; n=10; X=5; （在main函数提供，注释掉其中一些语句即可）
X=5
L[]=5 5 5 5 5 5 7 1 6 8
-----------------------------------------------------------------
Check :correct.
Time : 0.000 seconds.
-----------------------------------------------------------------
position=1
L[]=1 5 5 5 5 5 5 7 6 8
ii )n=10的随机数组
Number of elements to sort=>10
Seed for random number generator (integer)=>1
X=31051
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086
-----------------------------------------------------------------
Check :correct.
Time : 0.000 seconds.
-----------------------------------------------------------------
position=9
L[]=16838 5758 10113 17515 5627 23010 7419 16212 4086 31051
iii)n=10,000,000的随机数组
Number of elements to sort=>10000000
Seed for random number generator (integer)=>1
X=5500
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086 2749 12767 9084 1206
0 32225 17543 25089 21183 25137 25566 26966 ...(too much number, ignore)
-----------------------------------------------------------------
Check :correct.
Time : 2.440 seconds.
-----------------------------------------------------------------
position=1678846
L[]=2266 2127 2110 1762 626 1023 4566 2197 572 4086 2749 4060 1120 2206 2836 293
5 3375 3800 3392 4703 2069 ...(too much number, ignore)
iv )n=50,000,000随机数组
Number of elements to sort=>50000000
Seed for random number generator (integer)=>1
X=16413
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086 2749 12767 9084 1206
0 32225 17543 25089 21183 25137 25566 26966 ...(too much number, ignore)
-----------------------------------------------------------------
Check :correct.
Time : 38.350 seconds.
-----------------------------------------------------------------
position=25052130
L[]=3827 5758 10113 7067 1970 5627 10035 7419 16212 4086 2749 12767 9084 12060 6
42 4478 5374 2400 10405 7411 10487 ...(too much number, ignore)
v ）其他自己认为具有“边界”特性的数组。
none
| | samhoo 回复于：2002-10-28 11:54:26
| 经整理的“离开水的蛤蟆”的解答，仍有部分数组未能应付。
（如果有理解错误的地方，请指正）
一）算法说明
两头向中间找不属于那个位置的数据，从左边开始找到的是大于目标数据（X）的位置，从右边开始找到的是小于X的位置，把他们互换。
如果遇到等于X的数，找出其后最后一个顺序适合的数，将他们进行互换。
这样向中间逼近，就能吧X放到合适的位置上。
二）编译运行平台，机器类型/主频
cc/sco OpenServer 5.05, intel 1.2GMhz
三）Partition函数代码
/*
* L：输入数组
* n：数组大小
* X：X元素
* 返回X在数组中的下标
*/
int Partition(long *L, int n, long X)
{
int MAX_SIZE = n;
long OBJECT_NUMBER = X;
long *my_array = L;
int last_less_room, last_more_room,
object_current_room, temp_room;
for (last_less_room = 0, last_more_room = MAX_SIZE -1 ;
last_less_room < last_more_room;)
{
while (my_array[last_less_room] < OBJECT_NUMBER) last_less_room ++;
while (my_array[last_more_room] > OBJECT_NUMBER) last_more_room --;
if (last_less_room >= last_more_room)
{
break;
}
if (my_array[last_less_room] == my_array[last_more_room])
{
for (temp_room = last_less_room+1;
(temp_room<(last_more_room-1))
&& (my_array[temp_room] == OBJECT_NUMBER); temp_room++);
if (my_array[temp_room] == OBJECT_NUMBER)
{
break;
}
else if (my_array[temp_room] > OBJECT_NUMBER)
{
//INT_EXCHANGE (temp_room, last_less_room);
SWAP (L, temp_room, last_more_room);
}
else if (my_array[temp_room] < OBJECT_NUMBER)
{
//INT_EXCHANGE (temp_room, last_less_room);
SWAP (L, temp_room, last_less_room);
}
continue;
}
if (my_array[last_less_room] == OBJECT_NUMBER)
{
object_current_room = last_less_room;
while (((last_less_room + 1) < (MAX_SIZE - 1))
&& (my_array[last_less_room + 1] < OBJECT_NUMBER))
{
last_less_room ++;
}
//INT_EXCHANGE (temp_room, last_less_room);
SWAP (L, last_less_room, object_current_room);
if (((last_less_room + 1) < MAX_SIZE)
&& (my_array[last_more_room] < OBJECT_NUMBER))
{
//INT_EXCHANGE (temp_room, last_less_room);
SWAP (L, last_less_room + 1, last_more_room);
}
}
if (my_array[last_more_room] == OBJECT_NUMBER)
{
object_current_room = last_more_room;
while (((last_more_room - 1) > 0)
&& (my_array[last_more_room - 1] > OBJECT_NUMBER))
{
last_more_room --;
}
//INT_EXCHANGE (temp_room, last_less_room);
SWAP (L, last_more_room, object_current_room);
if ((last_more_room > 0)
&& (my_array[last_less_room] > OBJECT_NUMBER))
{
//INT_EXCHANGE (temp_room, last_less_room);
SWAP (L, last_more_room - 1, last_less_room);
}
}
}
}
四）至少给出前4组测试数据的结果
i )L[]={5,5,5,5,5,5,7,1,6,8}; n=10; X=5; （在main函数提供，注释掉其中一些语句即可）
X=5
L[]=5 5 5 5 5 5 7 1 6 8
-----------------------------------------------------------------
Check :correct.
Time : 0.000 seconds.
-----------------------------------------------------------------
position=5
L[]=1 5 5 5 5 5 5 7 6 8
ii )n=10的随机数组
Number of elements to sort=>10
Seed for random number generator (integer)=>1
X=31051
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086
-----------------------------------------------------------------
等了许久，未见结果，相信有些边界条件判断失败，而陷入循环
iii)n=10,000,000的随机数组
＜未测试＞
iv )n=50,000,000的随机数组(小心，别影响别人工作)
＜未测试＞
v ）其他自己认为具有“边界”特性的数组。
X=7
L[]=3 5 7 1 8 7 6 7 2 0
-----------------------------------------------------------------
Check :correct.
Time : 0.000 seconds.
-----------------------------------------------------------------
position=7
L[]=3 5 1 0 2 6 7 7 7 8
| | samhoo 回复于：2002-10-28 11:58:38
| 经整理的baggar的解答.
（如果有理解错误的地方，请指正）
baggar的算法性能相当不错，但是在某种情况下（Ｘ为数组的最大值）返回Ｘ的下标的时候仍有点小bug.
一）算法说明
程序先把原始数据分成三部分,用下标将这三部分分开.
[ 比X小的 ] [ 比X大的 ] [ X ]
再将第三部分移到第二部分之前,完成处理.
[ 比X小的 ] [ X ] [ 比X大的 ]
二）编译运行平台，机器类型/主频
cc/sco OpenServer 5.05, intel 1.2GMhz
三）Partition函数代码
/*
* L：输入数组
* n：数组大小
* X：X元素
* 返回X在数组中的下标
*/
int Partition(long *L, int n, long X)
{
//在这里插入你的代码
int DATA_LEN = n;
int loop,loopstart,looplen,tmp,found_loc;
//int big_count,equ_count,big_loc,equ_loc,test_num;
int big_count,equ_count,big_loc,equ_loc,test_num = X;
//int ori_data[DATA_LEN]={56,6,56,678,45,546,88,56,345,577};
long *ori_data = L;
looplen=DATA_LEN; //e.g: 1000 numbers
//test_num=56;
loopstart=big_count=equ_count=big_loc=0;
for(loop=loopstart;loop<looplen;loop++){
if(test_num>ori_data[loop]){
if(big_count!=0){
//exchange small to big locate.
tmp=ori_data[big_loc];
ori_data[big_loc]=ori_data[loop];
ori_data[loop]=tmp;
}
big_loc++;
continue;
}
if(test_num<ori_data[loop]){
big_count++;
continue;
}
if(test_num==ori_data[loop]){
tmp=ori_data[loop];
ori_data[loop]=ori_data[looplen-1];
ori_data[looplen-1]=tmp;
equ_count++;
looplen--;
loop--;
}
}
if(equ_count==0){
printf("ERROR:test number not found.\n");
exit(1);
}else{
found_loc=big_loc+1;
equ_loc=DATA_LEN-equ_count;
if(equ_count<big_count){
looplen=DATA_LEN;
tmp=equ_loc;
loopstart=big_loc;
}else{
looplen=big_loc+big_count;
tmp=big_loc;
loopstart=DATA_LEN-big_count;
}
for(loop=tmp;loop<looplen;loop++){
tmp=ori_data[loop];
ori_data[loop]=ori_data[loopstart];
ori_data[loopstart]=tmp;
loopstart++;
}
}
return found_loc;
}
四）至少给出前4组测试数据的结果
i )L[]={5,5,5,5,5,5,7,1,6,8}; n=10; X=5; （在main函数提供，注释掉其中一些语句即可）
X=5
L[]=5 5 5 5 5 5 7 1 6 8
-----------------------------------------------------------------
Check :correct.
Time : 0.000 seconds.
-----------------------------------------------------------------
position=2
L[]=1 5 5 5 5 5 5 6 8 7
ii )n=10的随机数组
X=31051
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086
-----------------------------------------------------------------
Check :incorrect.
Time : 0.000 seconds.
-----------------------------------------------------------------
position=10
L[]=16838 5758 10113 17515 4086 5627 23010 7419 16212 31051
iii)n=10,000,000的随机数组
Number of elements to sort=>10000000
Seed for random number generator (integer)=>1
X=5500
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086 2749 12767 9084 1206
0 32225 17543 25089 21183 25137 25566 26966 ...(too much number, ignore)
-----------------------------------------------------------------
Check :correct.
Time : 0.110 seconds.
-----------------------------------------------------------------
position=1678847
L[]=4086 2749 4978 4143 920 1422 1945 3894 1414 5262 3181 1201 5202 4434 4586 41
66 2582 5000 3214 4697 3123 ...(too much number, ignore)
iv )n=50,000,000的随机数组(小心，别影响别人工作)
Number of elements to sort=>50000000
Seed for random number generator (integer)=>1
X=16413
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086 2749 12767 9084 1206
0 32225 17543 25089 21183 25137 25566 26966 ...(too much number, ignore)
-----------------------------------------------------------------
Check :correct.
Time : 0.800 seconds.
-----------------------------------------------------------------
position=25052131
L[]=5758 10113 5627 7419 16212 4086 2749 12767 9084 12060 4978 10311 11367 13145
12754 11653 6561 13628 15188 4143 6967 ...(too much number, ignore)
v ）其他自己认为具有“边界”特性的数组。
X=56
L[]=56 6 56 678 45 546 88 56 345 577
-----------------------------------------------------------------
Check :correct.
Time : 0.000 seconds.
-----------------------------------------------------------------
position=3
L[]=6 45 56 56 56 546 88 345 678 577
| | beggar 回复于：2002-10-28 12:06:43
| [这个贴子最后由beggar在 2002/10/28 01:26pm 编辑]
samhoo你好.
以下是输出结果
===ori data===
16838 5758 10113 17515 31051 5627 23010 7419 16212 4086
===Total===
find data:31051 location:10 foundtimes:1 total exchage:1
ok
===Last array===
16838 5758 10113 17515 4086 5627 23010 7419 16212 31051
返回下标是排序后的易读位置值(下标+1) 以这儿就是(9+1).可能这让你误以为下标错误.在此澄清.
| | 离了水的蛤蟆 回复于：2002-10-28 16:14:26
| samhoo:
我检查的程序，问题的确出在边界上，那组测试数据中，X是最大的数（就是这么村），如果X是最小的数，也会出现同样问题，我进行了修改，将两个if 语句改成：
if (my_array[last_less_room] == OBJECT_NUMBER)
{
object_current_room = last_less_room;
while ((last_less_room < (MAX_SIZE - 1)) /* ！！！！！！ */
&& (my_array[last_less_room + 1] < OBJECT_NUMBER))
{
last_less_room ++;
}
INT_EXCHANGE (last_less_room, object_current_room);
if (((last_less_room + 1) < MAX_SIZE)
&& (my_array[last_more_room] < OBJECT_NUMBER))
{
INT_EXCHANGE (last_less_room + 1, last_more_room);
}
}
else if (my_array[last_more_room] == OBJECT_NUMBER)
{
object_current_room = last_more_room;
while ((last_more_room > 0) /* ！！！！！！ */
&& (my_array[last_more_room - 1] > OBJECT_NUMBER))
{
last_more_room --;
}
INT_EXCHANGE (last_more_room, object_current_room);
if ((last_more_room > 0)
&& (my_array[last_less_room] > OBJECT_NUMBER))
{
INT_EXCHANGE (last_more_room - 1, last_less_room);
}
}
else
{
INT_EXCHANGE (last_less_room, last_more_room);
}
加惊叹号的地方是出错的地方。
请帮忙再测试一下。
我自己的测试结果是，如果目标数据没有包含在数组中，也会出现错误的结果，我修改了两个while语句：
while ((my_array[last_less_room] < OBJECT_NUMBER)
&& (last_less_room < MAX_SIZE)) last_less_room ++;
while ((my_array[last_more_room] > OBJECT_NUMBER)
&& (last_more_room > 0)) last_more_room --;
if ((last_less_room >= MAX_SIZE) || (last_more_room < 0))
{
break;
}
另外，在最后打印last_less_room和last_more_room应该就是X的位置
| | aegis 回复于：2002-10-28 16:23:10
| 1） 看来 beggar 应该去当律师，善于无中生有
2） 诚如 chinajiji 所说，原题目可理解为 重复的 X 可以放在左边或右边，不用
挪到一起。那样 f_aegis 的第二个程序也是正确的
3） 如果讨论本题，我认为满足原题要求就可以了，可按 x 挪到一起的要求来讨论
至于程序的效率，1000 个数满足时间复杂度 O(N) 的各种算法我想差别不大
如果要详细讨论，建议 samboo 另开新贴子，并规定回复格式，这样比较整齐
建议最好大家先写 思路，再写 程序。如果对时间要求很高的话，建议由
samboo 用同一环境进行测试，再把结果公布，这样结果比较可信。
4） 我想，解决问题主要是能有独立的想法。同类的算法当然可以精益求精地改进，
如果性能差别不是太大，这里就不必那么详细了。至于我上次提出的 2 pass
的方法，主要是从另一个角度出发来满足题目要求，在 1000 的长度范围也基本
适用。它算法简单，并且 O(n) 显而易见, 并不用来做 time score 的。
| | beggar 回复于：2002-10-28 16:38:52
| [这个贴子最后由beggar在 2002/10/28 04:40pm 编辑]
我想samhoo的测试已经说得很清楚了.我想你应试去看一看本题所有回贴.学点东西才是
到现在你还认为你的理解是正确的话我也无话可说.只能说你理解能力太差或是有神经质.
你的根本代码无法编译或是根本没有提供源代码.我只能认为纸上谈兵确有其人.
在这个问题上我不想再和你讨论了.
从time test已经看得出结果了.你还嘴硬吗?如果你用你那种算法能够比我的算法用更少的时间,以后你在此出现的话我就退避以示我怕你...
拿你的那个算法的程式码来看啊.如果不行的话请你以后就不要鬼扯了.想清楚再回贴
我每次测试一个程序就重启测试下一个怎么样?
| | samhoo 回复于：2002-10-28 16:50:46
| 我前面的帖子已经给出了解答的“八股”，各位可参照解之。
总结2：
1）baggar的程序修改后，经测试没有发现问题。
2）离开水的蛤蟆在修改后，在测试如下数据时依然有陷入循环：
X=4086
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086 2749 12767 9084 1206
0 32225 17543 25089 21183 25137 25566
请baggar和离开水的蛤蟆以及Chinajiji自己整理一下自己的“八股”，举手之劳即可让大家顺畅沟通，何乐而不为？
至于aegis呢，如果没有可运行的代码，让大家去“品味”你的思路以及代码，恐怕是困难的。
测试我倒是可以为各位服务，计算一下time score。
| | beggar 回复于：2002-10-28 17:31:10
| 我赞成samhoo的意见.
以下beggar的算法思路:
1.将数组分为三部分 [小于X] [大于X] [X] 通过记录下三部分起始位置的下标的方法将他们分开
2.通过比较第二部分与第三部分的大小,适当移动第三部分或第二部分完成目标数组
[小于X] [X] [大于X]
1.从第一个数开始寻找X,
如果小于X--->首先检查他的前面是否有大于X的数(通过big_count),如果没有就直接逻辑上将它归 第一部分,如果他前面已经有大于X的数了就把他与big_loc指向数进行交换.big_loc的值加1后仍指向第一个大于X数的下标. 继续
如果大于X--->逻辑上将它归为第二部分,如果是第一个大于X的数就记录下这个X数的下标存为big_loc, 大于X的数的计数big_count加1,继续..
如果等于X--->将它与数组最后的数交换(放入第三部分),第三部分无素个数equ_count加1,同时整个循环体减1,应为最后一个数就是要找的X不用再比较了.,同时应该设置本次循环无效,因为把最后一个数换过来了.所以要对的换过来的数再作一次判断.
重复以上方法直到循环结束.
由于整个数组的长度已知 ,那么第三部分起始位置就是(数组长度-等于X的个数equ_count) equ_loc=datalen-equ_count
在上面的循环记录了第二部分无素个数以及第二部的起始下标
我们有足够的信息将这三个部分分开来
即得到了一个 [ 小于X ] [ 大于X] [X]三部分组成的数组
至于后面的,只要将第三部分移入第二部分之前即可或将第二部分与第三部分的最后相交换,这取决于哪个部分的元素个数较多,以减少移动次数.
优点.程序采用单循环,只需少量的比较和移动次数,在将三部分移到第二部分之前时根本无需比较.
不足:如果数组是有大数全部在左边,小数在右边将十分不利,但也比嵌套loop要快得多.
| | beggar 回复于：2002-10-28 17:45:09
| #include <sys/types.h>
#include <stdio.h>
#define DATA_LEN 10
main()
{//a num used for temport value.
int total_mov_time=0;//记录下总共交换的次数.作测试用.
int loop,loopstart,looplen,tmp,found_loc;
int big_count,equ_count,big_loc,equ_loc,test_num;
int ori_data[DATA_LEN]={16838,5758,10113,17515,31051,5627,23010,7419,16212,4086};
looplen=DATA_LEN; // 数组总长度
test_num=31051;//假设找31051
printf("===ori data===\n");
for(loop=0;loop<looplen;loop++)
printf("%d ",ori_data[loop]);
printf("\n"); //输入出原始数据
loopstart=big_count=equ_count=big_loc=0;
for(loop=loopstart;loop<looplen;loop++){ //从第一个无素开始循环
if(test_num>ori_data[loop]){ //如果小于X
if(big_count!=0){ //看它前面是否有大于X的数
//把他与第一个大于X的数交换,就成为了在小于X的部分的最后一个数
tmp=ori_data[big_loc];
ori_data[big_loc]=ori_data[loop];
ori_data[loop]=tmp;
total_mov_time++;
}
big_loc++; //第二部分的起始位置后移1个数
continue; //退出本循环
}
if(test_num<ori_data[loop]){ //如果大于X
big_count++; //将第二部分的元素个数+1
continue; //退出循环
}
if(test_num==ori_data[loop]){ //如果等于X
tmp=ori_data[loop]; //将第三部分前一个数与当前数交换
ori_data[loop]=ori_data[looplen-1];
ori_data[looplen-1]=tmp;
equ_count++; //第三部分元素个数+1
looplen--; //第三部分不再参于比较
loop--; //再次进行本次循环,因为把最后一个数换过来了
total_mov_time++;
}
}
if(equ_count==0){
printf("ERROR:test number not found.\n");
exit(1);
}else{//以下代码要所第二部分及第三部分的长度决定移动哪部分.
found_loc=big_loc+1;
equ_loc=DATA_LEN-equ_count;
if(equ_count<big_count){
looplen=DATA_LEN;
tmp=equ_loc;
loopstart=big_loc;
}else{
looplen=big_loc+big_count;
tmp=big_loc;
loopstart=DATA_LEN-big_count;
}
for(loop=tmp;loop<looplen;loop++){
tmp=ori_data[loop];
ori_data[loop]=ori_data[loopstart];
ori_data[loopstart]=tmp;
loopstart++;
total_mov_time++;
}
}
printf("\n===Total===\n"); //输出统计信息
printf("find data:%d location:%d foundtimes:%d total exchage:%d\nok\n",
test_num,found_loc,equ_count,total_mov_time);
printf("\n===Last array===\n");//输出整理后的数组
for(loop=0;loop<DATA_LEN;loop++)
printf("%d ",ori_data[loop]);
printf("\n");
exit(0);
}
| | wwjxjtu 回复于：2002-10-28 19:29:15
| 不好意思，前几次都是即时写的，没有经过测试，下面是经过测试的，希望各位能发现问题！
void specsort(int *num,int x,int len){
int i,j,tmp,pos,val,var,k,nx=0;
tmp=len-1;
for(i=0;i<tmp;i++){
if(*(num+i)>x){
for(j=tmp;j>i;j--){
if(*(num+j)<x){
val=*(num+i);
*(num+i)=*(num+j);
*(num+j)=val;
tmp=j-1;
break;
}
else if(*(num+j)==x){
pos=j;
nx++;
}
}
}
else if(*(num+i)==x){
pos=i;
nx++;
}
if(i==j) break;
}
if(nx==0){
printf("No such value %d in array",x);
exit(0);
}
if(i==j) tmp=*(num+i)>=x&&pos<i?i-1:i;
else{
if(*(num+i)>=x) tmp=pos>i?i:i-1;
else if(*(num+i+1)>=x) tmp=pos>i?i+1:i;
}
*(num+pos)=*(num+tmp);
*(num+tmp)=x;
pos=nx;
k=j=1;
var=tmp>len-tmp?tmp:len-tmp;
for(i=1;i<=var&&nx>1;i++){
if(tmp>=i&&*(num+tmp-i)==x){
val=(num+tmp-i);
*(num+tmp-i)=*(num+tmp-j);
*(num+tmp-j)=val;
nx--;
j++;
}
if(tmp+i<len&&*(num+tmp+i)==x){
val=*(num+tmp+i);
*(num+tmp+i)=*(num+tmp+k);
*(num+tmp+k)=val;
nx--;
k++;
}
}
printf("value x=%d's nums:%d\n",x,pos);
printf("The left position is :%d\n",tmp-j+1);
}
| | samhoo 回复于：2002-10-28 19:58:22
| 各位“程序员”情结浓厚如是！
前面给出了模板，以利于高效交流，更深入的探讨。本想比较比较时间，
看看谁可以发挥到极致，看看一段集中的小程序是如何进化的。
可是三位陆续给出的解答，在samhoo已经整理的情况下，仍未能照此执行，
哪怕是举手之劳，嘿嘿。
sorry,我是再没有精力逐个整理，也不会再“希望各位能发现问题”了。
谢谢各位的参与，尽管仍有遗憾。
| | 离了水的蛤蟆 回复于：2002-10-28 21:16:04
| 我没有发现问题呀，这是我的机器上运行的结果：
Number of elements to sort=>1000000
Seed for random number generator (integer)=>345678
X=14338
L[]=19454 7084 24182 7795 23488 18221 15545 10591 14569 5637 25832 22887 18232 7
949 27961 24949 24469 19989 291 9932 21814 ...(too much number, ignore)
-----------------------------------------------------------------
436816 436855
Check :correct.
Time : 0.600 seconds.
-----------------------------------------------------------------
position=436816
L[]=9615 7084 11244 7795 1183 8439 8506 10591 5056 5637 4593 8136 592 7949 7470
6621 3875 13969 291 9932 13627 ...(too much number, ignore)
| | samvelly 回复于：2002-10-31 23:51:32
| void main()
{
longL[20]={6,7,2,4,5,7,8,5,3,5,4,5,6,2,3,4,8,9,6,1};
long x = 5, tmp;
longp1,p2,s1,i;
for(p1=0, p2=19, s1=0; p1<＝p2; )
{
if( L[p1] > x )
{
tmp = L[p2];
L[p2--] = L[p1];
L[p1] = tmp;
}
else if( L[p1] == x ){
p1++;
}
else{
L[s1++] = L[p1++];
}
}
for( i=s1;i<＝p2;i++ ){
L[i] = x;
}
for( i=0;i<20;i++ )
printf("%d\n", L[i]);
}
| | 西北风 回复于：2002-11-26 20:05:40
| /******************************************************************************
name : a.c
function: 算法演示，把数组中等于5的元素放在中间，大于的放在后面，小于者放在前面
memo:
约定：数组中至少有一个5元素
这个程序我测试过的，应该解决本题目。很高兴能与大家认识，望诸位以后多多提携小弟。
version:
1.0.0.0 xibeifeng 2002.11.26
*******************************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 1000
int Display( int *pData )
{
int i;
for( i = 0; i < N; i ++ ) {
printf( "%5d", pData[i] );
if( (i+1) % 22 == 0 ) {
printf( "\n" );
}
}
printf( "\n\n" );
return 0;
}
int Partition( int *pData )
{
int i;
int t1, t2;
int pos5start, pos5end;
int iFlag;
int iNo4Flag;
pos5start = 0;
pos5end = 0;
t1 = 0;
t2 = 0;
iFlag = 0;
iNo4Flag = 0;
for( i = 0; i < N; i ++ ) {
if( pData[i] < 5 ) {
t1 = pData[0];
pData[0] = pData[i];
pData[i] = t1;
break;
}
}
if( i == N ) {
iNo4Flag = 1;
for( i = 0; i < N; i ++ ) {
if( pData[i] > 5 ) {
if( t2 == 0 ) {
t2 = pData[i];
}
pData[i] = pData[i] - t2 + 4;
}
}
for( i = 0; i < N; i ++ ) {
if( pData[i] < 5 ) {
t1 = pData[0];
pData[0] = pData[i];
pData[i] = t1;
break;
}
}
}
for( i = 1; i < N; i ++ ) {
if( pData[i] == 5 ) {
t1 = pData[1];
pData[1] = pData[i];
pData[i] = t1;
break;
}
}
for( i = 2; i < N; i ++ ) {
if( pData[i] > 5 ) {
t1 = pData[2];
pData[2] = pData[i];
pData[i] = t1;
break;
}
}
for( i = 0; i < N; i ++ ) {
if( (0==iFlag) && (pData[i]<5) ) {
continue;
}
if( (0==iFlag) && (pData[i]==5) ) {
iFlag = 1;
pos5start = i;
continue;
}
if( (1==iFlag) && (pData[i]==5) ) {
continue;
}
if( (1==iFlag) && (pData[i]>5) ) {
pos5end = i - 1;
iFlag = 2;
continue;
}
if( (1==iFlag) && (pData[i]<5) ) {
pData[pos5start] = pData[i];
pData[i] = 5;
pos5start ++;
continue;
}
if( (2==iFlag) && (pData[i]>5) ) {
continue;
}
if( (2==iFlag) && (pData[i]<5) ) {
t1 = pData[pos5end+1];
pData[pos5end+1] = 5;
pData[pos5start] = pData[i];
pData[i] = t1;
pos5start ++;
pos5end ++;
continue;
}
if( (2==iFlag) && (pData[i]==5) ) {
t1 = pData[pos5end+1];
pData[pos5end+1] = 5;
pData[i] = t1;
pos5end ++;
continue;
}
}
if( iNo4Flag == 1 ) {
for( i = 0; i < N; i ++ ) {
if( pData[i] != 5 ) {
pData[i] = pData[i] - 4 + t2;;
}
}
}
return 0;
}
main()
{
int i, *data;
data = (int *)malloc( sizeof(int)*N );
if( NULL == data ) {
perror( "malloc fail" );
return -1;
}
srand( time(NULL) );
for( i = 0; i < N; i ++ ) {
data[i] = 1 + rand()%20;
}
i = rand()%N; data[i] = 5;
i = rand()%N; data[i] = 5;
i = rand()%N; data[i] = 5;
/* Display( data ); */
Partition( data );
/* Display( data ); */
return 0;
}
| | 蓝色键盘 回复于：2003-03-19 14:15:50
| [quote:e1d34c2180="aegis"]菜鸟啊菜鸟，一群菜鸟！谭笨蛋的书看多了吧？只会照抄，没有一点脑子！
无论干什么，都要先考虑算法！
比 x 小的放在前面，比 x 大的放到后面！算法都告诉你们了，还不会？！
从前面开始，比 x 小，则跳过，比 x 大，和“最后”的那个交换，
反复进行；直到 ok。
int MyCode () // return x position
{
long L [ 1000 ], l;
int s, e;
for ( s = 0, e = 999; s < e;)
{
if ( L [ s ] > X )
{
l = L [ e ];
L [ e -- ] = L [ s ];
L [ s ] = l;
}
else
s ++;
}
return s;
}
上面假定数组里没有其他和 X 相同的数值
简单吧？一群菜鸟
当然还可以有更好的算法，不是菜鸟的自己做吧[/quote:e1d34c2180]呵呵，有意思，建议定义一个100000000的long数据，然后做所谓腾挪大法，建议你构造一个哈希函数，看看效率如何？？？
| | menp9999 回复于：2003-03-19 15:01:42
| [quote:56c483dc78="离了水的蛤蟆"]e_room]) ......这一段）
如果两头都停止在等于X的数的位置，那么从它们之间找到一个不等于X的数,
与两端的数进行互换，这样循环就能够继续下去，直至last_less_room和last_more_room之间全部都是X。[/quote:56c483dc78]
好思路.
这个题目的目的其实并没有要求排序.
实际就是从第一个数查找大于X的数,查到一个就相应的从最后反向查找小于X的数,交换一下.
我想这位朋友的答案就是最后的答案了.
| | menp9999 回复于：2003-03-19 15:05:06
| [quote:55deef61d2="蓝色键盘"]呛牵幸馑迹ㄒ槎ㄒ逡桓?00000000的long数据，然后做所谓腾挪大法，建议你构造一个哈希函数，看看效率如何？？？[/quote:55deef61d2]
构造HASH不符合题目的意思,在最坏的情况呢?你的空间消耗是多少?而且HASH要设计指针,看起来指针没有空间消耗,其实会没有么?
| | wangz 回复于：2003-03-19 16:17:02
| [quote:a36192796b="aegis"];
}
else
s ++;
}
return s;
}
上面假定数组里没有其他和 X 相同的数值
简单吧？一群菜鸟
当然还可以有更好的算法，不是菜鸟的自己做吧[/quote:a36192796b]
同意这位仁兄意见，这只是腾挪，又不是排序！！
| | biansj 回复于：2003-03-19 17:48:03
| 这是老头我的解答
我的平台为：
winxp-cgywin
intel-p4-1.8
512M
gcc编译器
结果：
Number of elements to sort=>10000000
Seed for random number generator (integer)=>1
X=356357611
L[]=1481765933 1085377743 1270216262 1191391529 812669700 553475508 445349752 1344887256 730417256 1812158119 147699711 880268
1 1889772843 686078705 2105754108 182546393 1949118330 220137366 1979932169 1089957932 1873226917 ...(too much number, ignore)
-----------------------------------------------------------------
Check :correct.
Time : 0.270 seconds.
-----------------------------------------------------------------
position=1660433
L[]=126327593 46166452 192565618 137712912 20451713 225182725 97345414 103854117 33560245 261810579 147699711 24076199 2350035
347814638 174345139 182546393 167555317 220137366 271580728 167974811 331088965 ...(too much number, ignore)
Number of elements to sort=>50000000
Seed for random number generator (integer)=>1
X=1755472876
L[]=1481765933 1085377743 1270216262 1191391529 812669700 553475508 445349752 1344887256 730417256 1812158119 147699711 88026835
1 1889772843 686078705 2105754108 182546393 1949118330 220137366 1979932169 1089957932 1873226917 ...(too much number, ignore)
-----------------------------------------------------------------
Check :incorrect.
Time : 0.811 seconds.
-----------------------------------------------------------------
position=40870704
L[]=1481765933 1085377743 1270216262 1191391529 812669700 553475508 445349752 1344887256 730417256 739188062 147699711 880268351
125787503 686078705 1039920646 182546393 350985345 220137366 503919052 1089957932 996044826 ...(too much number, ignore)
[code:1:9a0bda07b5]
int Partition(long *L, int n, long X)
{
//在这里插入你的代码
int start_pos=0,end_pos=n-1,tmp,dup_num=0;
for(;;)
{
if(end_pos-start_pos-dup_num==0||(end_pos-start_pos-dup_num==1&&L[start_pos]<=L[end_pos-dup_num]))
break;
while(L[start_pos++]<X&&start_pos!=end_pos-dup_num);
start_pos==0? : start_pos--;
while(L[end_pos--]>X&&start_pos!=end_pos-dup_num);
end_pos==n-1? : end_pos++;
if(start_pos!=end_pos-dup_num)
switch(L[end_pos]==X)
{
case 1:
if(L[start_pos]==X)
{
dup_num++ ;
tmp=L[start_pos];
L[start_pos]=L[end_pos-dup_num];
L[end_pos-dup_num]=tmp;
}
else
{
tmp=L[start_pos];
L[start_pos]=L[end_pos];
L[end_pos]=tmp;
tmp=L[start_pos];
L[start_pos]=L[end_pos-dup_num-1];
L[end_pos-dup_num-1]=tmp;
end_pos--;
}
break;
case 0:
tmp=L[start_pos],L[start_pos]=L[end_pos],L[end_pos]=tmp;
break;
default:
break;
}
}
return end_pos;
}
[/code:1:9a0bda07b5]
非常感谢samhood的这种交流方式，还有程序模板！！:D :D
真省力气，算法我也不说明了，反正也没人看。8) 8)
| | thinkeryy 回复于：2003-04-18 12:04:12
| 我的方法：
#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[i] <objnum;i++);
for(;array[j] >objnum;j--);
// printf(" array[%d]=%d",i,array[i]);
// printf(" array[%d]=%d\n",j,array[j]);
// getchar();
if((array[i] == objnum)&&(array[j] ==objnum))
{
for( k=i;k<=j;k++)
{
if(array[k] <objnum)
{
tmp =array[i];
array[i] = 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[i];
array[i]=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 回复于：2003-12-25 14:55:36
| 来这里就是想回复这个帖子，如有问题欢迎探讨。
解决方法：
首先设定数组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[b]<=X)
{
if (L[b]<X) {L[a]=L[b];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[b]>X而且L[c]<X
chage(L[b],L[c]);//交换L[b],L[c]中存放的数据，此处还可以部分改进
}
for(int i=a+1;i<d;i++;L[i]=X);//从a到d间的数据是X
到这里为止，全部算法完成，最快速解决此问题。
| |
|
