合并排序
合并排序(MERGE
SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假
设数组A有N个元素,那么可以看成数组A是又N个有序的子序列组成,每个子序列的长度为1,然后再两两合并,得到了一个 N/2
个长度为2或1的有序子序列,再两两合并,如此重复,值得得到一个长度为N的有序数据序列为止,这种排序方法称为2—路合并排序。
例如数组A有7个数据,分别是: 49 38 65 97 76 13 27,那么采用归并排序算法的操作过程如图7所示:
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由长度为1的7个子序列组成
第一次合并之后 [38 49] [65 97] [13 76] [27]
看成由长度为1或2的4个子序列组成
第二次合并之后 [38 49 65 97] [13 27 76]
看成由长度为4或3的2个子序列组成
第三次合并之后 [13 27 38 49 65 76 97]
图6 归并排序算法过程图
合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现,形式上较为简单,但实用性很差。
合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数
是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次,按照这一
X
规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。
*/
-
public
static
void
mergeSort(
int
[] array,
int
low,
int
height){
-
if
(low>=height)
return
;
-
int
mid = (low+height)/
2
;
-
mergeSort(array,low,mid);
-
mergeSort(array,mid+1
,height);
-
merge(array,low,mid,height);
-
}
-
-
public
static
void
merge(
int
[] array,
int
low,
int
mid,
int
height){
-
int
i,j,h,k;
-
int
[] temp =
new
int
[array.length];
-
i=low;
-
h=low;
-
j=mid+1
;
-
-
while
(h<=mid&&j<=height){
-
if
(array[h]<array[j]){
-
temp[i] = array[h];
-
h++;
-
}else
{
-
temp[i] = array[j];
-
j++;
-
}
-
i++;
-
}
-
-
if
(j>height){
-
for
(k=h;k<=mid;k++){
-
temp[i] = array[k];
-
i++;
-
}
-
}else
{
-
for
(k=j;k<=height;k++){
-
temp[i] = array[k];
-
i++;
-
}
-
}
-
for
(k=low;k<=height;k++){
-
array[k] = temp[k];
-
}
-
}
分享到:
相关推荐
5-14 归并排序时间复杂度及排序算法复杂度对比 5-15 二分查找 5-16 二分查找时间复杂度 六、树和树的算法 6-01 树的概念 6-02 二叉树的概念 6-03 二叉树的广度优先遍历 6-04 二叉树的实现 6-05 二叉树的先序...
本文将对几种常见的排序算法进行总结,包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、拓扑排序、锦标赛排序以及基数排序。 **冒泡排序**: 冒泡排序是最基础的排序算法之一,通过不断...
1. 题目 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。...2. 归并排序 详见 LeetCode 315. 计算右侧小于当前元素的个数(二叉查找树&二分查找&归并排序逆序数总结) 方法
排序可以使用快速排序、归并排序等高效算法,这里的关键在于排序后的序列可以帮助我们找到最长子序列。 2. **记录最大值**:创建一个新的数组,用于存储每个位置的最长子序列的结束点。数组的初始值为1,表示每个...
7. **排序和查找**:除了上述数组的排序算法,还有其他高级排序算法如归并排序、希尔排序、快速排序的变种等。查找算法有顺序查找、二分查找、哈希查找等,它们的效率分析是重要考点。 8. **动态规划**:在数据结构...
归并排序 二分法 deep TypeScript ts效能开发【Recent update】 h5c3 h5开发坑点小总结:fire: h5适配 开源项目 wechatApp-template refactor-boilerplate omim-tag vscode有趣的插件 修改vscode背景图 自编杂文...
在算法方面,考研中常见的有排序算法(如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等)、查找算法(如顺序查找、二分查找、哈希查找)、图的遍历算法(如深度优先搜索DFS和广度优先搜索BFS)、字符...
- **排序算法**:冒泡、选择、插入、快速、归并等,以及时间复杂度分析。 - **查找算法**:二分查找,哈希查找。 - **常用数据结构**:栈、队列、链表、树、图等。 通过阅读《Java常见面试题.doc》、《Java面试...