Bài viết này tập trung nói về vấn đề sắp xếp trong java - các cách thức để thực hiện, và làm như thế nào để thực hiện sắp xếp một cách chính xác, nhanh và hiệu quả nhất. Bài viết này sử dụng một bài toán, và sẽ đưa ra nhiều hướng giải quyết khác nhau để thực hiện....
Bài toán:

Hãy sắp xếp danh sách các quyển sách, theo số trang sách, và theo các chữ cái đầu tiên tên của tác giả. Cách thức nhập là theo hàng một, một số 0 đến 999 biểu diễn số trang sách, một khoảng trắng, tiếp đến là tên tác giả với 2 kí tự được viết hoa.

Yêu cầu hãy sắp xếp chúng theo số trang, và sau đó sắp xếp theo kí tự đầu tiên kí tự cuối cùng tên của tác giả ấy.
Đầu vào chương trình là nhập một chuỗi, với một số biểu diễn số trang sách. Ta phải viết một phương thức bookOrder để trả về một chuỗi được sắp xếp.

Input:
15 AB 219 AE 518 SE 518 AB 17 CE, 5

Output:
15 AB 17 CE 219 AE 518 AB 518 SE

Cách 1:

Bởi vì trong phép so sánh, đây là cách mất thời gian, nên có lẽ viết nó không hiệu quả, sử dụng bubble sort

PHP Code:
import java.util.*;
public class 
Book{
    public 
String bookOrderString booksint number ){
        
    
int[] pages = new intnumber ];
    
String [] title = new Stringnumber ];
    
StringTokenizer st = new StringTokenizerbooks );

    
// Parsing
    
for ( int cnt 0cnt numbercnt++ ){
        
pages [cnt] = Integer.parseIntst.nextToken() );
        
title [cnt] = st.nextToken();
    }

    
// Bubblesort
    
for ( int i 0numberi++ ){
        for ( 
int j 0number 1j++ ){
        
// This does the actual comparison
        
if ( pages [j] > pages[j+1] || 
            ( 
pages [j] == pages[j+1] && title[j].compareTotitle[j+1] ) > ) ){
            
// Swapping
            
pages [j] ^= pages [j+1];
            
pages [j+1] ^= pages [j];
            
pages [j] ^= pages [j+1];
            
String temp title [j];
            
title [j] = title [j+1];
            
title [j+1] = temp;
        }
        }
    }

    
// Returns it in the format required.    
    
String s "";
    for ( 
int cnt 0cnt numbercnt++ ){
        
+= (int)pages[cnt] + " " title[cnt] + " ";
    }
    
// trim() trims the trailing ( and leading spaces ) in a string.
        
return s.trim();
    }

Cách trên đây phải mất 5 phút để viết, ổn định nhưng lại không được hiệu quả cho lắm. (O(n^2)).

Đoạn mã sau cũng rất khả thi, bởi vì bạn chỉ cần thay đổi câu lệnh sau để sắp xếp theo một cách khác:

PHP Code:
if ( pages [j] > pages [j+1] || 
pages [j] == pages [j+1] && title [j].compareTotitle [j+1] ) > ) ) 
Nếu bạn muốn sắp xếp theo kí tự đầu tiên và sau đó mới đến số trang, ta có thể đơn giản sửa lại như sau:

PHP Code:
if ( title [j].compareTotitle [j+1] ) > ) || 
title [j].compareTotitle [j+1] ) == && pages [j] > pages [j+1] ) ) 
hoặc thay đổi lại dấu nếu muốn sắp xếp giảm dần

PHP Code:
if ( pages [j] < pages [j+1] || 
pages [j] == pages [j+1] && title [j].compareTotitle [j+1] ) > ) ) 
Cách 2:

Cách tốt hơn và hiệu quả hơn là dùng đến hàm Java API. Đây là cách dùng một lớp java.util.Arrays và inteface Comparable:

PHP Code:
import java.util.*;
public class 
Book{
    private class 
implements Comparable {
    
// Fields to be sorted
    
int pages;
    
String title;
    
    
// Initializer
    
public int pString t ){
        
title t;
        
pages p;
    }
    
    
// The required compareTo method.
    
public int compareToObject o ){
        
B k = (Bo;
        if ( 
pages != k.pages ){
        return 
pages k.pages;
        }
        else 
        return 
title.compareTok.title );
    }
    }

    public 
String bookOrderString booksint number ){
    
B[] book = new Bnumber ];
    
StringTokenizer st = new StringTokenizerbooks );

    
// Parsing
    
for ( int cnt 0cnt numbercnt++ ){
        
book [cnt] = new B(Integer.parseIntst.nextToken() ), st.nextToken() ); 
    }
    
    
// Using Arrays.sort
    
Arrays.sortbook );
    
    
// Return it in the format required.
    
String s "";
    for ( 
int cnt 0;cnt number;cnt++ ){
        
+= (int)book [cnt].pages " " book [cnt].title " ";
    }
    return 
s.trim();
    }

Cách này đảm bảo nó chạy trong thời gian O(n*log n), sử dụng quicksort đã sửa đổi. Cái hay nhất trong cách viết mã ở phương pháp này đó là nó sáng sủa hơn nhiều, và nó cũng ít có khả năng sinh lỗi hơn, nếu như bạn để API làm việc.

