Cara menggunakan algoritma isihan gabungan dalam C++

Cara menggunakan algoritma isihan gabungan dalam C++

Isih gabung ialah algoritma isihan klasik Ia menggunakan idea kaedah bahagi dan takluk untuk membahagikan urutan yang akan diisih kepada dua urutan, menyusunnya. secara berasingan, dan kemudian menggabungkan dua Susunan tertib digabungkan menjadi urutan tertib. Di bawah, kami akan memperkenalkan cara menggunakan bahasa C++ untuk melaksanakan algoritma isihan gabungan dan memberikan contoh kod khusus.

1. Idea algoritma

Idea teras isihan gabungan adalah untuk membahagikan urutan untuk diisih kepada berbilang jujukan, kemudian melakukan pengisihan panggilan rekursif pada jujukan, dan akhirnya menggabungkan jujukan yang diisih.

Langkah-langkah khusus adalah seperti berikut:
1) Jika panjang jujukan ialah 1, bermakna ia sudah dipesan, dan kembali terus
2) Bahagikan jujukan kepada dua jujukan sama banyak, dan lakukan pengasingan panggilan rekursif pada dua jujukan
3) Gabungkan kedua-dua urutan dengan Urutan ordinal digabungkan menjadi urutan tertib

2. Contoh kod

Berikut ialah contoh kod menggunakan bahasa C++ untuk melaksanakan algoritma isihan gabungan:

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序子序列
void merge(vector<int>& arr, int left, int mid, int right) {
    int i = left;    // 左子序列起始索引
    int j = mid + 1; // 右子序列起始索引
    int k = 0;       // 临时数组起始索引
    vector<int> temp(right - left + 1); // 临时数组

    // 比较两个子序列的元素，将较小的元素放入临时数组中
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 将剩余的元素复制到临时数组中
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 将临时数组的元素复制回原数组
    for (int m = 0; m < k; ++m) {
        arr[left + m] = temp[m];
    }
}

// 归并排序递归函数
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        // 递归调用排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并两个有序子序列
        merge(arr, left, mid, right);
    }
}

// 归并排序函数
void mergeSort(vector<int>& arr) {
    mergeSort(arr, 0, arr.size() - 1);
}

int main() {
    vector<int> arr = {4, 6, 2, 8, 9, 1, 5, 3, 7};

    // 调用归并排序函数
    mergeSort(arr);

    // 输出排序结果
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Kod di atas ialah contoh menggunakan C++ untuk melaksanakan algoritma isihan gabungan Pertama, a Fungsi merge函数，用来合并两个有序子序列。然后定义了mergeSort函数，用来进行归并排序的递归调用。最后，在main函数中调用mergeSort mengisih urutan untuk diisih dan mengeluarkan hasil yang diisih.

3. Ringkasan

Algoritma isihan gabungan ialah algoritma isihan yang cekap dan stabil dengan kerumitan masa O(nlogn). Melalui panggilan rekursif dan operasi cantum, isihan cantum boleh membahagikan urutan untuk diisih ke dalam blok kecil untuk mengisih, dan kemudian menggabungkan urutan tersusun ke dalam urutan tersusun. Melalui contoh kod khusus yang dilaksanakan dalam bahasa C++, kita boleh lebih memahami dan menguasai proses pelaksanaan algoritma isihan gabungan.

Atas ialah kandungan terperinci Cara menggunakan algoritma isihan gabungan dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!