java递归和非递归的实现-创新互联

  • 代码如下:

    创新互联建站是一家专业提供罗城企业网站建设,专注与成都网站设计、网站建设、外贸网站建设H5开发、小程序制作等业务。10年已为罗城众多企业、政府机构等服务。创新互联专业网络公司优惠进行中。
    private void merge(int[] array, int left, int mid, int right) {
           int i = left;
           int j = mid;
           int length = right - left;
           int[] extra = new int[length];
           int k = 0;
    
           while(i < mid && j < right) {
               if(array[i] <= array[j]) {
                   extra[k++] = array[i++];
               } else {
                   extra[k++] = array[j++];
               }
           }
    
           while (i < mid) {
               extra[k++] = array[i++];
           }
           while (j < right) {
               extra[k++] = array[j++];
           }
    
           // 从 extra 搬移回 array
           for (int t = 0; t < length; t++) {
           // 需要搬移回原位置,从 low 开始
               array[left + t] = extra[t];
           }
       }
  • 递归实现操作:

    public void mergeSort(int[] array) {
       mergeSortInternal(array, 0, array.length);
    }
    
    private void mergeSortInternal(int[] array, int left, int right) {
       if(left >= right - 1)
         return;
    
       int mid = (left + right) >>> 1;
       mergeSortInternal(array, left, mid);
       mergeSortInternal(array, mid, right);
    
       merge(array, left, mid, right);
    }
  • 非递归实现操作
    public void mergeSort(int[] array) {
           for (int i = 1; i < array.length; i = i * 2) {
               for (int j = 0; j < array.length; j = j + 2 * i) {
                   int low = j;
                   int mid = j + i;
                   if (mid >= array.length) {
                       continue;
                   }
                   int high = mid + i;
                   if (high > array.length) {
                       high = array.length;
                   }
                   merge(array, low, mid, high);
               }
           }
       }
性能分析
  • 时间复杂度:O(N * log(N))
  • 空间复杂度:O(N)
  • 稳定性:稳定

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


当前标题:java递归和非递归的实现-创新互联
文章位置:http://cdiso.cn/article/doioch.html

其他资讯