Pengisihan dan Pembahagian: sort, stable_partition
Isih dan bahagikan bekas dengan std::sort dan std::stable_partition.
Pengisihan dan Pembahagian: sort, stable_partition ialah pelajaran C++ Academy percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 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.
std::sort
Algoritma pengisihan serba guna. O(N log N) secara purata. Beroperasi pada tempatnya. Tidak dijamin stabil.
#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascendingPembanding Tersuai
Hantar pembanding (lambda atau objek fungsi) untuk mengisih berdasarkan kriteria lain.
std::sort(v.begin(), v.end(),
[](int a, int b) { return a > b; }); // descendingMengisih Jenis Tersuai
Sediakan pembanding yang membandingkan ahli tertentu, atau takrifkan operator< pada jenis tersebut.
struct Person { std::string name; int age; };
std::vector<Person> people;
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) { return a.age < b.age; });std::stable_sort
Sama seperti sort, tetapi mengekalkan susunan relatif elemen yang sama. Sedikit lebih perlahan (biasanya memerlukan memori tambahan O(N log^2 N)).
std::partial_sort
Letakkan k elemen terkecil di hadapan dalam susunan terisih. Elemen selebihnya berada dalam susunan yang tidak ditentukan. Lebih pantas daripada pengisihan penuh apabila anda hanya memerlukan k elemen teratas.
std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// first 3 elements are the smallest, sortedstd::nth_element
Partisikan julat supaya elemen pada kedudukan nth berada pada kedudukan yang sama seperti dalam julat yang diisih sepenuhnya. Semua elemen sebelumnya adalah ≤ elemen nth; semua elemen selepasnya adalah ≥. O(N) secara purata.
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest elementstd::is_sorted
Semak sama ada julat sudah diisih.
if (std::is_sorted(v.begin(), v.end())) {
std::cout << "already sorted";
}std::partition
Susun semula julat supaya elemen yang memenuhi predikat berada di hadapan. Mengembalikan lelar ke elemen pertama yang tidak memenuhi predikat. Tidak stabil.
std::vector<int> v = {1, 2, 3, 4, 5};
auto pivot = std::partition(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
// even numbers come first, then oddstd::stable_partition
Seperti partition, tetapi mengekalkan susunan relatif dalam setiap kumpulan.
Mengisih Berdasarkan Berbilang Kunci
Gunakan pembanding yang membandingkan kunci utama, kemudian kunci sekunder jika kunci utama sama.
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
if (a.age != b.age) return a.age < b.age;
return a.name < b.name;
});Carian Binari pada Julat yang Diisih
Selepas diisih, gunakan std::lower_bound, std::upper_bound dan std::binary_search untuk pencarian dalam O(log N).
Semakan Ringkas
Algoritma manakah yang mengekalkan susunan relatif elemen yang sama selepas pengisihan?
Ringkasan
Gunakan std::sort untuk pengisihan umum, std::stable_sort apabila susunan elemen yang sama penting, std::partial_sort untuk k elemen teratas, std::nth_element untuk pemilihan, dan std::partition/std::stable_partition untuk pengumpulan.
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
- 51
- Pelajaran
- 203
Soalan Lazim
Adakah pelajaran “Pengisihan dan Pembahagian: sort, stable_partition” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran C++ Academy, termasuk “Pengisihan dan Pembahagian: sort, stable_partition”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus C++ Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Pengisihan dan Pembahagian: sort, stable_partition”?
Isih dan bahagikan bekas dengan std::sort dan std::stable_partition. 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 3 daripada 4.
Berapa lamakah pelajaran “Pengisihan dan Pembahagian: sort, stable_partition” 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
- Algoritma Tanpa Pengubahsuaian: find, count, all_of
- Pengubahsuaian: transform, copy_if, replace
- Pengisihan dan Pembahagian: sort, stable_partition
- Algoritma Berangka: accumulate, reduce, transform_reduce