本篇內(nèi)容主要講解“什么是Java歸并排序”,感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“什么是Java歸并排序”吧!
讓客戶滿意是我們工作的目標(biāo),不斷超越客戶的期望值來自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡(jiǎn)單的方式提供給客戶,將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴,公司提供的服務(wù)項(xiàng)目有:空間域名、網(wǎng)絡(luò)空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、新民網(wǎng)站維護(hù)、網(wǎng)站推廣。
歸并排序(merge-sort)是利用歸并的思想實(shí)現(xiàn)的排序方法,該算法采用經(jīng)典的分治(divide-and-conquer)策略(分治法將問題分(divide)成一些小的問題然后遞歸求解,而治(conquer)的階段則將分的階段得到的答案"修補(bǔ)"在一起,即分而治之).
說明:可以看到這種結(jié)構(gòu)很像一顆完全二叉樹,本文的歸并排序我們采用遞歸去實(shí)現(xiàn)(也可以采用迭代的方式去實(shí)現(xiàn)).分階段可以理解為就是遞歸拆分子序列的過程.
再來看看治階段,我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列,比如下圖的最有一次合并,要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列,合并為最終序列[1,2,3,4,5,6,7,8],來看下實(shí)現(xiàn)步驟.
package com.structures.sort; blic class MergeSort { public static void main(String[] args) { int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random() * 8000000); } int[] temp = new int[arr.length]; long start = System.currentTimeMillis(); mergeSort(arr,0,arr.length-1,temp); long end = System.currentTimeMillis(); System.out.println("耗時(shí):" + ((end - start)) + "ms"); /* 耗時(shí):15ms */ } //分+合 public static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = (left + right) / 2; //向左遞歸進(jìn)行分解 mergeSort(arr, left, mid, temp); //向右遞歸進(jìn)行分解 mergeSort(arr, mid + 1, right, temp); //合并 merge(arr, left, mid, right, temp); } } /** * 合并 * @param arr 已排序的原始數(shù)組 * @param left 左邊有序序列的初始索引 * @param mid 中間索引 * @param right 右邊索引 * @param temp 做中轉(zhuǎn)數(shù)組 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left;//初始化i,左邊有序序列的初始索引 int j = mid + 1;//初始化j,右邊有序序列的初始索引 int t = 0;//指向temp數(shù)組的當(dāng)前索引 //(一) //先把左右兩邊(有序)的數(shù)據(jù)按照規(guī)則填充到temp數(shù)組 //直到左右兩邊的有序序列,有一邊處理完畢為止,即全部填充到temp數(shù)組 while (i <= mid && j <= right) { //如果左邊的有序序列小于等于右邊的有序序列的當(dāng)前元素 //即將左邊的當(dāng)前元素拷貝到temp數(shù)組 //然后t++,i++后移 if (arr[i] <= arr[j]) { temp[t] = arr[i]; t += 1; i += 1; } else {//反之,將右邊有序序列的當(dāng)前元素,填充到temp數(shù)組 temp[t] = arr[j]; t += 1; j += 1; } } //(二) //把有剩余數(shù)據(jù)的一邊的數(shù)據(jù)依次填充到temp while (i <= mid) {//左邊的還有剩余,填充到temp數(shù)組 temp[t] = arr[i]; t += 1; i += 1; } while (j <= right) { temp[t] = arr[j]; t += 1; j += 1; } //(三) //將temp數(shù)組的元素拷貝到arr //注意并不是每次都拷貝所有 //第一次合并leftTemp = 0,right = 1,第二次合并leftTemp = 2,right = 3,第三次合并leftTemp = 0,right = 3... t = 0; int leftTemp = left; while (leftTemp <= right) { arr[leftTemp] = temp[t]; leftTemp += 1; t += 1; } }
到此,相信大家對(duì)“什么是Java歸并排序”有了更深的了解,不妨來實(shí)際操作一番吧!這里是創(chuàng)新互聯(lián)網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
網(wǎng)站名稱:什么是Java歸并排序
文章源于:http://muchs.cn/article22/ihdccc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供網(wǎng)站收錄、App開發(fā)、網(wǎng)站改版、品牌網(wǎng)站制作、ChatGPT、網(wǎng)站維護(hù)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)