搜尋
首頁後端開發php教程排序演算法—歸併排序【附代碼】

排序演算法—歸併排序【附代碼】

Aug 22, 2019 pm 05:06 PM
排序演算法

排序演算法—歸併排序【附代碼】

什麼是歸併排序?

  歸併排序簡單來講,就是將兩個有序的序列整合到一起。

推薦教學:PHP影片教學

#如何將兩個有順序的序列整合在一起呢?

  那麼我們假設,現在有 M={m1 ,m2,m3,....,mx}序列和 N = {n1,n2,n3,...., ny}序列,這兩個序列已經是有序的序列,首先創建一個空序列 K = {},那麼接著將 m1 和 n1 進行比較,加入 m1 

既然歸併排序是整合有序序列,那麼豈不是不能排序無序序列,這條件也太苛刻了點吧?

  歸併排序是建立在分治法的基礎上進行操作的,也就是可以將一個完全無序的序列進行無線分割以達到有序序列,例如:現在有M={m1 ,m2,m3,....,mx},M序列是完全無序的序列,那麼此時可以將 M 序列分成若干個小序列-{m1,m2},{m3,m4 }....{mx-1,mx};此時這些序列就是有序的,那麼就可以透過歸併操作進行排序,所以歸併排序也可以排序無序序列,且速度僅次於快速排序,屬於穩定排序。

如何分割序列?

  上個問題已經提過,歸併排序是建立在分治的基礎上進行操作的,其中分治的體現就體現在分割序列上,比如:現在有M ={m1 ,m2,m3,....,mx},第一次分割:M1 = {m1,m2,...,m(x 1)/2},M2 = {m(x 1)/ 2 1,m(x 1)/2 2,...,mx},第一次分割之後得到 M1 和 M2 序列,然後再分割 M1 和 M2 ,分割若干次之後得到 x/2 x%2 個序列,然後再逐一進行歸併操作。

此演算法特定步驟:

  1、規定首指標 left 與mid(left指向序列1的首元素,right 指向序列2的首元素)

  2、比較 left 和 mid 的大小,將小的元素放入新建的空間中

  3、重複步驟2,直到其中一個序列遍歷完畢

  4、將剩餘的未加入新空間中的元素直接複製貼上進新空間

該演算法的核心步驟:

  1、使用分治法(遞歸)分割序列

  2、比較 left 和 mid 的大小, 將小的元素的添加進入新建空間

敘述完畢,貼上程式碼:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 排序__归并排序
{
    class 归并
    {

        public static int[] arr = { 6, 202, 301, 100, 38, 8, 1 ,-1,1000};
        static void Main(string[] args)
        {
            Sort(arr, 0, arr.Length -1);
            foreach (var item in arr)
            {
                Console.Write(item + "  ");
            }
            Console.ReadKey();
        }

        public static void Sort(int []a,int left,int right)
        {
            if (left >= right) return;
            else
            {
                int mid = (left + right) / 2;                //@1
                Sort(a, left, mid);
                Sort(a, mid + 1, right);
                MergeSort(a, left, mid, right);
            }
        }

        public static void MergeSort(int []a,int left,int mid,int right)
        {
            int[] Arr = new int[right - left + 1];
            int l = left, m = mid +1 , k = 0;           //@2
            while ( m <= right && l <= mid )          //@3
            {
                if (a[l] > a[m]) Arr[k++] = a[m++];
                else Arr[k++] = a[l++];
            }
            while (m < right +1)                           //@4
            {
                Arr[k++] = a[m++];
            }
            while (l < mid +1 )  Arr[k++] = a[l++];        //@4
            for (k = 0, l = left; l < right + 1; k++, l++) a[l] = Arr[k];
        }
    }
}

程式碼解讀:

##  @1 :Sort()函數完成了序列的分割,每一次遞迴都會將序列分成兩半,直到無法分隔為止。

  @2 :l 代表序列1的首元素,m 代表序列2的首元素,k代表新建數組Arr的已有元素個數

  @3 :序列1的首元素和序列2的首元素進行比較,將小的放入 Arr 中,且序列遊標後移,直到其中一個序列的元素遍比較完畢

  @4 :在序列1 和序列2的比較過程中,可能出現序列1已經全部加入了 Arr 中,但是序列2還沒有,則將剩餘的未比較的元素直接複製進入 Arr 中

