温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

java递归和非递归的实现

发布时间:2020-05-29 14:51:07 来源:亿速云 阅读:235 作者:鸽子 栏目:编程语言
  • 代码如下:

    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)
  • 稳定性:稳定

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI