App下載

歸并排序:將分而治之融入排序的藝術(shù)

穩(wěn)走感情路 2024-02-20 11:49:39 瀏覽數(shù) (2876)
反饋

在計(jì)算機(jī)科學(xué)中,排序算法是一項(xiàng)基礎(chǔ)而重要的任務(wù)。歸并排序以其高效性和穩(wěn)定性而聞名于世。它通過(guò)將待排序數(shù)組一分為二,分別對(duì)兩個(gè)子數(shù)組進(jìn)行排序,再將排好序的子數(shù)組合并,最終得到完全有序的數(shù)組。本文將深入探討歸并排序的工作原理,以及它在實(shí)際應(yīng)用中的優(yōu)勢(shì)。

歸并排序原理

  • 分治策略:歸并排序采用分治的思想。它將待排序數(shù)組遞歸地分成兩個(gè)子數(shù)組,直到每個(gè)子數(shù)組只包含一個(gè)元素,然后對(duì)這些子數(shù)組進(jìn)行排序。
  • 合并操作:在子數(shù)組排序完成后,歸并排序?qū)⑦@些有序的子數(shù)組合并成一個(gè)有序的數(shù)組。合并操作是歸并排序的核心步驟。

Merge-Sort-in-Java-2-(1)-660


歸并排序步驟

  1. 分割數(shù)組將待排序數(shù)組遞歸地分割成兩個(gè)子數(shù)組,直到每個(gè)子數(shù)組只包含一個(gè)元素。
  2. 排序子數(shù)組對(duì)每個(gè)子數(shù)組進(jìn)行排序??梢允褂眠f歸繼續(xù)拆分子數(shù)組,或者使用其他排序算法如插入排序來(lái)處理較小的子數(shù)組。
  3. 合并子數(shù)組合并排好序的子數(shù)組,得到一個(gè)完全有序的數(shù)組。合并操作需要?jiǎng)?chuàng)建一個(gè)臨時(shí)數(shù)組,用于存儲(chǔ)合并后的結(jié)果。
  4. 重復(fù)合并重復(fù)步驟三,直至所有子數(shù)組都合并為一個(gè)有序的數(shù)組。

Merge-sort-example-300px

示例代碼

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {9, 5, 1, 3, 10, 8, 2, 4, 7, 6};
     
        mergeSort(arr, 0, arr.length - 1);
        
        System.out.println("排序后數(shù)組: " + Arrays.toString(arr));
    }
    
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            
            mergeSort(arr, left, mid); // 對(duì)左半部分進(jìn)行歸并排序
            mergeSort(arr, mid + 1, right); // 對(duì)右半部分進(jìn)行歸并排序
            
            merge(arr, left, mid, right); // 合并左右兩部分
        }
    }
    
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        int[] L = new int[n1];
        int[] R = new int[n2];
        
        // 將數(shù)據(jù)復(fù)制到臨時(shí)數(shù)組 L 和 R
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }
        
        // 合并臨時(shí)數(shù)組 L 和 R 到 arr
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        
        // 將剩余的元素復(fù)制到 arr
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

時(shí)間復(fù)雜度和穩(wěn)定性

時(shí)間復(fù)雜度:歸并排序的時(shí)間復(fù)雜度為O(nlogn),其中n是待排序數(shù)組的長(zhǎng)度。這是因?yàn)樵诿恳粚舆f歸中,需要O(n)的時(shí)間進(jìn)行合并操作,而遞歸的層數(shù)是O(logn)。

穩(wěn)定性:歸并排序是一種穩(wěn)定的排序算法,即具有相同值的元素在排序后的相對(duì)順序保持不變。

應(yīng)用場(chǎng)景

  • 大規(guī)模數(shù)據(jù)排序:歸并排序適用于大規(guī)模數(shù)據(jù)的排序,因?yàn)樗臅r(shí)間復(fù)雜度相對(duì)穩(wěn)定,不會(huì)受到數(shù)據(jù)分布的影響。
  • 外部排序:歸并排序適用于需要在外部存儲(chǔ)器上進(jìn)行排序的情況,因?yàn)樗梢杂行У乩么疟P或磁帶等外部存儲(chǔ)設(shè)備。
  • 排序穩(wěn)定性要求高:對(duì)于需要保持相同值元素相對(duì)順序的排序任務(wù),歸并排序是一個(gè)理想的選擇。

總結(jié)

歸并排序是一種高效、穩(wěn)定的排序算法,通過(guò)分治和合并的思想將排序問(wèn)題劃分為較小的子問(wèn)題,并且能夠保證排序的穩(wěn)定性。它的時(shí)間復(fù)雜度為O(nlogn),適用于大規(guī)模數(shù)據(jù)的排序和需要保持排序穩(wěn)定性的任務(wù)。歸并排序在計(jì)算機(jī)科學(xué)領(lǐng)域有廣泛的應(yīng)用,是排序算法中的重要一員。


0 人點(diǎn)贊