C Academy · Pelajaran

Isihan Buih dan Penyisipan

Isihan mudah

Pelajaran 1 daripada 413 langkah

Isihan Buih dan Penyisipan ialah pelajaran C Academy percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran C Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Pengisihan Mudah

Pengisihan gelembung dan pengisihan sisipan ialah dua pengisihan perbandingan yang paling mudah. Kedua-duanya ialah O(n kuasa dua) dalam kes terburuk, tetapi mudah difahami dan berguna untuk tatasusunan kecil atau yang hampir diisih.

Cara Pengisihan Gelembung Berfungsi

Pengisihan gelembung berulang kali menelusuri tatasusunan sambil menukar pasangan bersebelahan yang tidak mengikut tertib. Selepas setiap laluan penuh, unsur terbesar yang masih ada bergelembung ke kedudukan akhirnya di hujung.

Menukar Dua Integer

Pembantu pertukaran yang boleh digunakan semula menjadikan kod pengisihan lebih kemas.

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

int main(void) {
    int x = 1, y = 2;
    swap(&x, &y);
    printf("%d %d\n", x, y);
    return 0;
}

Pelaksanaan Pengisihan Gelembung

Gelung bersarang: gelung luar mengira laluan, manakala gelung dalam membandingkan pasangan bersebelahan dan menukarnya. Selepas laluan i, i unsur terakhir telah diisih.

#include <stdio.h>

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    bubble_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Pengoptimuman Keluar Awal

Jika satu laluan penuh tidak melakukan sebarang pertukaran, tatasusunan sudah diisih dan anda boleh berhenti. Ini menjadikan pengisihan gelembung O(n) bagi input yang sudah diisih.

#include <stdio.h>

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
            }
        if (!swapped) break;
    }
}

int main(void) {
    int a[] = {1, 2, 3, 4, 5};
    bubble_sort(a, 5);
    printf("sorted with early exit\n");
    return 0;
}

Cara Pengisihan S 삽ipan Berfungsi

Pengisihan sisipan membina rantau yang diisih pada bahagian hadapan. Bagi setiap unsur baharu, ia mengalih unsur yang lebih besar ke kanan dan meletakkan unsur baharu pada tempatnya, seperti menyusun kad permainan di tangan.

Pelaksanaan Pengisihan S isip

Ambil unsur key = a[i], kemudian alihkan setiap unsur yang lebih besar dalam a[0..i-1] satu slot ke kanan, dan sisipkan key ke dalam ruang kosong itu.

#include <stdio.h>

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

int main(void) {
    int a[] = {5, 2, 9, 1, 3};
    insertion_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Pengisihan S isip pada Data yang Hampir Diisih

Pengisihan sisipan sangat berkesan apabila tatasusunan hampir diisih: setiap unsur hanya bergerak beberapa kedudukan, menghampiri O(n). Inilah sebabnya ia digunakan sebagai langkah akhir dalam pengisihan hibrid.

#include <stdio.h>

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

int main(void) {
    int a[] = {1, 2, 4, 3, 5}; /* one out of place */
    insertion_sort(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Kestabilan

Kedua-dua pengisihan adalah stabil: unsur yang sama mengekalkan susunan relatif asal kerana ia hanya ditukar atau dialih apabila perbandingan lebih besar yang ketat berlaku. Kestabilan penting apabila rekod diisih berdasarkan beberapa kunci.

Perbandingan Kerumitan

Kedua-duanya ialah O(n kuasa dua) secara purata dan dalam kes terburuk, tetapi berbeza dalam amalan:

Gelembung: banyak pertukaran, jarang digunakan dalam kod sebenar
Sisipan: lebih sedikit penulisan, sangat baik untuk tatasusunan kecil atau hampir diisih

Kes terbaik bagi kedua-duanya dengan pengoptimuman ialah O(n).

Mengira Operasi

Mari kita kira perbandingan yang dilakukan oleh pengisihan sisipan pada tatasusunan yang diisih secara terbalik, iaitu kes terburuk.

#include <stdio.h>

int main(void) {
    int a[] = {5, 4, 3, 2, 1};
    int n = 5; long cmp = 0;
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
        a[j+1] = key;
    }
    printf("comparisons = %ld\n", cmp);
    return 0;
}

Semakan Pantas

Uji pemahaman anda tentang pengisihan mudah.

Jawab dalam pelajaran interaktif

Imbas Kembali

Anda telah mempelajari dua pengisihan mudah O(n kuasa dua).

Pengisihan gelembung menukar pasangan bersebelahan pada setiap laluan
Pengisihan sisipan mengalih dan menyisipkan unsur ke bahagian hadapan yang diisih
Kedua-duanya stabil; kedua-duanya mencapai O(n) pada input yang diisih dengan pengoptimuman
Pengisihan sisipan ialah pilihan praktikal yang lebih baik untuk data kecil

Percuma untuk bermula

Pelajari C dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 39
Pelajaran: 144

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Isihan Buih dan Penyisipan” percuma?

Ya — teks penuh “Isihan Buih dan Penyisipan” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus C Academy, tingkat taraf kepada CoddyKit PRO. Kursus C Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Isihan Buih dan Penyisipan”?

Isihan mudah Anda berlatih C Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan C Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran C Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.

Berapa lamakah pelajaran “Isihan Buih dan Penyisipan” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

Isihan Buih dan Penyisipan
Quicksort
Mergesort
Menggunakan qsort

← Kembali ke C Academy