Chủ đề này có 5 trả lời

[hugobaoloc]

Em chào các thầy, các anh...em muốn hỏi Các thuật toán sắp xếp được phân loại như thế nào dựa theo nguyên lý cơ sở của nó? Mong các thầy, các anh giúp em...em không hiểu vấn đề này...Em xin cảm ơn.

[FOOL90]

Cái này có lẽ không thuộc về phần này cho lắm .
Có lẽ cái bạn đề cập thuộc vấn đề tin học.
Mình sẽ nói theo ngôn ngữ tin học ( mảng)
mình cũng biết một số cái .
Phân loại:
- Phương pháp xen trực tiếp ( straight isnertion) với mỗi i=2,3...n tìm vi trí để chèn vào đúng vị trí a[i] vào đúng vị trí của nó theo thứ tự tăng dầntrong dãy a[1], a[2]...a[i-1].
- Phương pháp xen nhị phân (binary insertion) tươnng tự pp xen trực tiwwps ,nhưng khi tìm vị trí thích hợp cho phần tử a[i] ta không sử dụng cách tìm tuần tự mà sử dụng cách tìm nhị phân( chia đôi đoạn a[1].......a[i-1] để tìm)
- Phương pháp chọn trực tiếp ( straigh selection) với mỗi phần tử thứ i (i=1.2.....n-1) ,mỗi lần có phâng tử từ i+1 đến n nhỏ hơn phần tử thứ i thì đổi chỗ hai phần tử cho nhau .
- Phương pháp nổi bọt (bubble sort) sau vòng lặp i=1 phần tử có khóa lớn nhất chìm xuống vị trí a[n] và một số phần tử nổi lên một mức ,sau vòng lặp i=2 phần tử có khóa lớn nhất chìm xuống vị trí a[n-1]
- Phương pháp sắp xếp nhanh (quick sort) Bước đầu chọn phần tử đầu tiên a[1] của mảng cần sắp xếp a[1..n] làm mốc, sau đó phân hoạch thành 2 phần bằng cách chuyển tất cả các thành phần có khóa lớn hơn khóa của mốc sang bên phải mốc , còn tất cả các khóa nhỏ hơn chuyển sang bên trái mốc.

[neverstop]

Bạn tham khảo tài liệu này xem có ích gì không nhé, trong này trình bày rất cặn kẽ các thuật toán cơ sở, phân tích và minh họa rõ ràng bằng ngôn ngữ Pascal: http://rapidshare.co..._Minh_Hoang.pdf

Cuốn sách còn trình bày cặn kẽ những thuật toán khác nữa như tìm kiếm, quy hoạch động, vét cạn, đồ thị, ... chắc sẽ rất hữu ích với bạn.

[toanhoc]

Bạn có thể tham khảo: Algorithms của Robert Sedgewick (Luận án của ông này là về quicksort)-quyển này có bản dịch tiếng Việt tựa là Cẩm nang thuật toán gồm 2 tập nhưng tốt hơn dùng trực tiếp bạn gốc.
Quyển tôi thích nhất là Data structures and algorithms của Aho, Hopcroft and Ullman. Đây là 1 trong tủ sách kinh điển của 3 vị này.
Tôi không hiều lắm câu hỏi của bạn. Bạn muốn phân loại dựa trên time complexity ? Cái này được bàn rất hay trong quyển của 3 vị trên. Nó phụ thuộc nhiều thứ: kích cỡ dữ liệu, phân bố dữ liệu... big O chỉ là 1 phần.
Merge Sort là thuật toán tốt cho sắp xếp ngoài vì mỗi lần bạn có thể load 1 run vào internal memory, chỉ có khi merge lại mới cần truy xuất thiết bị lưu trữ. Các thuật toán còn lại chủ yếu là sắp xếp trong.
Gần đây, tôi mới biết có các thuật toán randomized, trong đó có randomized quicksort nhưng thú thật hiện tôi mù tịt mấy thứ này.

[Tái xuất giang hồ]

Có trang này, gồm những programme viết sẵn, bác tải vể dùng thử.
http://www.yendor.co...ogramming/sort/

[Magus]

Em chào các thầy, các anh...em muốn hỏi Các thuật toán sắp xếp được phân loại như thế nào dựa theo nguyên lý cơ sở của nó? Mong các thầy, các anh giúp em...em không hiểu vấn đề này...Em xin cảm ơn.

Hình như có 2 loại thuật toán sắp xếp:

Sắp xếp ổn định
Một thuật toán sắp xếp được gọi là sắp xếp ổn định nếu sau khi tiến hành sắp xếp vị trí tương đối giữa các phần tử bằng nhau không bị thay đổi.


Sắp xếp so sánh
Một thuật toán sắp xếp được gọi là sắp xếp so sánh nếu trong quá trình thực hiện thuật toán ta tiến hành so sánh các khoá và đổi chỗ các phần tử cho nhau. Đa số các thuật toán sắp xếp dưới đây là sắp xếp so sánh, riêng sắp xếp đếm phân phối không phải là sắp xếp so sánh