这篇文章主要介绍了java数据结构排序算法之归并排序,结合具体实例形式详细分析了归并排序的原理、实现技巧与相关注意事项,需要的朋友可以参考下
本文实例讲述了java数据结构排序算法之归并排序。分享给大家供大家参考，具体如下：
在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列，而归并排序的思想是：基于合并，将两个或两个以上有序表合并成一个新的有序表
归并排序算法：假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列长度为1,然后两两归并，得到n/2个长度为2（n为奇数的时候，最后一个序列的长度为1）的有序子序列。在此基础上，再对长度为2的有序子序列进行亮亮归并，得到若干个长度为4的有序子序列。如此重复，直到得到一个长度为n的有序序列为止。这种方法被称作是：2-路归并排序（基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列）。
算法实现代码如下：
立即学习“Java免费学习笔记（深入）”；
package exp_sort;
public class MergeSort {
/**
* 相邻两个有序子序列的合并算法
*
* @param src_array
* @param low
* @param high
* @param des_array
*/
public static void Merge(int src_array[], int low, int high,
int des_array[]) {
int mid;
int i, j, k;
mid = (low + high) / 2;
i = low;
k = 0;
j = mid + 1;
// compare two list
while (i <= mid && j <= high) {
if (src_array[i] <= src_array[j]) {
des_array[k] = src_array[i];
i = i + 1;
} else {
des_array[k] = src_array[j];
j = j + 1;
}
k = k + 1;
}
// if 1 have,cat
while (i <= mid) {
des_array[k] = src_array[i];
k = k + 1;
i = i + 1;
}
while (j <= high) {
des_array[k] = src_array[j];
k = k + 1;
j = j + 1;
}
for (i = 0; i < k; i++) {
src_array[low + i] = des_array[i];
}
}
/**
* 2-路归并排序算法，递归实现
*
* @param src_array
* @param low
* @param high
* @param des_array
*/
public static void mergeSort(int src_array[], int low, int high,
int des_array[]) {
int mid;
if (low < high) {
mid = (low + high) / 2;
mergeSort(src_array, low, mid, des_array);
mergeSort(src_array, mid + 1, high, des_array);
Merge(src_array, low, high, des_array);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
int array2[] = new int[array1.length];
mergeSort(array1, 0, array1.length - 1, array2);
System.out.println("\n----------after sort-------------");
for (int ii = 0; ii < array1.length; ii++) {
System.out.print(array1[ii] + " ");
}
System.out.println("\n");
}
}代码解释：
归并排序中一趟归并要多次调用到2-路归并算法，一趟的归并的时间复杂度是O(n)，合并两个已经排好序的表的时间显然是线性的，因为最多进行了n-1次比较，其中n是元素的总数。如果有多个数，即n不为1时，递归的将前半部分数据和后半部分数据各自归并排序，得到排序后的两部分数据，再合并到一起。
算法分析：
该算法是建立在归并操作（也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作）上的一种有效的排序算法。该算法是采用分治法（pide and Conquer）的一个非常典型的应用，它将问题分成一些小的问题然后递归求解，而治的阶段则是将分的阶段解得的各个答案修补到一块；分治是递归非常有力的用法。注意：与快速·排序和堆排序比较，归并排序最大的特点就是，它一种稳定的排序方法。速度仅次于快速排序，一般用于对总体无序，但是各子项相对有序的数列。
复杂度：
时间复杂度为：O(nlogn) ——该算法最好、最坏和平均的时间性能。
空间复杂度为 ：O(n)
比较操作的次数介于(nlogn) / 2和 nlogn - n + 1之间。
赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)
很难用于主存排序（归并排序比较占用内存，主要问题在于合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样的一些附加操作，其结果严重放慢了排序的速度）但是效率很高，主要用于外部排序，对于重要的内部排序应用而言，一般还是选择快速排序。
本软件完全免费，无任何bug。用户可放心使用，网关需单独注册，请联系软件作者。1、关于接口设置：721K 卡易智能点卡接口，易宝支付网银接口。2、关于账户功能：商户信息管理、玩家留言信箱、网关下载、资金管理。3、关于游戏管理：分区管理、添加分区、分组管理、比例模板、补发管理、获取代码。4、关于订单管理：订单查询、渠道管理、结算统计。5、关于数据统计：玩家排名、分区排名、渠道统计。6、程序是 .NE
归并操作的步骤如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
归并排序的步骤如下（假设序列共有n个元素）：
将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕
【相关推荐】
