0Pricing
C++ Academy · บทเรียน

การเรียงลำดับและแบ่งพาร์ทิชัน sort stable_partition

เรียงลำดับและแบ่งพาร์ทิชันคอนเทนเนอร์ด้วย std::sort และ std::stable_partition

การเรียงลำดับและแบ่งพาร์ทิชัน sort stable_partition เป็นบทเรียน C++ Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน C++ Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส C++ Academy มีบทเรียนทั้งหมด 4 บทเรียน

std::sort

std::sort
#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascending

ตัวเปรียบเทียบแบบกำหนดเอง

ส่งตัวเปรียบเทียบ (แลมบ์ดาหรือฟังก์เตอร์) เพื่อเรียงลำดับตามเกณฑ์อื่น

std::sort(v.begin(), v.end(),
    [](int a, int b) { return a > b; });   // descending

การเรียงลำดับชนิดข้อมูลกำหนดเอง

จัดเตรียมตัวเปรียบเทียบที่เปรียบเทียบสมาชิกเฉพาะ หรือกำหนด operator< ให้กับชนิดข้อมูล

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

เหมือนกับการเรียงลำดับ แต่จะรักษาลำดับสัมพัทธ์ของสมาชิกที่มีค่าเท่ากันไว้ ใช้เวลาช้าลงเล็กน้อย (โดยทั่วไปใช้หน่วยความจำเพิ่มเติม O(N log^2 N))

std::partial_sort

วางสมาชิกที่มีค่าน้อยที่สุด k ตัวไว้ด้านหน้าและเรียงลำดับแล้ว สมาชิกที่เหลือจะอยู่ในลำดับที่ไม่ได้ระบุ เร็วกว่าการเรียงลำดับทั้งหมดเมื่อคุณต้องการเฉพาะ k อันดับแรก

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, sorted

std::nth_element

แบ่งช่วงข้อมูลเพื่อให้สมาชิกที่ตำแหน่ง nth อยู่ในตำแหน่งเดียวกับที่จะอยู่หากเรียงลำดับทั้งช่วง สมาชิกทั้งหมดก่อนหน้านั้นมีค่าน้อยกว่าหรือเท่ากับสมาชิกที่ตำแหน่ง nth และสมาชิกทั้งหมดหลังจากนั้นมีค่ามากกว่าหรือเท่ากับ ใช้เวลาเฉลี่ย O(N)

std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest element

std::is_sorted

ตรวจสอบว่าช่วงข้อมูลเรียงลำดับอยู่แล้วหรือไม่

if (std::is_sorted(v.begin(), v.end())) {
    std::cout << "already sorted";
}

std::partition

จัดเรียงช่วงข้อมูลใหม่ให้สมาชิกที่ตรงตามเงื่อนไขอยู่ด้านหน้า คืนตัววนซ้ำที่ชี้ไปยังสมาชิกตัวแรกที่ไม่ตรงตามเงื่อนไข และไม่รักษาลำดับเดิม

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 odd

std::stable_partition

เหมือนกับการแบ่งช่วงข้อมูล แต่จะรักษาลำดับสัมพัทธ์ภายในแต่ละกลุ่มไว้

การเรียงลำดับด้วยหลายคีย์

ใช้ตัวเปรียบเทียบที่เปรียบเทียบคีย์หลักก่อน แล้วจึงเปรียบเทียบคีย์รองเมื่อคีย์หลักมีค่าเท่ากัน

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;
    });

การค้นหาแบบทวิภาคบนช่วงข้อมูลที่เรียงลำดับแล้ว

เมื่อเรียงลำดับแล้ว ให้ใช้ std::lower_bound, std::upper_bound และ std::binary_search เพื่อค้นหาโดยใช้เวลา O(log N)

ตรวจสอบความเข้าใจ

อัลกอริทึมใดรักษาลำดับสัมพัทธ์ของสมาชิกที่มีค่าเท่ากันหลังการเรียงลำดับ

ทบทวน

ใช้ std::sort สำหรับการเรียงลำดับทั่วไป ใช้ std::stable_sort เมื่อลำดับของสมาชิกที่มีค่าเท่ากันมีความสำคัญ ใช้ std::partial_sort สำหรับ k อันดับแรก ใช้ std::nth_element สำหรับการเลือก และใช้ std::partition/std::stable_partition สำหรับการจัดกลุ่ม

คำถามที่พบบ่อย

บทเรียน “การเรียงลำดับและแบ่งพาร์ทิชัน sort stable_partition” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “การเรียงลำดับและแบ่งพาร์ทิชัน sort stable_partition” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส C++ Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส C++ Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “การเรียงลำดับและแบ่งพาร์ทิชัน sort stable_partition”

เรียงลำดับและแบ่งพาร์ทิชันคอนเทนเนอร์ด้วย std::sort และ std::stable_partition คุณปฏิบัติ C++ Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน C++ Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน C++ Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน

บทเรียน “การเรียงลำดับและแบ่งพาร์ทิชัน sort stable_partition” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน C++ Academy นี้ได้ไหม

ได้ บทเรียน C++ Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. อัลกอริทึมที่ไม่แก้ไข: find count all_of
  2. การแก้ไขด้วย transform copy_if replace
  3. การเรียงลำดับและแบ่งพาร์ทิชัน sort stable_partition
  4. อัลกอริทึมเชิงตัวเลข accumulate reduce transform_reduce
← กลับไปที่ C++ Academy