Tóm tắt¶

Điểm lại trọng tâm¶

Sắp xếp nổi bọt thực hiện sắp xếp bằng cách hoán đổi các phần tử liền kề. Bằng cách thêm biến cờ hiệu để kích hoạt kết thúc sớm, chúng ta có thể tối ưu hóa độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp nổi bọt thành \(O(n)\).
Trong mỗi vòng, sắp xếp chèn đưa một phần tử từ phần chưa được sắp xếp vào đúng vị trí của nó trong phần đã được sắp xếp. Mặc dù sắp xếp chèn có độ phức tạp thời gian là \(O(n^2)\), nó vẫn rất phổ biến đối với các tác vụ sắp xếp quy mô nhỏ vì mỗi thao tác tương đối nhẹ.
Sắp xếp nhanh dựa trên phân hoạch lính canh. Trong phân hoạch lính canh, việc liên tục chọn phải chốt tồi nhất có thể làm suy giảm độ phức tạp thời gian về \(O(n^2)\). Việc chọn chốt dựa trên trung vị hoặc chọn chốt ngẫu nhiên có thể làm giảm xác suất xảy ra sự suy giảm này. Bằng cách gọi đệ quy trên mảng con ngắn hơn trước, chúng ta có thể giảm độ sâu đệ quy một cách hiệu quả và tối ưu hóa độ phức tạp không gian thành \(O(\log n)\).
Sắp xếp trộn gồm hai giai đoạn: chia và trộn, thể hiện điển hình cho chiến lược chia để trị. Trong sắp xếp trộn, sắp xếp một mảng đòi hỏi phải tạo các mảng phụ trợ, dẫn đến độ phức tạp không gian là \(O(n)\); tuy nhiên, độ phức tạp không gian khi sắp xếp một danh sách liên kết có thể được tối ưu hóa về \(O(1)\).
Sắp xếp xô gồm ba bước: phân bổ dữ liệu vào các xô, sắp xếp bên trong các xô, và gộp các kết quả. Thuật toán này cũng thể hiện chiến lược chia để trị và phù hợp với lượng dữ liệu rất lớn. Chìa khóa của sắp xếp xô là phân bổ dữ liệu một cách đồng đều.
Sắp xếp đếm là một trường hợp đặc biệt của sắp xếp xô, thực hiện sắp xếp bằng cách đếm số lần xuất hiện của dữ liệu. Sắp xếp đếm phù hợp cho các tình huống có lượng dữ liệu lớn nhưng phạm vi dữ liệu bị giới hạn, và yêu cầu dữ liệu có thể chuyển đổi thành các số nguyên dương.
Sắp xếp cơ số thực hiện sắp xếp dữ liệu bằng cách sắp xếp theo từng chữ số, yêu cầu dữ liệu có thể biểu diễn dưới dạng các số có số chữ số cố định.
Nhìn chung, chúng ta hy vọng tìm được một thuật toán sắp xếp hiệu quả, ổn định, tại chỗ và thích ứng. Tuy nhiên, tương tự như các cấu trúc dữ liệu và thuật toán khác, không có thuật toán sắp xếp nào có thể đáp ứng đồng thời tất cả các tiêu chí này. Trong thực tế, chúng ta cần lựa chọn thuật toán sắp xếp phù hợp dựa trên các đặc tính của dữ liệu.
Hình dưới đây so sánh các thuật toán sắp xếp phổ biến về hiệu suất, tính ổn định, đặc tính tại chỗ và tính thích ứng.

Q & A¶

Q: Trong trường hợp nào thì tính ổn định của thuật toán sắp xếp là cần thiết?

Trong thực tế, chúng ta có thể sắp xếp dựa trên một thuộc tính nhất định của đối tượng. Ví dụ, học sinh có hai thuộc tính: tên và chiều cao. Chúng ta muốn thực hiện sắp xếp đa cấp: đầu tiên sắp xếp theo tên để được (A, 180) (B, 185) (C, 170) (D, 170); sau đó sắp xếp theo chiều cao. Vì thuật toán sắp xếp không ổn định, chúng ta có thể nhận được kết quả là (D, 170) (C, 170) (A, 180) (B, 185).

