Sắp xếp nhanh trong Java được giải thích

Quy ước giảm một nửa

Khi số phần tử trong danh sách là số chẵn, việc giảm một nửa danh sách có nghĩa là nửa đầu theo nghĩa đen của danh sách là nửa đầu và nửa sau theo nghĩa đen của danh sách là nửa sau. Phần tử giữa (giữa) của toàn bộ danh sách, là phần tử cuối cùng của danh sách đầu tiên. Điều này có nghĩa là chỉ số ở giữa có độ dài / 2 - 1, vì việc đếm chỉ số bắt đầu từ số không. Độ dài là số phần tử trong danh sách. Ví dụ, nếu số phần tử là 8, thì nửa đầu của danh sách có 4 phần tử và nửa sau của danh sách cũng có 4 phần tử. Đó là tốt. Vì việc đếm chỉ số bắt đầu từ 0 nên chỉ số giữa là 3 = 8/2 - 1.

Còn đối với trường hợp số phần tử trong danh sách hoặc danh sách con là số lẻ thì sao? Khi bắt đầu, độ dài vẫn được chia cho 2. Theo quy ước, số phần tử trong nửa đầu của phép chia này là độ dài / 2 + 1/2. Việc đếm chỉ số bắt đầu từ số không. Chỉ số giữa được cho bởi chiều dài / 2 - 1/2. Đây được coi là thời hạn giữa, theo quy ước. Ví dụ: nếu số phần tử trong danh sách là 5, thì chỉ số ở giữa là 2 = 5/2 - 1/2. Và, có ba phần tử trong nửa đầu của danh sách và hai phần tử trong nửa sau. Phần tử giữa của toàn bộ danh sách là phần tử thứ ba tại chỉ mục, 2, là chỉ mục giữa vì việc đếm chỉ mục bắt đầu từ 0.

Phép chia theo cách này là một ví dụ về số học số nguyên.

Trung vị của ba giá trị

Câu hỏi: Trung vị của dãy số là gì:

C B A

Dung dịch:
Sắp xếp danh sách theo thứ tự tăng dần:

A B C

Số hạng giữa, B, là trung vị. Nó là độ lớn nằm giữa hai độ lớn còn lại.

Tìm kiếm trung vị trong một danh sách không phải là loại như vậy. Ví dụ: trong danh sách 19 phần tử chưa được sắp xếp, có thể yêu cầu giá trị trung vị cho phần tử đầu tiên, phần tử giữa và phần tử cuối cùng. Ba giá trị này có thể không theo thứ tự tăng dần; và do đó, các chỉ số của chúng phải được xem xét.

Với Sắp xếp nhanh, trung vị cho toàn bộ danh sách và danh sách phụ là bắt buộc. Mã giả để tìm giá trị trung bình của ba giá trị cách nhau trong một danh sách (mảng) là:

Thuật ngữ arr có nghĩa là mảng. Đoạn mã này tìm kiếm giá trị trung bình và cũng thực hiện một số phân loại. Đoạn mã này trông đơn giản, nhưng nó có thể khá khó hiểu. Vì vậy, hãy chú ý đến lời giải thích sau:

Việc sắp xếp trong hướng dẫn này sẽ tạo ra một danh sách trong đó giá trị đầu tiên là giá trị nhỏ nhất và giá trị cuối cùng là giá trị lớn nhất. Với bảng chữ cái, A nhỏ hơn Z.

Ở đây, trục chính là trung vị kết quả. Thấp là chỉ số thấp nhất của danh sách hoặc danh sách phụ (không nhất thiết phải có giá trị thấp nhất); high là chỉ số cao nhất của danh sách hoặc danh sách con (không nhất thiết cho giá trị cao nhất), và middle là chỉ số giữa quy ước (không nhất thiết cho giá trị giữa của toàn bộ danh sách).

Vì vậy, giá trị trung bình thu được là giữa giá trị của chỉ số thấp nhất, giá trị của chỉ số giữa và giá trị của chỉ số cao nhất.

