目錄
一、基本思想
二、演算法分析
1、演算法描述
2、過程分析
3、動圖示範
#三、演算法實作
首頁 Java java教程 Java中歸併排序演算法的原理是什麼幾怎麼實現

Java中歸併排序演算法的原理是什麼幾怎麼實現

Apr 19, 2023 pm 05:43 PM
java

    一、基本思想

    歸併排序是建立在歸併操作上的一種有效的排序演算法。此演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合併成一個有序表,稱為2-路歸併。

    二、演算法分析

    1、演算法描述

    把長度為n的輸入序列分成兩個長度為n/2的子序列;對這兩個子序列分別採用歸併排序;將兩個排序好的子序列合併成一個最終的排序序列。

    2、過程分析

    (1)、現在我們將拆分項[1] (指數從0 到0,兩邊都包含) 和[28] 指數從1 到1 ,兩邊都包括) 歸併在一起。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (2)、因為 1 (左拆分) <= 28 (右拆分), 我們將 {rightPart} 複製新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (3)、因為左拆分是空的,我們將 28 (右拆分)複製到新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (4)、我們將新陣列中的元素拷貝回原來的陣列中。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (5)、因為 3 (左拆分) <= 21 (右拆分), 我們將 {rightPart} 複製新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (6)、因為左拆分是空的,我們將 21 (右拆分)複製到新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (7)、現在我們將拆分項[1,28] (指數從0 到1,兩邊都包含) 和[3,21] 指數從2到3 ,兩邊都包括) 歸併在一起。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (8)、因為 1 (左拆分) <= 3 (右拆分), 我們將 {rightPart} 複製新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (9)、因為 28 (左拆分) > 3 (右拆分), 我們將 {rightPart} 複製新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (10)、因為 28 (左拆分) > 21 (右拆分), 我們將 {rightPart} 複製新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (11)、因為右拆分是空的,我們將28 (左拆分) 拷貝進新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (12)、我們將新陣列中的元素拷貝回原來的陣列中。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (13)、現在我們將拆分項[11] (指數從4 到4,兩邊都包含) 和[7] 指數從5 到5 ,兩邊都包括) 歸併在一起。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (14)、因為 11 (左拆分) > 7 (右拆分), 我們將 {rightPart} 複製新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (15)、因為右拆分是空的,我們將11 (左拆分) 拷貝進新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (16)、我們將新陣列中的元素拷貝回原來的陣列中。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (17)、以此類推

    (18)、因為1 (左拆分) <= 6 (右拆分), 我們將{rightPart} 拷貝新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (19)、因為 3 (左拆分) <= 6 (右拆分), 我們將 {rightPart} 複製新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (20)、因為 21 (左拆分) > 6 (右拆分), 我們將 {rightPart} 複製新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (21)、因為 21 (左拆分) > 7 (右拆分), 我們將 {rightPart} 複製新的陣列。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    (22)、以此類推,我們將新數組中的元素拷貝回原來的陣列中。

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    3、動圖示範

    Java中歸併排序演算法的原理是什麼幾怎麼實現

    #三、演算法實作

    package com.algorithm.tenSortingAlgorithm;
    
    import java.util.Arrays;
    
    public class MergeSort {
        private static void mergeSort(int[] arr, int low, int high) {
            if (low < high) { //当子序列中只有一个元素时结束递归
                int mid = (low + high) / 2; //划分子序列
                mergeSort(arr, low, mid); //对左侧子序列进行递归排序
                mergeSort(arr, mid + 1, high); //对右侧子序列进行递归排序
                merge(arr, low, mid, high); //合并
            }
        }
    
        private static void merge(int[] arr, int low, int mid, int high) {
            int[] temp = new int[arr.length]; //辅助数组
            int k = 0, i = low, j = mid + 1; //i左边序列和j右边序列起始索引,k是存放指针
            while (i <= mid && j <= high) {
                if (arr[i] <= arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            //如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
            while (i <= mid) {
                temp[k++] = arr[i++];
            }
            //同上
            while (j <= high) {
                temp[k++] = arr[j++];
            }
            //复制回原数组
            for (int t = 0; t < k; t++) {
                arr[low + t] = temp[t];
            }
        }
    
        public static void main(String[] args) {
            int[] arr = {1,28,3,21,11,7,6,18};
            mergeSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
    }
    登入後複製

    以上是Java中歸併排序演算法的原理是什麼幾怎麼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

    本網站聲明
    本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

    熱AI工具

    Undresser.AI Undress

    Undresser.AI Undress

    人工智慧驅動的應用程序,用於創建逼真的裸體照片

    AI Clothes Remover

    AI Clothes Remover

    用於從照片中去除衣服的線上人工智慧工具。

    Undress AI Tool

    Undress AI Tool

    免費脫衣圖片

    Clothoff.io

    Clothoff.io

    AI脫衣器

    Video Face Swap

    Video Face Swap

    使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

    熱工具

    記事本++7.3.1

    記事本++7.3.1

    好用且免費的程式碼編輯器

    SublimeText3漢化版

    SublimeText3漢化版

    中文版,非常好用

    禪工作室 13.0.1

    禪工作室 13.0.1

    強大的PHP整合開發環境

    Dreamweaver CS6

    Dreamweaver CS6

    視覺化網頁開發工具

    SublimeText3 Mac版

    SublimeText3 Mac版

    神級程式碼編輯軟體(SublimeText3)

    熱門話題

    Java教學
    1657
    14
    CakePHP 教程
    1415
    52
    Laravel 教程
    1309
    25
    PHP教程
    1257
    29
    C# 教程
    1230
    24
    突破或從Java 8流返回? 突破或從Java 8流返回? Feb 07, 2025 pm 12:09 PM

    Java 8引入了Stream API,提供了一種強大且表達力豐富的處理數據集合的方式。然而,使用Stream時,一個常見問題是:如何從forEach操作中中斷或返回? 傳統循環允許提前中斷或返回,但Stream的forEach方法並不直接支持這種方式。本文將解釋原因,並探討在Stream處理系統中實現提前終止的替代方法。 延伸閱讀: Java Stream API改進 理解Stream forEach forEach方法是一個終端操作,它對Stream中的每個元素執行一個操作。它的設計意圖是處

    PHP:網絡開發的關鍵語言 PHP:網絡開發的關鍵語言 Apr 13, 2025 am 12:08 AM

    PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

    PHP與Python:了解差異 PHP與Python:了解差異 Apr 11, 2025 am 12:15 AM

    PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

    PHP與其他語言:比較 PHP與其他語言:比較 Apr 13, 2025 am 12:19 AM

    PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

    PHP與Python:核心功能 PHP與Python:核心功能 Apr 13, 2025 am 12:16 AM

    PHP和Python各有優勢,適合不同場景。 1.PHP適用於web開發,提供內置web服務器和豐富函數庫。 2.Python適合數據科學和機器學習,語法簡潔且有強大標準庫。選擇時應根據項目需求決定。

    Java程序查找膠囊的體積 Java程序查找膠囊的體積 Feb 07, 2025 am 11:37 AM

    膠囊是一種三維幾何圖形,由一個圓柱體和兩端各一個半球體組成。膠囊的體積可以通過將圓柱體的體積和兩端半球體的體積相加來計算。本教程將討論如何使用不同的方法在Java中計算給定膠囊的體積。 膠囊體積公式 膠囊體積的公式如下: 膠囊體積 = 圓柱體體積 兩個半球體體積 其中, r: 半球體的半徑。 h: 圓柱體的高度(不包括半球體)。 例子 1 輸入 半徑 = 5 單位 高度 = 10 單位 輸出 體積 = 1570.8 立方單位 解釋 使用公式計算體積: 體積 = π × r2 × h (4

    PHP的影響:網絡開發及以後 PHP的影響:網絡開發及以後 Apr 18, 2025 am 12:10 AM

    PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

    PHP:許多網站的基礎 PHP:許多網站的基礎 Apr 13, 2025 am 12:07 AM

    PHP成為許多網站首選技術棧的原因包括其易用性、強大社區支持和廣泛應用。 1)易於學習和使用,適合初學者。 2)擁有龐大的開發者社區,資源豐富。 3)廣泛應用於WordPress、Drupal等平台。 4)與Web服務器緊密集成,簡化開發部署。

    See all articles