那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

常见排序算法的实现(六)-归并排序

归并排序的算法思想:把待排序序列分成相同大小的两个部分,依次对这两部分进行归并排序,完毕之后再按照顺序进行合并.

// 归并排序中的合并算法
void Merge(int array[], int start, int mid, int end)
{
    
int temp1[10], temp2[10];
    
int n1, n2;
    n1 
= mid - start + 1;
    n2 
= end - mid;

    
// 拷贝前半部分数组
    for (int i = 0; i < n1; i++)
    
{
        temp1[i] 
= array[start + i];
    }

    
// 拷贝后半部分数组
    for (int i = 0; i < n2; i++)
    
{
        temp2[i] 
= array[mid + i + 1];
    }

    
// 把后面的元素设置的很大
    temp1[n1] = temp2[n2] = 1000;
    
// 逐个扫描两部分数组然后放到相应的位置去
    for (int k = start, i = 0, j = 0; k <= end; k++)
    
{
        
if (temp1[i] <= temp2[j])
        
{
            array[k] 
= temp1[i];
            i
++;
        }

        
else
        
{
            array[k] 
= temp2[j];
            j
++;
        }

    }

}


// 归并排序
void MergeSort(int array[], int start, int end)
{
    
if (start < end)
    
{
        
int i;
        i 
= (end + start) / 2;
        
// 对前半部分进行排序
        MergeSort(array, start, i);
        
// 对后半部分进行排序
        MergeSort(array, i + 1, end);
        
// 合并前后两部分
        Merge(array, start, i, end);
    }

}

posted on 2006-07-04 01:34 那谁 阅读(1606) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理