Sắp xếp nhanh trong java

Trong học lập trình java cơ bản sắp xếp kiểu phân đoạn(partition sort) hay sắp xếp nhanh(quick sort.) là một cải tiến của việc sắp xếp đổi chỗ, người sang lập ra nó là C.A.R.Hoare và được gọi là phương pháp sắp xếp nhanh.

- Nguyên tắc của phương pháp sắp xếp này:

Chọn một khóa ngẫu nhiên nào đó trong dãy làm khóa chốt.Mọi phần tử nhỏ hơn chốt thì ta đặt phần tử đó trước chốt, các phần tử sau chốt thì ta đặt các phần tử ở phía sau chốt
Dãy sau khi thực hiện sẽ phân thành 2 đoạn, một đọa trước chốt sé nhỏ hơn chốt và một đoạn sau chốt sẽ lớn hơn chốt.
Các lượt tiếp theo cũng áp dụng kĩ thuật tương tự đối với các phân đoạn còn lại.
Xử lý một phân đoạn và ghi nhớ một phân đoạn cho đến khi chỉ còn một phần tử.

*Ví dụ:

Cho dãy số 1,3,7,2,4,6,9,8,5. Ta sẽ sắp xếp theo phương pháp này:
Gọi số đầu dãy là chốt, là số 1
Để thể hiện việc phân đoạn như trên bằng một thủ tục Partition(A,Bt,Bd,j) Bt là biên trên, Bd là biên dưới, A là vecto biểu diễn dãy khóa đã cho, j là chỉ số ứng với khóa chốt sau khi đã tách dãy khóa thành 2 đoạn.
Ý tưởng để thực hiện thủ tục Partition :
• Đưa vào một khóa giả để khống chế biên trên A[n+1] khóa này lớn hơn tất cả các số trong dãy.
• Hai chỉ số i,j để duyệt dãy khóa theo chiều ngược nhau.
• I = Bd +1 ; j = Bt ;
• I sẽ được tăng đến chừng nào mà A > A[Bd] (Chốt) thì thôi, tiếp theo đó là j sẽ giảm giá trị tới khi A[j] < chốt thì thôi, nếu lúc đó i bé hơn j thì ta sẽ đổi chỗ A và A[j], cho tới khi i>j thì đổi chỗ A[j] với A[Bd]. Phân đoạn sẽ kết thúc.

• Code thuật toán :

Procedure PARTITION(A,Bd,Bt)
I= Bd+1
J= Bt
While(i<=j)
{
While(A<A[Bd]) { i=i+i}
While(A[j]>A(Bt)) {j=j-1}
If i<j then đổi chỗ A và A[j]
I=i+1
J=j-a
}
Đổi chỗ A(Bd) và A[j]

- Chuương trình chạy chính: ( Viết theo giải thuật đệ qui)
procedur Quick_Sort(a[],Bd,Bt)
if Bd<Bt
call PARTITION(a[],Bd,Bt)
call Quick_sort(a[],Bd,j-1)
call Quick_Sort(a[], Bd, j+1).
Ví dụ bằng java code:

PHP:

if (l<r){



    int v = a[(l+r)/2]; //chọn phần tử đầu là chốt

    int i = l+1;

    int j = r;

    int temp;

   while (i<=j){

        while (a[i] < v) i++; //tìm phần tử phía đầu đoạn mà ≥ v

        while (a[j] > v) j--; //tìm phần tử phía cuối đoạn mà ≤ v

        //lúc này: a[i] ≥ v ≥ a[j]

        if (i<=j)

        {

            if (i<j)

            {

                temp = a[i];

                a[i] = a[j];

                a[j] = temp;

            }

*Chú ý:

- Nên chọn khóa chốt là phần tử ở giữa dãy sẽ thuân lợi hơn rất nhiều, tránh trường hợp vào phần tử nhỏ nhất hay phần tử lớn nhất lúcdđó thời gian sẽ không thể nhanh được nữa.
- Sau một số bước thực hiện khi chia thành các đoạn nhỏ hơn ta nên kết hợp với một số kiểu sắp xếp khác để được hiệu quả cao nhất về tốc độ.( Tùy biến thực hành nhiều các bạn sẽ có thêm kĩ năng )