Các thuật toán sắp xếp cơ bản: từ O(n²) đến O(n log n), code C++ và Python

Vì sao sắp xếp là bước mở khóa của hàng loạt bài toán?

Khi các phần tử trong mảng nằm lộn xộn, bạn hầu như không có thông tin gì nếu chưa kiểm tra từng phần tử một. Nhưng ngay khi mảng được sắp xếp tăng dần (chỉ mất O(n log n) một lần ở đầu chương trình), hàng loạt tính chất mạnh mẽ lập tức xuất hiện:

1. Cho phép dùng Tìm kiếm nhị phân và Hai con trỏ: Tìm một giá trị giảm từ O(n) xuống O(log n); tìm cặp có tổng bằng X giảm từ O(n²) xuống O(n).
2. Các phần tử bằng nhau tự động đứng cạnh nhau: Việc đếm số giá trị phân biệt, tìm phần tử xuất hiện nhiều nhất hay gom nhóm chỉ cần một vòng lặp duyệt qua mảng.
3. Phần tử nhỏ nhất và lớn nhất nằm ngay ở hai đầu: Là bước khởi đầu quen thuộc của hầu hết các bài thuật toán tham lam (ví dụ: xếp lịch công việc theo thời điểm kết thúc tăng dần).

Nhóm 1: Ba thuật toán sắp xếp cơ bản O(n²)

Dù không dùng cho mảng hàng trăm nghìn phần tử, 3 thuật toán cơ bản này rất ngắn gọn và giúp bạn rèn kỹ năng điều khiển hai vòng lặp lồng nhau:

• Sắp xếp chọn (Selection Sort): Ở lượt thứ i, tìm phần tử nhỏ nhất trong đoạn chưa sắp xếp [i .. n - 1] rồi đổi chỗ nó về đúng vị trí i. Ưu điểm là tốn ít lần đổi chỗ nhất (tối đa n - 1 lần), nhưng dù mảng ban đầu đã tăng dần sẵn thì nó vẫn mù quáng chạy đủ n(n - 1) / 2 phép so sánh.
• Sắp xếp nổi bọt (Bubble Sort): Duyệt qua mảng nhiều lượt, mỗi lần thấy hai phần tử kề nhau bị ngược thứ tự (a[j] > a[j + 1]) thì đổi chỗ ngay để phần tử lớn nhất "nổi" dần về cuối mảng. Nếu trong một lượt không có lần đổi chỗ nào xảy ra, ta biết mảng đã có thứ tự và dừng sớm.
• Sắp xếp chèn (Insertion Sort): Giống hệt cách bạn xếp các quân bài trên tay. Ở bước thứ i, đoạn đầu a[0 .. i - 1] đã tăng dần; ta rút phần tử key = a[i] ra, dồn các phần tử lớn hơn key sang phải một ô rồi chèn key vào đúng khe trống. Khi mảng gần như đã sắp xếp sẵn, vòng lặp trong hầu như không phải chạy nên Insertion Sort đạt tốc độ gần tuyến tính O(n).

Nhóm 2: Các thuật toán sắp xếp nhanh O(n log n)

Để vượt qua mốc n = 100.000, ta dùng tư duy Chia để trị (Divide and Conquer) kết hợp với đệ quy:

1. Sắp xếp trộn (Merge Sort)

Merge Sort chia đôi mảng thành hai nửa bằng nhau, gọi đệ quy sắp xếp từng nửa, rồi dùng hai con trỏ trên hai mảng để trộn hai nửa đã tăng dần thành một mảng tăng dần hoàn chỉnh:

Vì mảng bị chia đôi liên tiếp nên cây đệ quy chỉ cao log₂ n tầng; ở mỗi tầng, việc trộn tất cả các đoạn tốn tổng cộng O(n) phép so sánh. Nhân lại, độ phức tạp thời gian của Merge Sort luôn luôn là O(n log n) trong mọi trường hợp (tốt nhất, trung bình lẫn xấu nhất), đổi lại nó cần thêm O(n) bộ nhớ cho mảng tạm lúc trộn.

2. Sắp xếp nhanh (Quick Sort)

Thay vì trộn ở bước cuối như Merge Sort, Quick Sort làm việc nặng ngay ở bước chia (gọi là phân hoạch — partition):

• Chọn một phần tử trong đoạn làm chốt (pivot).
• Đưa mọi phần tử nhỏ hơn chốt về bên trái, mọi phần tử lớn hơn chốt về bên phải. Khi đó chốt đã nằm đúng vị trí cuối cùng của nó.
• Gọi đệ quy sắp xếp nửa bên trái và nửa bên phải chốt (không cần bước trộn).

Quick Sort sắp xếp trực tiếp trên mảng gốc (bộ nhớ phụ chỉ tốn O(log n) cho ngăn xếp đệ quy) và có hằng số thực thi rất nhỏ. Tuy nhiên, nếu chọn chốt không khéo (ví dụ luôn chọn phần tử đầu làm chốt mà mảng đầu vào lại đã tăng dần), một bên phân hoạch sẽ có 0 phần tử và bên kia có n - 1 phần tử, làm Quick Sort suy biến thành O(n²). Trong thực tế, người ta chọn chốt ngẫu nhiên hoặc lấy trung vị của 3 phần tử đầu – giữa – cuối.

