Cách sắp xếp nào ít lần so sánh nhất
Nhiều người cho rằng việc khử đệ quy của sắp xếp nhanh thực ra không cần thiết, nó chỉ có tác dụng cho những người mới tiếp cận khoa học máy tính hiểu sâu sắc hơn về khái niệm đệ quy. Bản chất của các giải thuật đệ quy là lưu trữ các tham biến đệ quy vào một ngăn xếp (stack) để lần lượt lấy ra xử lý. Show Khi khử đệ quy của giải thuật đệ quy, mỗi lần phân chia danh sách thành 2 danh sách con ta lưu trữ các tham số của danh sách đứng sau vào một ngăn xếp, rồi phân chia tiếp danh sách đứng trước. Giải thuật đơn giản nhất để khử đệ quy của sắp xếp nhanh như sau:
Ưu điểm của sắp xếp nhanh không đệ quy nằm ở những cải tiến của giải thuật trên đây. Có thể cải tiến theo những hướng sau: Cất vào ngăn xếp danh sách con ít phần tử hơn trong hai danh sách con và đối với các danh sách con có độ dài đủ nhỏ thì dùng một phương pháp sắp xếp sơ cấp (chẳng hạn sắp xếp chèn). Quick sort chia ba[sửa | sửa mã nguồn]Một phương pháp chia khác là chia danh sách thành 3 danh sách con, lần lượt nhỏ hơn, bằng và lớn hơn phần tử chốt. Giải thuật Selection Sort là 1 trong các thuật toán sắp xếp kinh điển, cơ bản và dễ hiện thực, là thuật toán được tiếp cận sớm nhất khi bắt đầu học các giải thuật sắp xếp cơ bản. Trong 1 số trường hợp đơn giản, thuật toán này rất hữu hiệu, chẳng hạn với các mảng dữ liệu nhỏ không đòi hỏi phải tối ưu về thời gian. Selection SortÝ tưởngChọn phần tử nhỏ nhất đưa về vị trí đầu tiên của mảng hiện tại và không cần quan tâm đến nó nữa. Khi đó mảng chỉ còn lại Thuật toán Sắp xếp bong bóng là một kỹ thuật sắp xếp dựa trên so sánh, liên tục so sánh các phần tử liền kề và hoán đổi chúng nếu chúng sắp xếp sai thứ tự. Thuật toán tiến hành lặp đi lặp lại cho đến khi toàn bộ danh sách được sắp xếp. Nó có độ phức tạp về thời gian là O(n^2), trong đó n đại diện cho số phần tử trong danh sách. Sắp xếp là quá trình bố trí lại các phần tử trong một tập hợp theo một trình tự nào đó nhằm mục đích giúp quản lý và tìm kiếm các phần tử dễ dàng và nhanh chóng hơn. Tại sao phải sắp xếp?
Các phương pháp sắp xếp thông dụng:
Interchange SortKhái niệm nghịch thế:
Mảng chưa sắp xếp sẽ có nghịch thế Mảng đã có thứ tự sẽ không chứa nghịch thế a[0] <= a[1] <=… <=[n -1] Nhận xét:
Ý tưởng:
Đánh giá:
Bubble SortÝ tưởng:
Đánh giá:
Khuyết điểm:
Insertion SortNhận xét:
Ý tưởng chính:
Đánh giá:
Selection SortNhận xét:
Ý tưởng: mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế:
Đánh giá:
Tạm kếtNhư vậy là mình đã giới thiệu cho các bạn 4 thuật toán sắp xếp thông dụng. Ở phần tới mình sẽ giới thiệu thêm cho các bạn thêm các thuật toán sắp xếp khác. |