Sắp xếp - Sorting

Ta khảo sát trường hợp xấu nhất, trung bình và tốt nhất cho mỗi giải thuật. Thời gian thực hiện thay đổi dựa vào sự phân bố ban đầu của dãy. | Đặt vấn đề Sắp xếp là một quá trình tổ chức lại một dãy các dữ liệu theo một trật tự nhất định Mục đích của sắp xếp là nhằm giúp cho việc tìm kiếm dữ liệu được dễ dàng nhanh chóng Ví dụ: Cho trước một dãy n số nguyên được sắp thứ tự tăng dần Việc tìm kiếm một phần tử x nào đó được thực hiện bằng cách chia đôi dãy ban đầu Chỉ cần k bước ta xác định được phần tử cần tìm Trường hợp xấu nhất Vậy với n = 1000 210 chỉ cần 10 bước là ta xác định được phần tử cần tìm trong dãy 1000 phần tử n = 220 n = 1 tỷ 230 Rõ ràng sắp xếp là một việc làm hết sức cơ bản và được áp dụng rộng rãi trong các kỹ thuật lập trình nhằm xử lý thông tin. Đặt vấn đề Sorting Nội dung Định nghĩa Giả thiết Sắp xếp tại chỗ Chiến lược sắp xếp Tổng quan về thời gian thực hiện Sorting Định nghĩa Sắp xếp là một tiến trình: Tìm một bộ hoán vị trên tập hợp các đối tượng cho trước a1, a2, ., an (ví dụ là các số nguyên), và Trả về một thứ tự khác (a'1, a'2, ., a'n) sao cho a'1 ≤ a'2 ≤ · · · ≤ a'n Ít khi ta sắp xếp các giá trị đơn lẻ. Thông thường chúng ta sắp xếp một số các mẫu tin chứa một số các trường trên cơ sở trường khóa 19991532 Stevenson Monica 3 Glendridge Ave. 19990253 Redpath Ruth 53 Belton Blvd. 19985832 Kilji Islam 37 Masterson Ave. 20003541 Groskurth Ken 12 Marsdale Ave. 19989932 Carol Ann 81 Oakridge Ave. 20003287 Redpath David 5 Glendale Ave. 19989932 Carol Ann 81 Oakridge Ave. 19985832 Kilji Islam 37 Masterson Ave. 19990253 Redpath Ruth 53 Belton Blvd. 19991532 Stevenson Monica 3 Glendridge Ave. 20003287 Redpath David 5 Glendale Ave. 20003541 Groskurth Ken 12 Marsdale Ave. 19989932 Carol Ann 81 Oakridge Ave. 20003541 Groskurth Ken 12 Marsdale Ave. 19985832 Kilji Islam 37 Masterson Ave. 20003287 Redpath David 5 Glendale Ave. 19990253 Redpath Ruth 53 Belton Blvd. 19991532 Stevenson Monica 3 Glendridge Ave. Theo ID number Theo thứ tự họ tên Sorting Định nghĩa Trong phần này, ta giả sử rằng: Mảng đựợc sử dụng cho cả input và output Tập trung sắp xếp trường khóa và để lại . | Đặt vấn đề Sắp xếp là một quá trình tổ chức lại một dãy các dữ liệu theo một trật tự nhất định Mục đích của sắp xếp là nhằm giúp cho việc tìm kiếm dữ liệu được dễ dàng nhanh chóng Ví dụ: Cho trước một dãy n số nguyên được sắp thứ tự tăng dần Việc tìm kiếm một phần tử x nào đó được thực hiện bằng cách chia đôi dãy ban đầu Chỉ cần k bước ta xác định được phần tử cần tìm Trường hợp xấu nhất Vậy với n = 1000 210 chỉ cần 10 bước là ta xác định được phần tử cần tìm trong dãy 1000 phần tử n = 220 n = 1 tỷ 230 Rõ ràng sắp xếp là một việc làm hết sức cơ bản và được áp dụng rộng rãi trong các kỹ thuật lập trình nhằm xử lý thông tin. Đặt vấn đề Sorting Nội dung Định nghĩa Giả thiết Sắp xếp tại chỗ Chiến lược sắp xếp Tổng quan về thời gian thực hiện Sorting Định nghĩa Sắp xếp là một tiến trình: Tìm một bộ hoán vị trên tập hợp các đối tượng cho trước a1, a2, ., an (ví dụ là các số nguyên), và Trả về một thứ tự khác (a'1, a'2, ., a'n) sao cho a'1 ≤ a'2 ≤ · · · ≤ a'n Ít khi .

Không thể tạo bản xem trước, hãy bấm tải xuống
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.