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

18755 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:

hãy comment và chia sẻ ủng hộ ad !
Thấy hay hãy like
  • Làm thế nào để vượt mặt đối thủ cạnh tranh ?

  • Bạn cần website để giới thiệu dịch vụ ?

  • Cho đến lúc này, điều mà bạn đang quan tâm có lẽ là muốn tìm hiểu thêm về dịch vụ thiết kế website và Công ty chúng tôi ?

  • SỞ HỮU NGAY WEB CHUYÊN NGHIỆP TẠI WEBSHARE MEDIA VIỆT NAM ĐỂ VƯỢT MẶT ĐỐI THỦ NGAY HÔM NAY !!!

Bài viết liên quan

Leave a Reply

avatar
  Subscribe  
Notify of