分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。其一般的算法设计模式如下：
Divide-and-Conquer(P)
{
if (｜P｜＜＝n0) Adhoc(P):
divide P into smaller subinstance
P1, P2,...,Pk
for (i=0; i {
yi = Divide-and-Conquer(Pi);
}
return Merge(y1,y2,...,yk);
}
许多问题可以取k=2，这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总比子问题规模不等的做法要好。
二分搜索算法是运用分治策略的一个典型例子。
#include
int BinarySearch( int *arr, size_t n, int elem )
{
size_t left = 0;
size_t right = n-1;
size_t middle;
while (left <= right)
{
middle = (left+right)/2;
if (arr[middle] == elem)
{
return middle;
}
else if(arr[middle] < elem)
{
left = middle + 1;
}
else
{
right = middle - 1;
}
}
return -1;
}
int main(int argc, char * argv[])
{
int arr[] = {1,2,3,4,5,6,7} ;
printf( "%d\n", BinarySearch( arr, 7, 6 ) );
return 0;
}
分治算法采用的是递归的思想，我们都知道递归的开销比较大，所以一般的分治算法也可以采用非递归来实现。下面以合并排序为例：
合并排序的递归算法：
#include
#include
void Merge( int *arr, size_t left, size_t right )
{
size_t middle = (left + right)/2;
size_t r = middle + 1;
size_t l = left;
int *temp = calloc( right-left+1, sizeof(int) );
int *p = temp;
while (l<=middle && r<=right)
{
if (arr[l] <= arr[r] )
{
*p = arr[l];
l++;
}
else
{
*p = arr[r];
r++;
}
p++;
}
/* copy the rest elements in the left to the allocated array */
if (l <= middle)
{
*p = arr[l];
p++;
l++;
}
int *end = p;
p = temp;
l = left;
/* copy it back to the array */
while( p != end )
{
arr[l] = *p;
p++;
l++;
}
free( temp );
}
void MergeSort( int *arr, size_t left, size_t right )
{
if (left >= right)
{
return;
}
size_t k = (left + right)/2;
MergeSort( arr, left, k );
MergeSort( arr, k+1, right);
Merge( arr, left, right );
}
int main(int argc, char * argv[])
{
int arr[] = {1,5,7,2,6,3,4} ;
MergeSort( arr, 0, 6 );
size_t i = 0;
for (i=0; i<7; i++)
{
printf( "%d ", arr[i] );
}
printf( "\n" );
return 0;
}
递归算法是一种从上到下的思想，非递归则从下到上。递归将其分成大致相等的两组，那么到最后肯定是两个元素进行排序，我们可以从底向上，先两两排序，再四个一组进行排序，以此类推，这样与递归相比，少了合并的过程。下面给出全并排序的非递归算法：
#include
#include
#include
#include
/* tmp: store the ordered elements for a while
span: to indicate how many numbers we sort each time
*/
void MergeSpan( int *arr, size_t len, int *tmp, size_t i, size_t span )
{
int end = i + span-1;
end = (end>=(len-1))?(len-1):end; /* right limit */
/* we will use i,span and tmp later, so don't change them */
int fir = i;
int sec = i+span/2;
int *p = tmp;
while (fir<=i+span/2-1 && sec<=end)
{
if (arr[fir] <= arr[sec])
{
*p = arr[fir];
fir++;
}
else
{
*p = arr[sec];
sec++;
}
p++;
}
while (fir<=i+span/2-1)
{
*p = arr[fir];
fir++;
p++;
}
/* copy it back to the array */
int *ptr = tmp;
fir = i;
while (ptr < p)
{
arr[fir] = *ptr;
ptr++;
fir++;
}
//memset( tmp, 0, 2*span*sizeof(int) ); /* not necessary, */
}
void MergeSort( int *arr, size_t len )
{
int *tmp = calloc( len, sizeof(int) );
size_t span = 2;
size_t i = 0;
size_t j = 1;
while (span <= len)
{
span = (int)pow(2,j);
j++;
for (i=0; i {
MergeSpan( arr, len, tmp, i, span );
}
}
// free( tmp );
}
int main(int argc, char * argv[])
{
int arr[] = {4,6,3,1,2,5};
MergeSort( arr, 6);
int i = 0;
for (i=0; i<6; i++)
{
printf( "%d ", arr[i] );
}
printf( "\n" );
return 0;
}
用gcc进行编译时需加上-lm选项。
上面的非递归算法中，我们是按一种平均的思想，即平均分成几组，事实上，有些元素可能已经排好序了，比如{5,1，2,3，4}，如果我们将它们拆成两组{5}和{1，2,3，4}，然后将这两组进行合并即可，快速排序算法其分成的两组也不是平均分配的。按照这种思想，我们可以编程实现如下：
#include
#include
#define NUM 7
/* 基本思想是将一个数组分成已经自然排序好的几个子数组段，再两两合并。由于每个数组段的长度不定，所以我们用链表来实现 ，比如{1,3,5,2,4,6}将*/
/* 将每个元素变成一个结点 */
typedef struct Node{
size_t index;
struct Node *next;
}Node;
/* 此链表存贮将每个子段的连起来 */
typedef struct NodeList
{
Node *node;
struct NodeList *next;
}NodeList;
/* 创建结点及子数段 */
void create_node( int *arr, size_t len, Node *node, NodeList *ndlt )
{
node->index = 0;
node->next = NULL;
ndlt->node = node;
ndlt->next = NULL;
Node *nnext;
size_t i = 0;
for (i=1; i {
nnext = node+1;
nnext->index = i;
nnext->next = NULL;
if (arr[nnext->index] >= arr[node->index])
{
node->next = nnext;
}
else /* 当遇到非自然排序时创建新的链表 */
{
NodeList *nl = malloc(sizeof(NodeList)); /* 合并的过程中释放 */
nl->node = nnext;
nl->next = NULL;
ndlt->next = nl;
ndlt = nl;
nl = NULL;
}
node = nnext;
}
}
/* 合并指定的两个链表 */
void mergenl( int *arr, NodeList *fir, NodeList *sec )
{
Node *fn = fir->node;
Node *sn = sec->node;
Node *p = fir->node;
if (arr[fn->index] >= arr[sn->index])
{
fir->node = sn;
sn = sn->next;
}
else
{
fir->node = fn;
fn = fn->next;
}
p = fir->node;
while (fn != NULL && sn != NULL)
{
if (arr[fn->index] >= arr[sn->index] )
{
p->next = sn;
sn = sn->next;
p = p->next;
}
else
{
p->next = fn;
fn = fn->next;
p = p->next;
}
}
while (fn != NULL)
{
p->next = fn;
p=p->next;
fn=fn->next;
}
while (sn != NULL)
{
p->next = sn;
p = p->next;
sn = sn->next;
}
}
/* 进行两两合并 */
void merge( int *arr, NodeList *ndlt )
{
NodeList *keep = ndlt;
NodeList *merg;
while (keep->next != NULL)
{
ndlt = keep;
while ( ndlt->next != NULL )
{
merg = ndlt->next;
mergenl( arr, ndlt, merg );
if (merg->next != NULL)
{
ndlt->next = merg->next;
}
else
{
ndlt->next = NULL;
break;
}
free( merg );
}
}
}
int main(int argc, char * argv[])
{
int arr[] = {7,4,6,2,1,5,3} ;
Node node[NUM];
NodeList ndlt;
create_node( arr, NUM, node, &ndlt );
merge( arr, &ndlt );
Node *n = ndlt.node;
while (n != NULL )
{
printf( "%d ", arr[n->index] );
n=n->next;
}
printf( "\n" );
return 0;
}
阅读(4045) | 评论(0) | 转发(0) |
