Các thuật toán trong javascript
Chắc hẳn ai từng theo học ngành công nghệ thông tin đều từng ngán ngẩm môn “cấu trúc dữ liệu và giải thuật“. Không biết mọi người thế nào, chứ bản thân mình thì môn này trượt lên trượt xuống. Show Rồi thời gian trôi nhanh như pet chạy ngoài đồng. Nhìn lại cũng đã đi làm được vài năm, cũng phải va vấp vào thuật toán. Đúng là ghét của nào trời trao của ấy. Có bạn nào đi phỏng vấn mà bị nhà tuyển dụng hỏi về thuật toán không? Chắc là có đúng không! Hầu như ai làm về phần mềm thì đều phải làm việc với thuật toán. Bất kể phần mềm lớn hay nhỏ thì đều phải vận dụng thuật toán. Bài viết này, mình sẽ tổng hợp 5 thuật toán phổ biến nhất mà mọi lập trình viên nên biết. Cùng bắt đầu nhé. Chờ chút: Nếu bạn chưa biết thuật toán, đọc lại bài viết này nhé: Thuật toán là gì? Nội dung chính của bài viết
5 thuật toán phổ biến nhấtĐể các bạn dễ theo dõi, mình sẽ sắp xếp theo mức độ phổ biến của thuật toán. 1. Thuật toán sắp xếp nhanh (Quick Sort)Thuật toán Quick Sort được phát triển bởi C.A.R Đúng như tên gọi, thuật toán sắp xếp nhanh là một thuật toán cho kết qua nhanh, gọn, nhẹ. Thuật toán này dựa trên việc chia một mảng thành các mảng nhỏ hơn. Nếu so với các thuật toán sắp xếp khác như Insertion Sort hay sắp xếp nổi bọt (Bubble Sort), thì thuật toán sắp xếp nhanh cho tốc độ nhanh hơn đáng kể. Thuật toán Quick sort là một thuật toán chia để trị (divide and Conquer Algorithm). Nó sẽ chọn một phần tử trong mảng làm điểm đánh dấu (pivot). Sau khi lựa chọn được điểm pivot, bước tiếp theo sẽ chia mảng thành nhiều mảng con dựa vào pivot đã chọn. Và lặp đi lặp lại như vậy cho đến khi kết thúc. Tốc độ của thuật toán bị ảnh hưởng bởi việc chọn pivot. Có nhiều cách chọn pivot, dưới đây là một số cách:
Để mình họa cho thuật toán sắp xếp nhanh, chúng ta cùng thực hành một bài toán: Sắp xếp mảng sau theo thứ tự tăng dần: [10, 7, 8, 9, 1, 5] Quicksort example program in c++: #include |