Trong mã, chỉ số giữa thông thường được lấy trước. Tại thời điểm bắt đầu, danh sách không được sắp xếp. Việc so sánh và một số sắp xếp lại theo thứ tự tăng dần của ba giá trị sẽ diễn ra cùng một lúc. Câu lệnh if đầu tiên so sánh giá trị cho chỉ mục thấp nhất và giá trị của chỉ mục giữa. Nếu giá trị của chỉ số giữa nhỏ hơn của chỉ số thấp nhất, thì hai giá trị hoán đổi vị trí cho nhau. Thao tác này bắt đầu sắp xếp và thay đổi cách sắp xếp các giá trị trong danh sách hoặc danh sách con. Câu lệnh if thứ hai so sánh giá trị của chỉ mục cao nhất và giá trị của chỉ mục thấp nhất. Nếu giá trị của chỉ số cao nhất nhỏ hơn chỉ số thấp nhất, thì hai giá trị sẽ hoán đổi vị trí cho nhau. Điều này thực hiện một số sắp xếp và thay đổi cách sắp xếp các giá trị trong danh sách hoặc danh sách con. Câu lệnh if thứ ba so sánh giá trị của chỉ mục giữa và giá trị của chỉ mục cao nhất. Nếu giá trị của chỉ số cao nhất nhỏ hơn chỉ số giữa, thì hai giá trị sẽ hoán đổi vị trí cho nhau. Một số phân loại hoặc sắp xếp lại cũng có thể xảy ra ở đây. Điều kiện if thứ ba này không giống như hai điều kiện trước.

Vào cuối ba lần hoán đổi này, giá trị giữa của ba giá trị được đề cập sẽ là A [cao], mà nội dung ban đầu của chúng có thể đã bị thay đổi trong đoạn mã. Ví dụ: hãy xem xét chuỗi không được sắp xếp:

C B A

Chúng ta đã biết rằng trung vị là B. Tuy nhiên, điều này cần được chứng minh. Mục đích ở đây là lấy giá trị trung bình của ba giá trị này bằng cách sử dụng đoạn mã trên. Câu lệnh if đầu tiên so sánh B và C. Nếu B nhỏ hơn C, thì vị trí của B và C phải được hoán đổi. B nhỏ hơn C nên cách sắp xếp mới trở thành:

B C A

Lưu ý, các giá trị cho chỉ số thấp nhất và chỉ số giữa đã thay đổi. Câu lệnh if thứ hai so sánh A và B. Nếu A nhỏ hơn B, thì vị trí của A và B phải được hoán đổi. A nhỏ hơn B, vì vậy cách sắp xếp mới trở thành:

A C B

Lưu ý, các giá trị cho chỉ số cao nhất và chỉ số thấp nhất đã thay đổi. Câu lệnh if thứ ba so sánh C và B. Nếu C nhỏ hơn B, thì vị trí của C và B phải được hoán đổi. C không nhỏ hơn B nên không xảy ra hoán đổi. Sự sắp xếp mới vẫn như trước, đó là:

A C B

B là trung vị, là A [cao], và nó là trục. Vì vậy, trục được sinh ra ở cuối danh sách hoặc danh sách con.

Chức năng hoán đổi

Một tính năng khác cần có của Quick Sort là chức năng hoán đổi. Chức năng hoán đổi, trao đổi giá trị của hai biến. Mã giả cho chức năng hoán đổi là:

Ở đây, x và y chỉ các giá trị thực chứ không phải các bản sao.

Việc sắp xếp trong bài viết này sẽ tạo ra một danh sách trong đó giá trị đầu tiên là giá trị nhỏ nhất và giá trị cuối cùng là giá trị lớn nhất.

Nội dung bài viết

• Thuật toán sắp xếp nhanh
• Mã giả phân vùng
• Minh họa về Sắp xếp nhanh
• Mã hóa Java
• Phần kết luận

