Thuật toán JavaScript: Quicksort

Quicksort là một thuật toán tìm kiếm hiệu quả hơnsắp xếp lựa chọn,trong hầu hết các trường hợp, và nó sử dụng đệ quy.

Đệ quy có nghĩa là chúng ta gọi một hàm từ bên trong cùng một hàm. Đó là một thực hành rất hữu ích, đôi khi, và đây là một trong những trường hợp đó.

Tôi đã nói "trong hầu hết các trường hợp", vì như chúng ta sẽ thấy, trong trường hợp xấu nhất, sắp xếp bong bóng có thể mất cùng thời gian với việc sắp xếp lựa chọn:O(n^2). Nhưng trong trường hợp tốt nhất, nó sẽ chạy ởO(n log n), ở giữaO(n)O(n^2).

Làm thế nào nó hoạt động? Cho một mảng, chúng tôi chọn một mục, được gọi làtrục. Sau đó, chúng tôi nhận được tất cả các mục nhỏ hơn trục và các mục lớn hơn trục.

Sau đó, chúng tôi chạy cùng một hoạt động trên 2 mảng để tạo các mục nhỏ hơn và lớn hơn.

Dễ dàng xem mã hơn là mô tả nó:

const quickSort = (originalList) => {
  const list = [...originalList]

if (list.length < 2) { return list }

const pivot = list[0]

const smaller = list.filter((item) => item < pivot) const bigger = list.filter((item) => item > pivot)

return […quickSort(smaller), pivot, …quickSort(bigger)] }

Trong trường hợp này, tôi đã chọn pivot là mục đầu tiên trong mảng, nhưng nó cũng có thể là mục ở giữa, ví dụ:

const pivot = list[Math(floor(list.length / 2)]

Lưu ý cách chúng tôi sao chép mảng đầu tiên, vì vậy việc gọiquickSort()không sửa đổi mảng ban đầu, nó chỉ trả về một mảng mới được sắp xếp:

const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]

console.log(quickSort(a)) //[0, 1, 1, 3, 4, 4, 5, 6, 8 console.log(a) //[1, 6, 3, 4, 5, 1, 0, 4, 8]

Tải xuống miễn phí của tôiSổ tay dành cho Người mới bắt đầu JavaScript


Các hướng dẫn js khác: