Hướng dẫn thuật toán Quicksort của Python
Khám phá thuật toán quicksort trong Python. Tìm hiểu lựa chọn trục, phân vùng và đệ quy trong ví dụ mã hóa tương tác này.
Tổng quan
Quicksort là một thuật toán sắp xếp cực kỳ nhanh và được sử dụng rộng rãi. Giống như sắp xếp hợp nhất, nó sử dụng cách tiếp cận chia để trị. Tuy nhiên, quicksort sắp xếp các phần tử 'tại chỗ', giúp bộ nhớ hoạt động hiệu quả.
Thuật toán hoạt động bằng cách chọn phần tử 'trục' từ danh sách. Sau đó, nó phân vùng các phần tử khác thành hai mảng con: những phần tử nhỏ hơn trục và những phần tử lớn hơn trục. Quá trình này được áp dụng đệ quy cho các mảng con.
Mặc dù Quicksort có độ phức tạp trong trường hợp xấu nhất là O(n²), nhưng thời gian chạy trong trường hợp trung bình của nó là O(n log n) và nó thường hoạt động tốt hơn phương pháp sắp xếp hợp nhất trong thực tế do lỗi bộ nhớ đệm thấp hơn và chi phí tạo mảng tạm thời bằng không.
Đầu ra mã & thực thi
Tập lệnh Sắp xếp nhanh đệ quy ngắn gọn sử dụng khả năng hiểu danh sách để có khả năng đọc cao.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]Triển khai từng bước
- Các quy trình sắp xếp hệ thống trong đó dung lượng bộ nhớ phải được giữ ở mức tối thiểu
- Sắp xếp mục đích chung trong khung thư viện ngôn ngữ tiêu chuẩn
- Giảng dạy học thuật về cơ học phân vùng và phân chia để chinh phục đệ quy
Câu hỏi thường gặp
Làm cách nào chúng ta có thể tránh được độ phức tạp trong trường hợp xấu nhất của O(n²) trong Quicksort?
Trường hợp xấu nhất xảy ra khi trục được chọn liên tục là phần tử nhỏ nhất hoặc lớn nhất. Để giảm thiểu điều này, các nhà phát triển sử dụng các chiến lược như chọn một trục ngẫu nhiên hoặc giá trị "trung vị của ba".
Quicksort có ổn định không?
Không, Quicksort tiêu chuẩn không ổn định. Trong quá trình phân vùng, các phần tử được hoán đổi trong phạm vi dài, điều này có thể thay đổi thứ tự tương đối của các phần tử trùng lặp.
Chủ đề liên quan
Tìm hiểu cách triển khai Sắp xếp hợp nhất trong Python. Ví dụ tương tác từng bước về chiến lược sắp xếp Phân chia và Chinh phục.
Thuật toán sắp xếp PythonKhám phá các thuật toán sắp xếp python. Trực quan hóa sắp xếp bong bóng và sắp xếp hợp nhất nguyên bản trong ngữ cảnh IDE của trình duyệt.
Thuật toán tìm kiếm nhị phân PythonTìm kiếm danh sách được sắp xếp theo thời gian logarit O(log n). Chạy và hiểu tìm kiếm nhị phân trong Python, bao gồm logic từng bước, các trường hợp phức tạp và tối ưu hóa.