Thuật toán sắp xếp nhanh

Cách thông thường để sắp xếp một danh sách không được sắp xếp là xem xét hai giá trị đầu tiên. Nếu chúng không theo thứ tự, hãy đặt chúng theo thứ tự. Tiếp theo, hãy xem xét ba giá trị đầu tiên. Quét hai giá trị đầu tiên để xem giá trị thứ ba khớp ở đâu và lắp nó một cách thích hợp. Sau đó, hãy xem xét bốn giá trị đầu tiên. Quét ba giá trị đầu tiên để xem giá trị thứ tư phù hợp và khớp với nó ở đâu. Tiếp tục với quy trình này cho đến khi toàn bộ danh sách được sắp xếp.

Thủ tục này, còn được gọi là sắp xếp bạo lực, theo cách nói của lập trình máy tính, quá chậm. Thuật toán Sắp xếp nhanh đi kèm với một quy trình nhanh hơn nhiều.

Các bước cho thuật toán quicksort như sau:

1. Đảm bảo có ít nhất 2 số để sắp xếp trong danh sách chưa sắp xếp.
2. Nhận giá trị trung tâm ước tính cho danh sách, được gọi là trục. Trung vị, như được mô tả ở trên, là một cách để có được trục. Những cách khác nhau đi kèm với những ưu điểm và nhược điểm của chúng. - Hẹn gặp lại.
3. Phân vùng danh sách. Điều này có nghĩa là, đặt trục xoay trong danh sách. Theo cách này, tất cả các phần tử ở bên trái nhỏ hơn giá trị tổng hợp và tất cả các phần tử ở bên phải lớn hơn hoặc bằng giá trị tổng hợp. Có nhiều cách phân vùng khác nhau. Mỗi phương pháp phân vùng đi kèm với những ưu điểm và nhược điểm của nó. Phân vùng đang phân chia trong mô hình chia để trị.
4. Lặp lại đệ quy các bước 1, 2 và 3 cho các cặp danh sách con mới xuất hiện cho đến khi toàn bộ danh sách được sắp xếp. Đây là sự chinh phục trong mô hình chia để trị.

Mã giả Sắp xếp Nhanh là:

Mã giả phân vùng

Mã giả phân vùng được sử dụng trong hướng dẫn này là:

Trong hình minh họa về Sắp xếp nhanh bên dưới, mã này được sử dụng:

Minh họa về Sắp xếp nhanh

Hãy xem xét danh sách (mảng) chữ cái chưa được sắp xếp sau:

Q W E R T Y U I O P

Bằng cách kiểm tra, danh sách được sắp xếp là:

E I O P Q R T U W Y

Danh sách được sắp xếp bây giờ sẽ được chứng minh, bằng cách sử dụng thuật toán ở trên và các phân đoạn mã giả, từ danh sách chưa được sắp xếp:

Q W E R T Y U I O P

Trục đầu tiên được xác định từ arr [0] = Q, arr [4] = T và arr [9] = P, và được xác định là Q và được đặt ở cực bên phải của danh sách. Vì vậy, danh sách với bất kỳ sắp xếp hàm xoay nào sẽ trở thành:

P W E R T Y U I O Q

Trục hiện tại là Q. Thủ tục xoay đã thực hiện một số phân loại nhỏ và đặt P ở vị trí đầu tiên. Danh sách kết quả phải được sắp xếp lại (phân vùng), sao cho tất cả các phần tử ở bên trái có giá trị nhỏ hơn, khi đó trục xoay và tất cả các phần tử ở bên phải của trục xoay, bằng hoặc lớn hơn trục xoay. Máy tính không thể thực hiện phân vùng bằng cách kiểm tra. Vì vậy, nó thực hiện bằng cách sử dụng các chỉ mục và thuật toán phân vùng ở trên.

