MinhIT1991
Admin
Tổng số bài gửi : 130
Join date : 12/08/2011
Age : 32
Đến từ : Đại học Lạc Hồng
 |  Tiêu đề: BTVN (Định nghĩa các thuật toán sắp xếp)  Wed Sep 21, 2011 9:56 pm | |
| Sắp xếp đổi chỗ
Sắp xếp đổi chỗ (bubble sort) là phương pháp sắp xếp đơn giản, dễ hiểu thường được dạy trong khoa học máy tính. Giải thuật bắt đầu từ đầu của tập dữ liệu. Nó so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử tiếp theo cho đến cuối tập hợp dữ liệu. Sau đó nó quay lại với hai phần tử đầu cho đến khi không còn cần phải đổi chỗ nữa.
Sắp xếp chèn
Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp rất hiệu quả với các danh sách nhỏ. Nó lần lượt lấy các phần tử của danh sách chèn vào vị trí thích hợp trong một danh sách mới đã được sắp.
Sắp xếp chọn
Sắp xếp chọn (select sort) là phương pháp sắp xếp bằng cách chọn phần tử bé nhất xếp vào vị trí thứ nhất, tương tự với các phần tử nhỏ thứ hai, thứ ba,...
Sắp xếp trộn
Sắp xếp trộn (merge sort) cùng với sắp xếp nhanh là hai thuật toán sắp xếp dựa vào tư tưởng "chia để trị" (divide and conquer). Thủ tục cơ bản là việc trộn hai danh sách đã được sắp xếp vào một danh sách mới theo thứ tự. Nó có thể bắt đầu trộn bằng cách so sánh hai phần tử một (chẳng hạn phần tử thứ nhất với phần tử thứ hai, sau đó thứ ba với thứ tư...) và sau khi kết thúc bước 1 nó chuyển sang bước 2. Ở bước 2 nó trộn các danh sách hai phần tử thành các danh sách bốn phần tử. Cứ như vậy cho đến khi hai danh sách cuối cùng được trộn thành một.
Sắp xếp vun đống
Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).
Sắp xếp nhanh
Sắp xếp nhanh (quicksort) là một thuật toán theo tư tưởng chia để trị ,nó dựa trên thủ tục phân chia như sau: để chia một dãy ta chọn một phần tử được gọi là "chốt" (pivot), chuyển tất cả các phần tử nhỏ hơn chốt về trước chốt, chuyển tất cả các phần tử lớn hơn chốt về sau nó. Thủ tục này có thể thực hiện trong thời gian tuyến tính. Tiếp tục phân chia các dãy con đó như trên cho đến khi các dãy con chỉ còn một phần tử.
Điểm khác biệt giữa sắp xếp nhanh và sắp xếp trộn là trong sắp xếp trộn việc xác định thứ tự được xác định khi "trộn", tức là trong khâu tổng hợp lời giải sau khi các bài toán con đã được giải, còn sắp xếp nhanh đã quan tâm đến thứ tự các phần tử khi phân chia một danh sách thành hai danh sách con.
Ngoài ra còn nhiều giải thuật sắp xếp khác, trong đó nhiều giải thuật sắp xếp được cải tiến từ các giải thuật trên. Trong sau giải thuật liệt kê trên, ta thường coi các giải thuật chèn, chọn, nổi bọt là các giải thuật cơ bản, độ phức tạp trong trường hợp trung bình của chúng là O(n2). Ba giải thuật còn lại thường được coi là giải thuật cao cấp, độ phức tạp tính toán trung bình của chúng là n.lnn.
|
|
