这段快排用的是什么算法？求分析他的思路,该如何解决

这段快排用的是什么算法？求分析他的思路

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <omp.h>

#define ARRAY_SIZE 100
#define NUM_THREADS ARRAY_SIZE

int A[ARRAY_SIZE];
int RC[ARRAY_SIZE];
int LC[ARRAY_SIZE];
int f[ARRAY_SIZE];
int root;

void printarray(int root)
{
if (LC[root]!= ARRAY_SIZE+1)
printarray(LC[root]);
printf("%d \n", A[root]);
if (RC[root]!= ARRAY_SIZE+1)
printarray(RC[root]);
}

int main()
{
omp_set_num_threads(NUM_THREADS);
int i, j, k;
//initialize the array A
srand((int)time(0));
for (i=0; i<ARRAY_SIZE; i++)
A[i] = (int)rand();

#pragma omp parallel for shared(root)
for (i=0; i<ARRAY_SIZE; i++)
root = i;

for (i=0; i<ARRAY_SIZE; i++)
{ 
f[i] = root; 
LC[i] = RC[i] = ARRAY_SIZE+1; 
} 

#pragma omp parallel shared(LC, RC, f, root) private(i)
{
i = omp_get_thread_num();
while(1)
{
if ( i == root )
break;
if ((A[i] < A[f[i]]) || ((A[i] == A[f[i]]) && (i<f[i])))
{
if (LC[f[i]] == ARRAY_SIZE+1)
LC[f[i]] = i;
if ( i == LC[f[i]] )
break;
else
f[i] = LC[f[i]];
}
else
{
if (RC[f[i]] == ARRAY_SIZE+1)
RC[f[i]] = i;
if ( i == RC[f[i]] )
break;
else
f[i] = RC[f[i]];
}
}
}
printarray(root);
return 0;
}

快排?
[解决办法]
我的分析如下，有什么不对的请高手指教，谢谢
模拟二叉树的排序：

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <omp.h>

#define ARRAY_SIZE 10
#define NUM_THREADS ARRAY_SIZE

int A[ARRAY_SIZE];
int RC[ARRAY_SIZE];
int LC[ARRAY_SIZE];
int f[ARRAY_SIZE];
int root;

void printarray(int root)
{
if (LC[root]!= ARRAY_SIZE+1)
printarray(LC[root]);
printf("%d \t", A[root]);
if (RC[root]!= ARRAY_SIZE+1)
printarray(RC[root]);
}

int main()
{
omp_set_num_threads(NUM_THREADS);
int i, j, k;
//initialize the array A
srand((int)time(0));
for (i=0; i<ARRAY_SIZE; i++)
A[i] = (int)rand();

#pragma omp parallel for shared(root)
for (i=0; i<ARRAY_SIZE; i++)
root = i;

for (i=0; i<ARRAY_SIZE; i++)
{ 
f[i] = root;  
 
LC[i] = RC[i] = ARRAY_SIZE+1; 
} 

#pragma omp parallel shared(LC, RC, f, root) private(i)
{
i = omp_get_thread_num();
while(1)
{
if ( i == root )  //搜索到根结点就停止
break;
if ((A[i] < A[f[i]]) 
[解决办法]
 ((A[i] == A[f[i]]) && (i<f[i]))) //f[i]为上一次的结点，相当于确定i为f[i]的左子树还是右子树
{
if (LC[f[i]] == ARRAY_SIZE+1) //f[i]结点的左子树没有数，从上面可知，没有数时默认初始化为ARRAY_SIZE+1，则f[i]的左子树标志为i
LC[f[i]] = i;
if ( i == LC[f[i]] )//因为已经标志，一次只确定一个数在数的位置，所以确定了就跳出循环
break;
else   //承接第一个if的（LC[f[i]] ！= ARRAY_SIZE+1），左子树有数，那么f[i]结点为f[i]的左子树，直到插入为止，树的向下搜索就是向下搜的
f[i] = LC[f[i]];

}
else//与上面的一样，插入右子树
{
if (RC[f[i]] == ARRAY_SIZE+1)
RC[f[i]] = i;
if ( i == RC[f[i]] )
break;
else
f[i] = RC[f[i]];
}
}
}
printarray(root);
system("pause");
return 0;
}

查看更多 下一篇