Các chỉ số thấp và cao bây giờ là 0 và 9. Vì vậy, máy tính sẽ bắt đầu quét từ chỉ số 0 cho đến khi nó đạt đến một chỉ mục, có giá trị bằng hoặc lớn hơn pivot và tạm thời dừng lại ở đó. Nó cũng sẽ quét từ đầu cao (bên phải), chỉ số 9, đi xuống, cho đến khi đạt đến chỉ mục có giá trị nhỏ hơn hoặc bằng trục quay và tạm thời dừng lại ở đó. Điều này có nghĩa là hai vị trí dừng. Nếu i, biến chỉ số tăng dần, từ thấp chưa bằng hoặc lớn hơn biến chỉ số giảm, j từ cao, thì hai giá trị này được hoán đổi cho nhau. Trong tình huống hiện tại, việc quét từ cả hai đầu dừng lại ở W và O. Vì vậy, danh sách sẽ trở thành:

P O E R T Y U I W Q

Trục vẫn là Q. Quá trình quét theo các hướng ngược nhau vẫn tiếp tục và dừng lại tương ứng. Nếu i chưa bằng hoặc lớn hơn j, thì hai giá trị mà tại đó quá trình quét từ cả hai đầu đã dừng sẽ được hoán đổi cho nhau. Lần này, quá trình quét từ cả hai đầu dừng lại ở R và I. Vì vậy, sự sắp xếp của danh sách trở thành:

P O E I T Y U R W Q

Trục vẫn là Q. Quá trình quét theo các hướng ngược nhau vẫn tiếp tục và dừng lại tương ứng. Nếu tôi chưa bằng hoặc lớn hơn j, thì hai giá trị tại đó quá trình quét đã dừng, được hoán đổi cho nhau. Lần này, quá trình quét từ cả hai đầu dừng lại ở T đối với i và I đối với j. tôi và j đã gặp nhau hoặc vượt qua. Vì vậy, không thể có sự hoán đổi. Danh sách vẫn giữ nguyên như:

P O E I T Y U R W Q

Tại thời điểm này, trục xoay, Q, phải được đặt ở vị trí cuối cùng của nó trong việc sắp xếp. Điều này được thực hiện bằng cách hoán đổi arr [i] với arr [high], hoán đổi T và Q. Danh sách sẽ trở thành:

P O E I Q Y U R W T

Tại thời điểm này, phân vùng cho toàn bộ danh sách đã kết thúc. Trục = Q đã phát huy hết vai trò của nó. Bây giờ có ba danh sách phụ, đó là:

P O E I Q Y U R W T

Phân vùng là sự phân chia và chinh phục (sắp xếp) trong mô hình. Q ở đúng vị trí sắp xếp của nó. Mọi phần tử bên trái Q đều nhỏ hơn Q, và mọi phần tử bên phải Q đều lớn hơn Q. Tuy nhiên, danh sách bên trái vẫn chưa được sắp xếp; và danh sách bên phải vẫn chưa được sắp xếp. Toàn bộ hàm Sắp xếp nhanh phải được gọi đệ quy để sắp xếp danh sách con bên trái và danh sách con bên phải. Việc thu hồi Quick Sort này phải tiếp tục; danh sách con mới sẽ phát triển cho đến khi toàn bộ danh sách ban đầu được sắp xếp hoàn toàn. Đối với mỗi lần gọi lại chức năng Sắp xếp nhanh, danh sách con bên trái được tham gia đầu tiên trước khi danh sách con bên phải tương ứng được tham dự. Một trục mới phải được lấy cho mỗi danh sách phụ.

Đối với danh sách phụ:

P O E I

Trục (trung vị) của P, O và I được xác định. Trụ sẽ là O. Đối với danh sách con này và liên quan đến danh sách đầy đủ, arr [low] mới là arr [0] và arr [high] mới là arr [i-1] = arr [ 4-1] = arr [3], trong đó tôi là chỉ mục tổng hợp cuối cùng từ phân vùng trước đó. Sau khi hàm pivot () được gọi, giá trị pivot mới, pivot = O. Đừng nhầm lẫn giữa hàm pivot và giá trị pivot. Hàm pivot có thể thực hiện một số phân loại nhỏ và đặt pivot ở cực bên phải của danh sách phụ. Danh sách phụ này trở thành,

