Các thuật toán này có độ phức tạp trung bình là O(N*logN)

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

Ý tưởng

  • Chia dãy thành 2 phần, một phần “lớn” và một phần “nhỏ”.
    • Chọn một khóa pivot.
    • Những phần tử lớn hơn pivot chia vào phần lớn.
    • Những phần tử nhỏ hơn hoặc bằng pivot chia vào phần nhỏ.
  • Gọi đệ quy để sắp xếp 2 phần.

Ưu điểm

  • Chạy nhanh (nhanh nhất trong các thuật toán sắp xếp dựa trên việc so sánh các phần tử). Do đó quicksort được sử dụng trong nhiều thư viện của các ngôn ngữ như Java, C++ (hàm sort của C++ dùng Intro sort, là kết hợp của Quicksort và Insertion Sort).

Nhược điểm

  • Tùy thuộc vào cách chia thành 2 phần, nếu chia không tốt, độ phức tạp trong trường hợp xấu nhất có thể là O(N2). Nếu ta chọn pivot ngẫu nhiên, thuật toán chạy với độ phức tạp trung bình là O(N∗logN) (trong trường hợp xấu nhất vẫn là O(N2), nhưng ta sẽ không bao giờ gặp phải trường hợp đó).
  • Không ổn định do phù thuộc vào phần tử chốt (pivot).

Code minh họa (C#)

// Sắp xếp nhanh 
// l là index đầu tiên của mảng, r là index cuối cùng của mảng
public static void QuickSort(ref int[] data, int l, int r)
{
    // Nếu index đầu tiên <= index cuối cùng
    if (l <= r)
    {
        // Tạo phần tử key (ở đây lấy giá trị giữa của mảng)
        int key = data[(l + r) / 2];

        // Tạo biến tạm để lặp
        int i = l;
        int j = r;

        while (i <= j)
        {
            while (data[i] < key)
                i++;
            while (data[j] > key)
                j--;

            if (i <= j)
            {
                Swap(ref data[i], ref data[j]);
                i++;
                j--;
            }
        }

        // Đệ quy
        if (l < j)
            QuickSort(ref data, l, j);
        if (r > i)
            QuickSort(ref data, i, r);
    }
}

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

Ý tưởng

Sắp xếp trộn hoạt động kiểu đệ quy:

  • Đầu tiên chia dữ liệu thành 2 phần, và sắp xếp từng phần.
  • Sau đó gộp 2 phần lại với nhau. Để gộp 2 phần, ta làm như sau:
    • Tạo một mảng mới để chứa các phần tử đã sắp xếp.
    • So sánh 2 phần tử đầu tiên của 2 phần. Phần tử nhỏ hơn ta cho vào mảng mới và xóa khỏi phần tương ứng.
    • Tiếp tục như vậy đến khi ta cho hết các phần tử vào mảng mới.

Ưu điểm

  • Chạy nhanh.
  • Ổn định.

Nhược điểm

  • Cần dùng thêm bộ nhớ để lưu mảng.

Code minh họa (C#)

// Sắp xếp các phần tử có chỉ số từ left đến right của mảng data.
void Merge(ref int[] arr, int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    //tạo 2 mảng tạm thời để chứa các phần tử sau khi chia
    int[] L = new int[n1];
    int[] R = new int[n2];

    // Copy dữ liệu sang các mảng tạm 
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // khởi tạo các giá trị ban đầu
    i = 0;
    j = 0;
    k = l;

    //gộp hai mảng tạm thời vào mảng arr
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy các phần tử còn lại của mảng L vào arr nếu có 
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy các phần tử còn lại của mảng R vào arr nếu có 
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp 
void MergeSort(ref int[] arr, int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;
        // Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng
        MergeSort(ref arr, l, m);
        MergeSort(ref arr, m + 1, r);

        Merge(ref arr, l, m, r);
    }
}

3. Sắp xếp vun đống (Heap Sort)

Ý tưởng

  • Dự vào cấu trúc dữ liệu đống nhị phân (Binary Heap).
  • Ta lưu mảng vào CTDL Heap.
  • Ở mỗi bước, ta lấy ra phần tử nhỏ nhất trong Heap, cho vào mảng đã sắp xếp.

Ưu điểm

  • Cài đặt đơn giản nếu đã có sẵn thư viện Heap.
  • Chạy nhanh

Nhược điểm

  • Không ổn định

Code minh họa (C#)

// Sắp xếp vun đống
void HeapSort(int[] arr)
{
    int n = arr.Length;

    // Tạo Heap
    for (int i = n / 2 - 1; i >= 0; i--)
        Heapify(arr, n, i);

    // Lấy phần tử từ Heap
    for (int i = n - 1; i > 0; i--)
    {
        // Duyệt từ gốc đến hết
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Lấy giá trị lớn nhất từ Heap
        Heapify(arr, i, 0);
    }
}

// Xây dựng một Heap
void Heapify(int[] arr, int n, int i)
{
    int largest = i;   // Nút gốc (nút có giá trị lớn nhất)
    int l = 2 * i + 1; 
    int r = 2 * i + 2; 

    // Nếu nút con bên trái lớn hơn nút gốc
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // Nếu nút con bên phải lớn hơn giá trị lớn nhất
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // Nếu giá trị lớn nhất không phải là gốc
    if (largest != i)
    {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // Đệ quy
        Heapify(arr, n, largest);
    }
}