Các Thuật Toán Sắp Xếp Trong Java - VietTuts

Bài tập java - Kiểm tra chuỗi s1 có chứa chuỗi s2 hay không? Bài tập Java - Sắp xếp nổi bọt (Bubble Sort) trong Java

Nội dung chính

• Giải thuật sắp xếp
• Sắp xếp nổi bọt trong Java
• Sắp xếp chọn trong Java
• Sắp xếp chèn trong Java
• Sắp xếp trộn trong Java
• Sắp xếp nhanh trong Java
• Shell Sort trong Java

Giải thuật sắp xếp

Sắp xếp là sắp xếp dữ liệu theo một định dạng cụ thể như theo thứ tự anphabet tăng/giảm dần, theo thứ tự số tăng/giảm dần. Trong khoa học máy tính, giải thuật sắp xếp xác định cách để sắp xếp dữ liệu theo một thứ tự nào đó. Sắp xếp theo thứ tự ở đây là sắp xếp theo thứ tự dạng số hoặc thứ tự dạng chữ cái như trong từ điển.

Tính quan trọng của việc sắp xếp dữ liệu nằm ở chỗ: việc tìm kiếm dữ liệu có thể được tối ưu nếu dữ liệu được sắp xếp theo một thứ tự nào đó (tăng hoặc giảm). Sắp xếp cũng được sử dụng để biểu diễn dữ liệu trong một định dạng dễ đọc hơn.

Mời bạn click chuột vào liên kết sau để xem chi tiết Giải thuật sắp xếp.

Sắp xếp nổi bọt trong Java

Sắp xếp nổi bọt (Bubble Sort) là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.

Mời bạn click chuột vào liên kết sau để xem chi tiết Sắp xếp nổi bọt trong Java .

Sắp xếp chọn trong Java

Giải thuật sắp xếp chọn (Selection Sort) là một giải thuật đơn giản. Giải thuật sắp xếp này là một giải thuật dựa trên việc so sánh in-place, trong đó danh sách được chia thành hai phần, phần được sắp xếp (sorted list) ở bên trái và phần chưa được sắp xếp (unsorted list) ở bên phải. Ban đầu, phần được sắp xếp là trống và phần chưa được sắp xếp là toàn bộ danh sách ban đầu.

Mời bạn click chuột vào liên kết sau để xem chi tiết Sắp xếp chọn trong Java .

Sắp xếp chèn trong Java

Sắp xếp chèn (Insertion Sort) là một giải thuật sắp xếp dựa trên so sánh in-place. Ở đây, một danh sách con luôn luôn được duy trì dưới dạng đã qua sắp xếp. Sắp xếp chèn là chèn thêm một phần tử vào danh sách con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo thứ tự.

Mời bạn click chuột vào liên kết sau để xem chi tiết Sắp xếp chèn trong Java .

Sắp xếp trộn trong Java

Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Conquer). Với độ phức tạp thời gian trường hợp xấu nhất là Ο(n log n) thì đây là một trong các giải thuật đáng được quan tâm nhất.

Đầu tiên, giải thuật sắp xếp trộn chia mảng thành hai nửa và sau đó kết hợp chúng lại với nhau thành một mảng đã được sắp xếp.

Mời bạn click chuột vào liên kết sau để xem chi tiết Sắp xếp trộn trong Java .

Sắp xếp nhanh trong Java

Giải thuật sắp xếp nhanh (Quick Sort) là một giải thuật hiệu quả cao và dựa trên việc chia mảng dữa liệu thành các mảng nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng phần tử của mảng với một phần tử được chọn gọi là phần tử chốt (Pivot): một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và mảng còn lại bao gồm các phần tử lớn hơn hoặc bằng phần tử chốt.

Mời bạn click chuột vào liên kết sau để xem chi tiết Sắp xếp nhanh trong Java .

Shell Sort trong Java

Shell Sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp xếp chèn (Insertion Sort). Giải thuật này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn bên trái).

Đầu tiên, giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. Khoảng cách này còn được gọi là khoảng (interval) – là số vị trí từ phần tử này tới phần tử khác. Khoảng này được tính dựa vào công thức Knuth như sau:

Mời bạn click chuột vào liên kết sau để xem chi tiết Shell Sort trong Java .

Bài tập java - Kiểm tra chuỗi s1 có chứa chuỗi s2 hay không? Bài tập Java - Sắp xếp nổi bọt (Bubble Sort) trong Java