Cara menggunakan algoritma isihan sisipan dalam C++

Menggunakan algoritma isihan sisipan dalam C++ untuk melaksanakan pengisihan tatasusunan

Isihan sisipan ialah algoritma pengisihan yang mudah tetapi berkesan yang akan mengisih unsur-unsur dimasukkan ke dalam senarai disusun satu persatu, dan akhirnya senarai tersusun diperolehi. Artikel ini akan memperkenalkan cara menggunakan bahasa pengaturcaraan C++ untuk melaksanakan algoritma isihan sisipan dan memberikan contoh kod khusus.

Idea algoritma:
Idea asas isihan sisipan ialah membahagikan tatasusunan kepada selang yang diisih dan selang yang tidak diisih. Setiap kali elemen dipilih daripada julat yang tidak diisih dan dimasukkan ke dalam kedudukan julat yang diisih yang sesuai sehingga julat yang tidak diisih kosong.

Langkah khusus:

1. Lintas tatasusunan dan masukkan elemen selang tidak diisih ke dalam selang diisih mengikut turutan.
2. Untuk setiap elemen dalam selang yang tidak diisih, bandingkan dengan elemen dalam selang yang diisih untuk mencari kedudukan sisipan.
3. Masukkan elemen ke dalam kedudukan yang sesuai bagi selang yang diisih, dan gerakkan elemen selang yang diisih satu kedudukan ke belakang.

Contoh kod:
Berikut ialah contoh kod yang menggunakan bahasa pengaturcaraan C++ untuk melaksanakan algoritma isihan sisipan:

#include <iostream>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = { 5, 2, 4, 6, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "原始数组：";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    insertionSort(arr, n);

    std::cout << "排序后的数组：";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Dalam perkara di atas kod, kami mentakrifkan Fungsi bernama insertionSort的函数来实现插入排序。在main函数中，我们定义了一个待排序的数组并调用insertionSort digunakan untuk mengisih. Akhir sekali, kami mengeluarkan hasil yang diisih ke konsol.

Hasil berjalan:
Susun atur asal: 5 2 4 6 1 3
Susunurutan: 1 2 3 4 5 6

#🎜🎜🎜🎜🎜🎜🎜🎜 #Melalui kod contoh di atas, kita boleh melihat cara menggunakan algoritma isihan sisipan dalam C++ untuk mengisih tatasusunan. Walaupun isihan sisipan adalah mudah, kerumitan masanya ialah O(n^2), dan kecekapan pengisihan untuk data berskala besar adalah rendah. Dalam aplikasi praktikal, jika sejumlah besar data perlu diisih, adalah disyorkan untuk menggunakan algoritma pengisihan yang lebih cekap, seperti isihan cepat atau isihan gabungan.

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