I P E O

Với lược đồ này, trục xoay luôn kết thúc ở cuối bên phải của danh sách con hoặc danh sách sau lệnh gọi hàm của nó. Quá trình quét từ cả hai đầu bắt đầu từ arr [0] và arr [3] cho đến khi i và j gặp nhau hoặc chéo nhau. So sánh được thực hiện với pivot = O. Các điểm dừng đầu tiên là ở P và E. Chúng được hoán đổi vị trí và danh sách con mới trở thành:

I E P O

Quá trình quét từ cả hai đầu vẫn tiếp tục, và các điểm dừng mới là P đối với i và tại E đối với j. Bây giờ tôi và j đã gặp nhau hoặc qua lại. Vì vậy, danh sách con vẫn giống như:

I E P O

Việc phân vùng danh sách con hoặc danh sách kết thúc khi trục xoay đã được đưa vào vị trí cuối cùng của nó. Vì vậy, các giá trị mới cho arr [i] và arr [high] được hoán đổi. Tức là P và O đổi chỗ cho nhau. Danh sách phụ mới trở thành:

I E O P

O hiện đang ở vị trí cuối cùng trong toàn bộ danh sách. Vai trò của nó như một trục xoay đã kết thúc. Danh sách phụ hiện được chia thành ba danh sách khác, đó là:

I E O P

Tại thời điểm này, Sắp xếp nhanh của danh sách con bên phải đầu tiên phải được gọi. Tuy nhiên, nó sẽ không được gọi. Thay vào đó, nó sẽ được ghi chú và bảo lưu, sẽ được gọi sau. Khi các câu lệnh của hàm phân vùng đang được thực thi, từ trên cùng của hàm, nó là Sắp xếp nhanh cho danh sách con bên trái phải được gọi ngay bây giờ (sau khi pivot () đã được gọi). Nó sẽ được gọi cho danh sách:

NS

Nó sẽ bắt đầu bằng cách tìm trung vị của I và E. Ở đây, arr [low] = I, arr [mid] = I và arr [high] = E. Vì vậy, trung vị, pivot, nên được xác định bởi thuật toán pivot như , I. Tuy nhiên, mã giả trục ở trên sẽ xác định trục là E. Lỗi này xảy ra ở đây vì mã giả ở trên dành cho ba phần tử chứ không phải hai. Trong phần triển khai bên dưới, có một số điều chỉnh đối với mã. Danh sách phụ trở thành,

E tôi

Trục luôn kết thúc ở cuối bên phải của danh sách con hoặc danh sách sau lệnh gọi hàm của nó. Quá trình quét từ cả hai đầu bắt đầu từ arr [0] và arr [1] dành riêng cho đến khi i và j gặp nhau hoặc chéo nhau. Việc so sánh được thực hiện với pivot = I. Điểm dừng đầu tiên và duy nhất là ở I và E: tại I đối với i và tại E đối với j. Bây giờ tôi và j đã gặp nhau hoặc vượt qua. Vì vậy, danh sách con vẫn giống như:

E tôi

Việc phân vùng danh sách con hoặc danh sách kết thúc khi trục xoay đã được đưa vào vị trí cuối cùng của nó. Vì vậy, các giá trị mới cho arr [i] và arr [high] được hoán đổi. Ở đây xảy ra rằng arr [i] = I và arr [high] = I. Vì vậy, cùng một giá trị được hoán đổi với chính nó. Danh sách phụ mới trở thành:

E tôi

Bây giờ tôi đang ở vị trí cuối cùng trong toàn bộ danh sách. Vai trò của nó như một trục xoay đã kết thúc. Danh sách con hiện được chia thành hai danh sách khác, đó là,

