Các thuật toán sắp xếp

 131268105 lượt xem
Các thuật toán sắp xếp
Nếu bạn thấy hay hãy like share cho bạn bè cùng biết nhé !
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Merge sort

Giống như Quick sort, Merge sort là thuật toán chia để trị. Chia mảng thành các mảng nhỏ, sau đó gộp các mảng nhỏ đã sắp xếp lại với nhau.

Ví dụ với mảng 38, 27, 43, 3, 9, 82, 10, trình tự của merge sort sẽ như sau:Các thuật toán sắp xếp

Triển khai thuật toán: Vì merge sort là một thuật toán sử dụng rất nhiều bộ nhớ nên sẽ tốt hơn khi sử dụng linked list, với linked list thì việc tách mảng và lưu trữ sẽ đơn giản hơn rất nhiều so với sử dụng mảng thông thường (Bạn cần có kiến thức cơ bản về con trỏ trước khi xem đoạn code dưới).

Counting sort

  Nâng cao, Phát triển sự nghiệp của bạn trong kiểm thử phần mềm

Counting sort là một kỹ thuật sắp xếp các đối tượng trong một phạm vị cụ thể. Nó hoạt động bằng cách đếm số lượng các đôi tượng có giá trị giống nhau. Sau đó sử dụng một chút toán học để tính toán vị trí cuối cùng của đối tượng đó.

Độ phức tạp của thuật toán này là O(n+k) với n là số lượng đối lượng, k là phạm vị giá trị của n đối tượng.

Hãy tìm hiểu thông qua 1 ví dụ:

Đây là một đoạn code sắp xếp mảng các ký tự, thuật toán cũng có thể được sử dụng để sắp xếp mảng các số nguyên. Với mảng các số nguyên bao gồm cả số âm và dương thì cần phải thay đổi thuật toán 1 chút. Lí do là vì trong c++ bạn không thể truy cập giá trị tại ví trí âm trong mảng. Để giải quyết vấn đề này bạn cần tính lại khoảng k và xây dựng lại mảng count sao cho phần tử nhỏ nhất ở trị trí 0.

Radix sort

Các thuật toán quen thuộc như quick sort, merge sort, heap sort,… là các thuật toán sắp xếp dựa vào giá trị của các phép so sánh, độ phức tạo của các thuật toán này không thể tốt hơn O(nLogn). Còn với thuật toán counting sort ở trên, là một thuật toán tuyến tính với độ phức tạp là O(n+k). Trong trường hợp k bằng n*n thì counting sort là một lựa chọn tồi. Radix sort là một lựa chọn tốt trong TH này.

Tư tưởng của thuật toán này là sắp xếp các số theo giá trị của hàng chục, hàng trăm, hàng nghìn, …

Ví dụ:

Triển khai thuật toán:

Bạn có tìm thấy thông tin hữu ích nào trong bài viết của chúng tôi không?

Hướng dẫn kỹ năng viết blog chuyên nghiệp kiếm tiền online. Xây dựng nguồn thu nhập thụ động từ internet và tự chủ về tài chính.
Câu hỏi - Hướng dẫn này có mang lại lợi ích cho bạn không? Để lại một bình luận dưới đây. 
Bạn có biết ai có thể hưởng lợi từ hướng dẫn này không? Gửi cho họ trang này hoặc nhấp vào nút chia sẻ ở bên trái.
Bạn sẽ giúp chúng tôi bằng cách chia sẻ bài viết này chứ?
Quét bằng QR Code
Mã QR Code

Bạn có thể dùng ứng dụng đọc QR Code trên điện thoại để mở đường dẫn này
Xem hướng dẫn tại đây.

Đóng

QC.Sản phẩm nổi bật

Bài viết liên quan