Hãy xem code cài đặt hoàn chỉnh của Insertion Sort và Merge Sort bằng C++ và Python:

#include <iostream>
#include <vector>
using namespace std;

// 1. Sắp xếp chèn (Insertion Sort) — O(n^2), rất nhanh khi mảng nhỏ hoặc gần có thứ tự
void insertionSort(vector<int>& a) {
    for (int i = 1; i < (int)a.size(); ++i) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];  // dồn phần tử lớn hơn sang phải
            j--;
        }
        a[j + 1] = key;
    }
}

// 2. Sắp xếp trộn (Merge Sort) — luôn đảm bảo O(n log n)
void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);

    vector<int> tam;
    tam.reserve(r - l + 1);
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tam.push_back(a[i++]);
        else tam.push_back(a[j++]);
    }
    while (i <= mid) tam.push_back(a[i++]);
    while (j <= r) tam.push_back(a[j++]);
    for (int k = 0; k < (int)tam.size(); ++k) {
        a[l + k] = tam[k];
    }
}

int main() {
    vector<int> a1 = {38, 27, 43, 3, 9, 82, 10};
    vector<int> a2 = a1;
    insertionSort(a1);
    mergeSort(a2, 0, (int)a2.size() - 1);
    for (int i = 0; i < (int)a1.size(); ++i) {
        cout << a1[i] << (i + 1 == (int)a1.size() ? "\n" : " ");  // 3 9 10 27 38 43 82
    }
    cout << (a1 == a2) << "\n";  // 1
    return 0;
}

def insertion_sort(a):
    """Sắp xếp chèn (Insertion Sort) — O(n^2)."""
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a


def merge_sort(a):
    """Sắp xếp trộn (Merge Sort) — luôn đảm bảo O(n log n)."""
    if len(a) <= 1:
        return list(a)
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res


goc = [38, 27, 43, 3, 9, 82, 10]
a1 = insertion_sort(goc)
a2 = merge_sort(goc)
print(*a1)                 # 3 9 10 27 38 43 82
print(1 if a1 == a2 else 0)  # 1

Bảng so sánh tổng hợp các thuật toán sắp xếp

(Nếu bạn tò mò về những thuật toán sắp xếp hài hước kiểu "tung xúc xắc tới khi mảng tự tăng dần", hãy đọc thêm bài Bogosort: những thuật toán sắp xếp “pha ke”).

Cách dùng hàm sort có sẵn và viết tiêu chí so sánh tùy chỉnh

Khi giải bài tập thuật toán hay đi phỏng vấn, bạn không cần tự viết lại Merge Sort hay Quick Sort từ đầu mà dùng thẳng hàm được tối ưu cực tốt trong thư viện chuẩn:

• Trong C++ (<algorithm>):
  • std::sort(a.begin(), a.end()): dùng thuật toán lai Introsort (kết hợp Quick Sort, Heap Sort khi đệ quy quá sâu và Insertion Sort cho các đoạn nhỏ dưới 16 phần tử), đảm bảo luôn chạy trong O(n log n) nhưng không giữ tính ổn định.
  • std::stable_sort(a.begin(), a.end()): giữ nguyên thứ tự ban đầu của các phần tử bằng nhau.
• Trong Python:
  • a.sort() (sửa trực tiếp danh sách a) hoặc sorted(a) (trả về danh sách mới): dùng thuật toán Timsort (lai giữa Merge Sort và Insertion Sort), vừa đạt O(n log n) vừa ổn định (stable).

Rất nhiều bài toán yêu cầu sắp xếp theo nhiều tiêu chí, ví dụ: "Sắp xếp danh sách thí sinh theo điểm từ cao xuống thấp; nếu hai thí sinh bằng điểm nhau thì người có mã số nhỏ hơn đứng trước". Dưới đây là cách viết chuẩn bằng hàm ẩn danh (lambda) trong C++ và tham số key trong Python:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct ThiSinh {
    int maSo;
    int diem;
};

int main() {
    vector<ThiSinh> ds = {{102, 85}, {101, 90}, {105, 85}, {103, 90}};

    // Xếp điểm giảm dần; nếu điểm bằng nhau thì mã số tăng dần
    sort(ds.begin(), ds.end(), [](const ThiSinh& a, const ThiSinh& b) {
        if (a.diem != b.diem) return a.diem > b.diem;
        return a.maSo < b.maSo;
    });

    for (const auto& ts : ds) {
        cout << ts.maSo << ":" << ts.diem << " ";
    }
    cout << "\n";  // 101:90 103:90 102:85 105:85
    return 0;
}

ds = [(102, 85), (101, 90), (105, 85), (103, 90)]

# Xếp theo (-diem, ma_so): điểm cao đứng trước, cùng điểm thì mã số nhỏ đứng trước
ds.sort(key=lambda ts: (-ts[1], ts[0]))

print(*(f"{ma}:{diem}" for ma, diem in ds))  # 101:90 103:90 102:85 105:85

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Thực hành ngay các bài toán sắp xếp cơ bản và sắp xếp theo tiêu chí tùy chỉnh trên hệ thống Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• cppreference: std::sort
• Python Documentation: Sorting HOW TO
• MIT 6.006 Lecture 3: Sorting