新浪微博 登陆  注册   设为首页 加入收藏

学PHP >> 设计模式与算法 >> 归并排序算法

归并排序算法

查看次数24133 发表时间2013-08-04 15:42:47

归并排序的时间复杂度是:nlogn主要是用到二路归并排序,也就是把两个有序集合合并为一个有序集合.下面是我写的一个递归二路归并排序的算法:代码片段(1)[代码] [Java]代码view source...

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

代码片段(1)

[代码] [Java]代码

001 package algorithm;
002  
003 public class MergeSort {
004  // private static long sum = 0;
005  
006  /**
007   * <pre>
008   * 二路归并
009   * 原理:将两个有序表合并和一个有序表
010   * </pre>
011   *
012   * @param a
013   * @param s
014   *            第一个有序表的起始下标
015   * @param m
016   *            第二个有序表的起始下标
017   * @param t
018   *            第二个有序表的结束小标
019   *
020   */
021  private static void merge(int[] a, int s, int m, int t) {
022   int[] tmp = new int[t - s + 1];
023  
024   int i = s, j = m, k = 0;
025   while (i < m && j <= t) {
026    if (a[i] <= a[j]) {
027     tmp[k] = a[i];
028     k++;
029     i++;
030    else {
031     tmp[k] = a[j];
032     // sum += (j - i) - (j - m);
033     j++;
034     k++;
035    }
036   }
037   while (i < m) {
038    tmp[k] = a[i];
039    i++;
040    k++;
041   }
042  
043   while (j <= t) {
044    tmp[k] = a[j];
045    j++;
046    k++;
047   }
048  
049   System.arraycopy(tmp, 0, a, s, tmp.length);
050  }
051  
052  /**
053   *
054   * @param a
055   * @param s
056   * @param len
057   *            每次归并的有序集合的长度
058   */
059  public static void mergeSort(int[] a, int s, int len) {
060  
061   int size = a.length;
062   int mid = size / (len << 1);
063   int c = size & ((len<<1) - 1);
064  
065   // -------归并到只剩一个有序集合的时候结束算法-------//
066   if (mid == 0)
067    return;
068  
069   // ------进行一趟归并排序-------//
070   for (int i = 0; i < mid; ++i) {
071    s = i * 2 * len;
072    merge(a, s, s + len, (len << 1) + s - 1);
073   }
074  
075   // -------将剩下的数和倒数一个有序集合归并-------//
076   if (c != 0)
077    merge(a, size - c - 2 * len, size - c, size - 1);
078   //
079   // for (int i = 0; i < a.length; ++i) {
080   // System.out.print(a[i] + " ");
081   // }
082   // System.out.println();
083  
084   // -------递归执行下一趟归并排序------//
085   mergeSort(a, 02 * len);
086  }
087  
088  public static void main(String[] args) {
089   // merge(new int[] { 4, 3, 6, 1, 2, 5 }, 0, 3, 5);
090  
091   int[] a = new int[] { 436125};
092   mergeSort(a, 01);
093  
094   for (int i = 0; i < a.length; ++i) {
095    System.out.print(a[i] + " ");
096   }
097  
098   // System.out.println("/n" + sum);
099  }
100  
101 }

(转发请注明转自:学PHP)    


  相关推荐



1楼 瀛?HPER说: 2014-02-03 07:54:57
!S!WCRTESTTEXTAREA000000!E!
2楼 瀛?HPER说: 2014-02-04 20:08:52
!S!WCRTESTTEXTAREA000000!E!

  发表评论
昵称:
(不超过20个字符或10个汉字)
内容: