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