E tôi

Bây giờ, các trục quay cho đến nay là Q, O và I. Các chốt kết thúc ở vị trí cuối cùng của chúng. Danh sách con của một phần tử, chẳng hạn như P ở trên, cũng kết thúc ở vị trí cuối cùng của nó.

Tại thời điểm này, danh sách phụ đầu tiên bên trái đã được sắp xếp hoàn chỉnh. Và thủ tục sắp xếp bây giờ là:

E I O P Q Y U R W T

Danh sách phụ đầu tiên bên phải:

Y U R W T

vẫn cần được sắp xếp.

Chinh phục danh sách phụ bên phải đầu tiên
Hãy nhớ rằng lệnh gọi Sắp xếp nhanh cho danh sách con bên phải đầu tiên đã được ghi chú và dành riêng thay vì được thực thi. Tại thời điểm này, nó sẽ được thực thi. Và do đó, arr [low] = arr [5] = arr [QPivotIndex + 1] mới, và arr [high] mới vẫn là arr [9]. Một tập hợp các hoạt động tương tự đã xảy ra cho danh sách con bên trái đầu tiên sẽ xảy ra ở đây. Và danh sách con bên phải đầu tiên này được sắp xếp thành:

R T U W Y

Và danh sách ban đầu chưa được sắp xếp đã được sắp xếp thành:

E I O P Q R T U W Y

Mã hóa Java

Đặt thuật toán trong Java chỉ là đặt tất cả các đoạn mã giả ở trên vào các phương thức Java trong một lớp. Đừng quên rằng cần phải có một phương thức main () trong lớp sẽ gọi hàm quicksort () với mảng chưa được sắp xếp.

Phương thức pivot ()

Phương thức Java pivot () trả về giá trị, pivot, phải là:

Phương thức swap ()

Phương thức swap () phải là:

Phương thức quicksort ()

Phương thức quicksort () phải là:

Phương thức phân vùng ()

Phương thức partition () phải là:

Phương thức main ()

Phương thức main () có thể là:

Tất cả các phương thức trên có thể được đưa vào một lớp.

Phần kết luận

Sắp xếp nhanh là một thuật toán sắp xếp sử dụng mô hình chia để trị. Nó bắt đầu bằng cách chia một danh sách chưa được sắp xếp thành hai hoặc ba danh sách con. Trong hướng dẫn này, Sắp xếp nhanh đã chia danh sách thành ba danh sách con: danh sách con bên trái, danh sách ở giữa gồm một phần tử duy nhất và danh sách con bên phải. Chinh phục trong Sắp xếp nhanh là phân chia một danh sách hoặc danh sách con trong khi sắp xếp nó, sử dụng giá trị tổng hợp. Hướng dẫn này đã giải thích một cách triển khai Quick Sort trong ngôn ngữ máy tính Java.

Giới thiệu về tác giả

Chrysanthus Forcha

Người khám phá toán học Tích hợp từ các Nguyên tắc đầu tiên và các chuỗi liên quan. Bằng Thạc sĩ về Giáo dục Kỹ thuật, chuyên về Điện tử và Phần mềm Máy tính. BSc Điện tử. Tôi cũng có kiến ​​thức và kinh nghiệm ở cấp độ Thạc sĩ về Máy tính và Viễn thông. Trong số 20.000 nhà văn, tôi là nhà văn xuất sắc thứ 37 tại devarticles.com. Tôi đã làm việc trong các lĩnh vực này hơn 10 năm.

BÀI ĐĂNG GỢI Ý LINUX CÓ LIÊN QUAN

• So sánh các chuỗi trong Java
• Cách sử dụng HashMap trong Java
• Sắp xếp nhanh trong Java được giải thích
• Traversal đặt hàng trước cây nhị phân trong Java
• Giải thích Hợp nhất Sắp xếp trong Java
• Cách sử dụng Máy quét trong Java
• Java ghi vào tệp