Ta hãy xem xét nó một cách chi tiết:

PHP Code:
private class implements Comparable 
Đây là một private helper class. Nó cài đặt Comparable để ta có thể so sánh nó sau đó.

PHP Code:
public int compareToObject o ){
    
B k = (Bo;
    if ( 
pages != k.pages ){
    return 
pages k.pages;
    }
    else 
    return 
title.compareTok.title );

Phương thức này là phương thức phải làm việc trong khi so sánh. Bình thường, nó trả về một số nguyên âm nếu đối tượng này nhỏ hơn, một số 0 nếu bằng, và một số nguyên dương nếu như một đối tượng cụ thể là nhỏ hơn.

PHP Code:
Arrays.sortObject[] ) 
Điều này cho phép chúng ta sắp xếp bất cứ thứ gì, nhưng nó yêu cầu tất cả các phần tử trong mảng đó phải được cài đặt Comparable interface. Cũng có nghĩa là nếu bạn đang sắp xếp với các số nguyên, hay số double hoặc String, điều này rất thuận tiện và giúp công việc nhanh hơn.

Cách thức trên thì không khó để làm, và nó không mất nhiều thời gian, nhưng nó làm ta nhớ quá nhiều cú pháp.

Tuy nhiên, đó là cách hay được dùng để sắp xếp các thứ trong Java. Việc tìm hiểu nó có ích rất nhiều trong bài toán sắp xếp nói chung.

Để sửa theo yêu cầu nào muốn sắp xếp theo, đơn giản ta chỉ cẩn thay đổi lại trong phương thức compareTo

PHP Code:
public int compareToObject o ){
    
B k = (Bo;
    if ( 
pages != k.pages ){
    return 
pages k.pages;
    }
    else 
    return 
title.compareTok.title );

và với cách 1, nếu muốn sắp xếp tăng dần, ta viết:

PHP Code:
public int compareToObject o ){
    
B k = (Bo;
    if ( 
pages != k.pages ){
    return 
k.pages pages;
    }
    else 
    return 
title.compareTok.title );

hoặc là theo title first:

PHP Code:
public int compareToObject o ){
    
B k = (Bo;
    if ( 
title.compareTok.title ) != )
    return 
title.compareTok.title );
    else
    return 
pages k.pages
Cách 3:

Có còn cách nào khác không?

Phương pháp này yêu cầu chúng ta xem xét đến các điều kiện biên. Bởi vì Arrays.sort cũng là sắp xếp Strings, chúng ta có thể định dạng lại toàn bộ như là mảng của các String, và sau đó đem sắp xếp:

PHP Code:
import java.util.*;
public class 
Book{
    public 
String bookOrderString booksint number ){
    
StringTokenizer st = new StringTokenizerbooks );
    
String [] book = new Stringnumber ];

    
// Parsing
    
for ( int cnt 0cnt numberi++ ){
        
int pages Integer.parseIntst.nextToken() );
        
String title st.nextToken();

        
/** Format is as following:

         * DDDTTNNNNN
         * Where DDD is the number of pages
         * TT is the initials
         * and NNNNN is the original string
         **/

        
book [cnt] = formatpages ) + title pages " " title;
    }
    
    
// Using Arrays.sort
    
Arrays.sortbook );
    
    
String s "";
    for ( 
int cnt 0cnt numbercnt++ ){
    
// Why 5?  the first 5 characters are throw away letters to be sorted
        
+= book[cnt].substring(5) + " ";
    }
    return 
s.trim();
    }

    
// This pads the number of pages with zeros.
    
String format int pages ){
    
String temp "0000000" pages;
    
// Why 3?  Since it only goes up to 999, we only need the last 3 digits.
    
return temp.substringtemp.length() - );
    }

Theo cách làm việc trên, viết mã rất ngắn, và khá trực giác. Nói chung, tôi khuyên cách thứ 2, nhưng thường thường tôi phải tìm kiếm cú pháp về API, và cách làm này làm tôi tiết kiệm thời gian, và thời gian thì rất quan trọng.

Để thay đổi sắp xếp theo cái gì, đơn giản ta chỉ cần phân tích dòng:

PHP Code:
book[cnt] = formatpages ) + title pages " " title
theo số trang giảm dần:

PHP Code:
book[cnt] = format999 pages ) + title pages " " title
theo chữ cái đầu

PHP Code:
 book [cnt] = title format999 pages ) + pages " " title
theo chữ cái đầu giảm dần:

PHP Code:
book [cnt] = (char) ('Z' - ( title.charAt(0) - 'A' )) + (char) ('Z' - ( title.charAt(1) - 'A' ) +
      
format999 pages ) + pages " " title
Để kiểm tra các phương pháp trên, chúng ta chỉ cần đưa vào phương thức main như sau:

PHP Code:
 public static void mainString [] args )
    {
    
Book a = new Book();
    
System.out.printlna.bookOrder"15 AB 219 AE 518 SE 518 AB 17 CE") );
    } 

View more latest threads same category: