• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

java归并排序算法代码

JAVA相关 水墨上仙 1598次浏览

归并排序的时间复杂度是:nlogn
主要是用到二路归并排序,也就是把两个有序集合合并为一个有序集合.
下面是我写的一个递归二路归并排序的算法:

package algorithm;
public class MergeSort {
 // private static long sum = 0;
 /**
  * <pre>
  * 二路归并
  * 原理:将两个有序表合并和一个有序表
  * 

*
* @param a
* @param s
* 第一个有序表的起始下标
* @param m
* 第二个有序表的起始下标
* @param t
* 第二个有序表的结束小标
*
*/
private static void merge(int[] a, int s, int m, int t) {
int[] tmp = new int[t – s + 1];
int i = s, j = m, k = 0;
while (i < m && j <= t) { if (a[i] <= a[j]) { tmp[k] = a[i]; k++; i++; } else { tmp[k] = a[j]; // sum += (j - i) - (j - m); j++; k++; } } while (i < m) { tmp[k] = a[i]; i++; k++; } while (j <= t) { tmp[k] = a[j]; j++; k++; } System.arraycopy(tmp, 0, a, s, tmp.length); } /** * * @param a * @param s * @param len * 每次归并的有序集合的长度 */ public static void mergeSort(int[] a, int s, int len) { int size = a.length; int mid = size / (len << 1); int c = size & ((len<<1) - 1); // -------归并到只剩一个有序集合的时候结束算法-------// if (mid == 0) return; // ------进行一趟归并排序-------// for (int i = 0; i < mid; ++i) { s = i * 2 * len; merge(a, s, s + len, (len << 1) + s - 1); } // -------将剩下的数和倒数一个有序集合归并-------// if (c != 0) merge(a, size - c - 2 * len, size - c, size - 1); // // for (int i = 0; i < a.length; ++i) { // System.out.print(a[i] + " "); // } // System.out.println(); // -------递归执行下一趟归并排序------// mergeSort(a, 0, 2 * len); } public static void main(String[] args) { // merge(new int[] { 4, 3, 6, 1, 2, 5 }, 0, 3, 5); int[] a = new int[] { 4, 3, 6, 1, 2, 5}; mergeSort(a, 0, 1); for (int i = 0; i < a.length; ++i) { System.out.print(a[i] + " "); } // System.out.println("/n" + sum); } }


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明java归并排序算法代码
喜欢 (0)
加载中……