##總結:

  以上程式碼並不是真正意義上的分割數組,只是做了一個邏輯分割,沒有像其他程式碼一樣將分割後的數組填入一個新的數組,那樣做的話會對速度和記憶體產生一點影響,雖然微乎其微,但總歸是沒這麼好的,在歸併操作上,需要注意的是參數不要越界(我當時就想了很久為什麼 @2 上面的m 要等於 mid 1 而不是 mid ,其實道理很簡單,因為mid是屬於左序列,從 mid 1 開始才屬於右序列,將m = mid 1  改成 m = mid 不是不行,只是後面的程式碼也需要改,但是沒有必要多做一次無用比較,這個問題我當時真是想了半天...),其實只要理清楚其中的邏輯關係,這樣程式碼就能做到信手拈來。

以上是排序演算法—歸併排序【附代碼】的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文轉載於:博客园。如有侵權,請聯絡admin@php.cn刪除
哪些常見問題會導致PHP會話失敗?哪些常見問題會導致PHP會話失敗?Apr 25, 2025 am 12:16 AM

PHPSession失效的原因包括配置錯誤、Cookie問題和Session過期。 1.配置錯誤:檢查並設置正確的session.save_path。 2.Cookie問題:確保Cookie設置正確。 3.Session過期:調整session.gc_maxlifetime值以延長會話時間。

您如何在PHP中調試與會話相關的問題?您如何在PHP中調試與會話相關的問題?Apr 25, 2025 am 12:12 AM

在PHP中調試會話問題的方法包括:1.檢查會話是否正確啟動;2.驗證會話ID的傳遞;3.檢查會話數據的存儲和讀取;4.查看服務器配置。通過輸出會話ID和數據、查看會話文件內容等方法,可以有效診斷和解決會話相關的問題。

如果session_start()被多次調用會發生什麼?如果session_start()被多次調用會發生什麼?Apr 25, 2025 am 12:06 AM

多次調用session_start()會導致警告信息和可能的數據覆蓋。 1)PHP會發出警告,提示session已啟動。 2)可能導致session數據意外覆蓋。 3)使用session_status()檢查session狀態,避免重複調用。

您如何在PHP中配置會話壽命?您如何在PHP中配置會話壽命?Apr 25, 2025 am 12:05 AM

在PHP中配置會話生命週期可以通過設置session.gc_maxlifetime和session.cookie_lifetime來實現。 1)session.gc_maxlifetime控制服務器端會話數據的存活時間,2)session.cookie_lifetime控制客戶端cookie的生命週期,設置為0時cookie在瀏覽器關閉時過期。

使用數據庫存儲會話的優點是什麼?使用數據庫存儲會話的優點是什麼?Apr 24, 2025 am 12:16 AM

使用數據庫存儲會話的主要優勢包括持久性、可擴展性和安全性。 1.持久性:即使服務器重啟,會話數據也能保持不變。 2.可擴展性:適用於分佈式系統,確保會話數據在多服務器間同步。 3.安全性:數據庫提供加密存儲,保護敏感信息。

您如何在PHP中實現自定義會話處理?您如何在PHP中實現自定義會話處理?Apr 24, 2025 am 12:16 AM

在PHP中實現自定義會話處理可以通過實現SessionHandlerInterface接口來完成。具體步驟包括:1)創建實現SessionHandlerInterface的類,如CustomSessionHandler;2)重寫接口中的方法(如open,close,read,write,destroy,gc)來定義會話數據的生命週期和存儲方式;3)在PHP腳本中註冊自定義會話處理器並啟動會話。這樣可以將數據存儲在MySQL、Redis等介質中,提升性能、安全性和可擴展性。

什麼是會話ID?什麼是會話ID?Apr 24, 2025 am 12:13 AM

SessionID是網絡應用程序中用來跟踪用戶會話狀態的機制。 1.它是一個隨機生成的字符串,用於在用戶與服務器之間的多次交互中保持用戶的身份信息。 2.服務器生成並通過cookie或URL參數發送給客戶端,幫助在用戶的多次請求中識別和關聯這些請求。 3.生成通常使用隨機算法保證唯一性和不可預測性。 4.在實際開發中,可以使用內存數據庫如Redis來存儲session數據,提升性能和安全性。

您如何在無狀態環境(例如API)中處理會議?您如何在無狀態環境(例如API)中處理會議?Apr 24, 2025 am 12:12 AM

在無狀態環境如API中管理會話可以通過使用JWT或cookies來實現。 1.JWT適合無狀態和可擴展性,但大數據時體積大。 2.Cookies更傳統且易實現,但需謹慎配置以確保安全性。

See all articles

熱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

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

熱工具

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

SublimeText3 Mac版

SublimeText3 Mac版

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

記事本++7.3.1

記事本++7.3.1

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

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器