Chúng ta có thể thấy rằng học sinh D và C đã bị hoán đổi vị trí, phá vỡ thứ tự sắp xếp theo tên trước đó, đây không phải là điều chúng ta mong muốn.

Q: Có thể hoán đổi thứ tự "tìm kiếm từ phải sang trái" và "tìm kiếm từ trái sang phải" trong phân hoạch lính canh được không?

Không được. Khi sử dụng phần tử ngoài cùng bên trái làm chốt, chúng ta phải "tìm kiếm từ phải sang trái" trước, rồi mới "tìm kiếm từ trái sang phải". Kết luận này có phần hơi trái ngược với trực giác; chúng ta hãy cùng phân tích nguyên nhân.

Bước cuối cùng của phân hoạch lính canh partition() là hoán đổi nums[left] và nums[i]. Sau khi hoàn thành hoán đổi, các phần tử bên trái của chốt đều phải \(\le\) chốt, điều này yêu cầu điều kiện nums[left] >= nums[i] phải được thỏa mãn trước khi thực hiện lần hoán đổi cuối cùng. Giả sử chúng ta "tìm kiếm từ trái sang phải" trước, khi đó nếu không tìm thấy phần tử nào lớn hơn chốt, chúng ta sẽ thoát khỏi vòng lặp khi i == j, lúc này có thể xảy ra trường hợp nums[j] == nums[i] > nums[left]. Nói cách khác, thao tác hoán đổi cuối cùng sẽ chuyển một phần tử lớn hơn chốt về ngoài cùng bên trái của mảng, khiến phân hoạch lính canh bị thất bại.

Ví dụ, cho trước mảng [0, 0, 0, 0, 1], nếu tìm kiếm từ trái sang phải trước, mảng sau khi phân hoạch lính canh sẽ là [1, 0, 0, 0, 0], điều này là sai.

Cũng với lập luận tương tự, nếu chọn nums[right] làm chốt, thứ tự sẽ bị đảo ngược: chúng ta phải "tìm kiếm từ trái sang phải" trước.

Q: Về việc tối ưu hóa độ sâu đệ quy trong sắp xếp nhanh, tại sao việc chọn mảng con ngắn hơn có thể đảm bảo độ sâu đệ quy không vượt quá \(\log n\)?

Độ sâu đệ quy là số lượng lời gọi đệ quy chưa trả về. Mỗi vòng phân hoạch lính canh chia mảng ban đầu thành hai mảng con. Sau tối ưu hóa này, mảng con được chọn để tiếp tục gọi đệ quy có độ dài tối đa bằng một nửa mảng ban đầu. Trong trường hợp xấu nhất, nếu độ dài luôn bị giảm đi một nửa, độ sâu đệ quy cuối cùng sẽ là \(\log n\).

Xem xét lại thuật toán sắp xếp nhanh nguyên bản, chúng ta có thể liên tục gọi đệ quy trên mảng con dài hơn. Trong trường hợp xấu nhất, các độ dài mảng con sẽ lần lượt là \(n\), \(n - 1\), \(\dots\), \(2\), \(1\), dẫn đến độ sâu đệ quy là \(n\). Việc tối ưu hóa độ sâu đệ quy có thể tránh được tình huống này.

Q: Khi tất cả các phần tử trong mảng đều bằng nhau, độ phức tạp thời gian của sắp xếp nhanh có phải là \(O(n^2)\) không? Trường hợp thoái hóa này nên được xử lý như thế nào?

Có. Trong trường hợp này, mảng có thể được chia thành ba phần thông qua phân hoạch: nhỏ hơn, bằng, và lớn hơn chốt. Sau đó, chúng ta chỉ gọi đệ quy trên phần nhỏ hơn và phần lớn hơn. Với cách tiếp cận này, một mảng có tất cả các phần tử bằng nhau có thể được sắp xếp chỉ trong một vòng phân hoạch.

Q: Tại sao độ phức tạp thời gian trong trường hợp xấu nhất của sắp xếp xô lại là \(O(n^2)\)?

Trong trường hợp xấu nhất, tất cả các phần tử đều được phân bổ vào cùng một xô. Nếu chúng ta sử dụng một thuật toán có độ phức tạp \(O(n^2)\) để sắp xếp các phần tử này, độ phức tạp thời gian sẽ là \(O(n^2)\).