我们知道把两个已经排好序的数组合并成一个是很容易,也非常快的.于是根据这种思路就有个归并排序.
归并排序(Merge Sort)
并归排序利用了递归的思想,把数组分割成很多小的数组序列,然后两两合并,最终整个数组有序.因为递归到一个子数组序列只有一个元素时,然后将这样的数组合并就得到2个元素的有序数组,依次类推.
//合并两个子数组序列,以mid为中间点,begin,end为前后界限,分割成两个子序列.
void MergeSortedArr(int* arr, int begin , int mid , int end, int* tmpArr)
{
int lBegin = begin; //左边序列的起始索引号
int lEnd = mid; //左边序列的最后索引号
int rBegin = mid + 1;
int rEnd = end;
int k = 0; //两个子序列元素个数之和
while( lBegin <= lEnd && rBegin <= rEnd) //当有一个子序列遍历完了退出循环
{
if(arr[lBegin] <= arr[rBegin])
tmpArr[k++] = arr[lBegin++];
else
tmpArr[k++] = arr[rBegin++];
}
while(lBegin <= lEnd)
tmpArr[k++] = arr[lBegin++];
while(rBegin <= rEnd)
tmpArr[k++] = arr[rBegin++];
for(int i = 0; i < k; i++)
arr[begin + i] = tmpArr[i];
}
void MegerSort(int* arr, int begin , int end, int* tmpArr)
{
if( begin < end)
{
int mid = (begin + end) /2;
MergeSort(arr, begin , mid , tmpArr); //将左边序列排序
MergeSort(arr, mid + 1, end, tmpArr); //将右边序列排序
MergeSortedArr(arr, begin , mid, end, tmpArr); //合并两个序列
}
}
测试代码:
int arr[] = { 1,3,2,4,5,7,6,8,9};
int len = sizeof(arr)/sizeof(int);
int* tmpArr = new int[len];
MergeSort(arr, 0, len - 1, tmpArr);
delete []tmpArr;
分享到:
相关推荐
MATLAB实现《算法设计与分析》中的插入排序、二分归并排序、归并排序实验,其中包括.m文件和实验报告,安徽大学本科课程。
试通过随机数据比较归并排序、基数排序各算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有。关键字...
归并排序C语言实现
C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
根据算法导论实现的归并排序算法
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
归并排序,比较高效的排序算法之一。这是一个例子,一个关于归并排序的例子。
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
c语言实现归并排序,递归方式实现,含详细注释
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...
实现归并排序的一个类
算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
本人自己写的一些排序算法,这是系列1归并排序算法实现,