java递归和非递归的实现

  • 代码如下:

    创新互联是少有的成都网站设计、网站制作、外贸营销网站建设、营销型企业网站、微信小程序、手机APP,开发、制作、设计、外链、推广优化一站式服务网络公司,2013年开创至今,坚持透明化,价格低,无套路经营理念。让网页惊喜每一位访客多年来深受用户好评

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


分享名称:java递归和非递归的实现
文章转载:http://myzitong.com/article/pgppei.html