那谁的技术博客

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

<<算法导论>>一起学之一:我写的一个Merge算法

       第二章中给出的Merge算法,本质是初始化两个数组分别保存前后两个已经排序好了的数组,然后逐个扫描比较两个数组中的元素把元素放在原来数组的合适的位置上.
       不知道之前有没有人做过这个算法,比起书上的那个并不见得高明,在最坏的情况下要交换元素(N/2)*(N/2)也就是N的平方数量级(这里N是数组的大小),这个最坏的情况就是前面的数组中的元素都比后面数组的元素大.
       虽然不见得是最好的,不过至少是自己思考的结果,放上来也许对别人有启发.
      
// 如何证明算法的正确性?
// 我改进的merge算法
void Merge1(int array[], int start, int mid, int end)
{
    
// 思想:设置两个哨兵,分别指向前后两个数组,
    
// 逐个把前面的数组的元素和后面数组的元素进行比较
    
// 如果前面的元素不比后面的元素大,那么前面数组的哨兵前移一位
    
// 否则,交换两个元素,并且对后面的数组进行扫描,确保新的元素放在合适的位置
    
// 当前面的数组扫描完毕之后循环结束
    for (int i = start; i < mid + 1++i)
    
{
        
if (array[i] > array[mid + 1])
        
{
            swap(
&array[i], &array[mid + 1]);

            
// 把新放入后面数组的元素放到合适的位置去
            for (int j = mid +1; j + 1 <= end && array[j] > array[j + 1]; ++j)
            
{
                swap(
&array[j], &array[j + 1]);
            }

        }
       
    }

}


// 书上的算法实现
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 Merge_Sort(int array[], int start, int end)
{
    
if (start < end)
    
{
        
int i;
        i 
= (end + start) / 2;
        Merge_Sort(array, start, i);
        Merge_Sort(array, i 
+ 1, end);

        Merge1(array, start, i, end);
    }

}

 

      对外的接口:Merge_Sort(array, start, end);
即:传入一个数组,和起始位置中止位置,比如数组array[10],那么就是Merge_Sort(arrry,0,9)

posted on 2006-03-04 22:29 那谁 阅读(1456) 评论(2)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: >一起学之一:我写的一个Merge算法  回复  更多评论   

这个 blog 好,代码还可以伸缩啊。回头得给 fan 老大提提意见了。
2006-03-07 15:13 | win_hate

# re: >一起学之一:我写的一个Merge算法  回复  更多评论   

这个算法不需要辅助数组是一个原地排序。但是用了两重循环,复杂度为O(N^2),失去了归并排序的本意。
第二重循环是一个冒泡过程可改成折半插入,减少比较和元素移动。以重循环可先用折半查找寻找前半部
分第一个比array[mid+1]大的,但是这个算法仍然是O(N^2)的。原地的归并排序如bartcher奇偶归并排序
复杂度为O(N(logN)^2)可以看Robert Sedgewick的algorithm in c++,里面有实现。
2006-04-21 11:33 | yangtou

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理