排序算法之归并排序-蒲公英云

排序算法之归并排序

蔚落 2022-07-14 05:20 334阅读 0赞

归并排序>

之前曾经实现过堆排序，它用到了完全二叉树，但是堆的设计本身就是比较复杂的，而今天要实现的归并排序同样的也用到了完全二叉树的思想，这种思想比堆排序较为简单.

归并排序是利用归并的思想实现的排序算法.它的思路是:我们将具有n个序列的无序的数组序列两两合并排序后再合并，最终获得了一个有序的数组.

归并排序的实现也极其简单:

1).将这个数组分成两个区间.[start,mid],[mid+1,end].

2).从这两个区间中找到较小的值按照顺序放入暂存数组tmp中.

3).如果有区间中的数据没有放入暂存数组中则放入.

4).因为是将区间中较小的值放入暂存数组tmp中，所以最后tmp中的值是有序的，只需要将tmp中的值拷入数组a 中即可

Center

void _MergeSort(int *a,int *tmp,int start,int end)
{
    int mid=start+((end-start)>>1);
    if(start < mid)
        _MergeSort(a,tmp,start,mid);
    if(mid+1 < end)
        _MergeSort(a,tmp,mid+1,end);
    //分成两个区间 [start,mid]和[mid+1,end]
    int start1=start;
    int end1=mid;
    int start2=mid+1;
    int end2=end;
    int index=start;
    //从两个区间中选择最小的放入tmp中
    while (start1 <= end1 && start2 <= end2)
    {
        if(a[start1] < a[start2])
            tmp[index++]=a[start1++];
        else
            tmp[index++]=a[start2++];
    }
    while (start1 <= end1)
    {
        tmp[index++]=a[start1++];
    }
    while (start2 <= end2)
    {
        tmp[index++]=a[start2++];
    }
    //将tmp中的数据写入a中
    for (int i=start;i<index;++i)
    {
        a[i]=tmp[i];
    }
}
void MergeSort(int *a,int start,int end)
{
    int *tmp=new int[end-start+1];
    _MergeSort(a,tmp,start,end);
    delete []tmp;
}