Sắp xếp nhanh là một giải thuật chia để trị. Sắp xếp nhanh chia một mảng lớn thành hai mảng con nhỏ hơn: mảng các phần tử nhỏ và các phần tử lớn. Sắp xếp nhanh có thể thiết kế bằng đệ quy.
Các bước :
- Chọn một phần tử gọi là chốt, từ mảng.
- Phân vùng: sắp xếp lại thứ tự mảng để tất cả các phần tử có giá trị nhỏ hơn chốt đều nằm ở trước chốt, trong khi các phần tử có giá trị lớn hơn chốt đều đứng sau nó (các giá trị bằng chốt có thể nằm ở trước hay sau đều được). Sau khi phân vùng, chốt sẽ ở vị trí cuối cùng cùng nó. Đây được gọi là thao tác phân vùng.
- Áp dụng đệ quy các bước trên cho mảng con gồm các phần tử có giá trị nhỏ hơn và cả mảng con gồm các phần tử có giá trị lớn hơn.
Ảnh động mô tả giải thuật sắp xếp nhanh, dòng ngang là giá trị chốt.
| Name | Best | Average | Worst | Memory | Stable | Comments |
|---|---|---|---|---|---|---|
| Quick sort | n log(n) | n log(n) | n2 | log(n) | No | Quicksort is usually done in-place with O(log(n)) stack space |