QuickSort là một thuật toán phân chia và chinh phục. Trong mô hình thiết kế thuật toán Chia & Chinh phục, chúng ta chia các bài toán trong các bài toán con một cách đệ quy sau đó giải các bài toán con và cuối cùng kết hợp các lời giải để tìm ra kết quả cuối cùng. Trong bài viết này, chúng tôi sẽ tập trung vào QuickSort In
Các gợi ý sau sẽ được đề cập trong bài viết này,
Hãy bắt đầu nào!
Một điều cần lưu ý khi chia các bài toán thành các bài toán con là cấu trúc của các bài toán con không thay đổi như bài toán ban đầu.
Thuật toán Chia & Chinh phục có 3 bước:
- Chia: Chia vấn đề thành các bài toán con
- Chinh phục: Giải quyết một cách đệ quy các bài toán con
- Kết hợp: Kết hợp các giải pháp để có kết quả cuối cùng
mongodb tạo người dùng cho cơ sở dữ liệu
Có nhiều thuật toán khác nhau dựa trên mô hình phân chia và chinh phục. Sắp xếp nhanh & Sắp xếp hợp nhất nằm trong số đó.
Mặc dù độ phức tạp thời gian trong trường hợp xấu nhất của QuickSort là O (n2), cao hơn nhiều thuật toán sắp xếp khác như Merge Sort và Heap Sort, QuickSort trên thực tế nhanh hơn vì vòng lặp bên trong của nó có thể được triển khai hiệu quả trên hầu hết các kiến trúc và trong hầu hết các dữ liệu trong thế giới thực.
Hãy nói về việc triển khai thuật toán Sắp xếp nhanh. Các thuật toán Quicksort lấy một phần tử pivot và phân vùng mảng xung quanh pivot elememt. Có một số biến thể của Quicksot phụ thuộc vào cách bạn chọn phần tử xoay. Có nhiều cách để chọn phần tử xoay:
java cách sử dụng tostring
- Chọn phần tử đầu tiên
- Chọn phần tử cuối cùng
- Chọn một phần tử ngẫu nhiên
- Chọn phần tử trung bình
Điều quan trọng tiếp theo cần hiểu là, hàm partition () trong thuật toán Sắp xếp nhanh. Chức năng phân vùng để lấy một phần tử xoay, đặt nó ở vị trí bên phải, di chuyển tất cả các phần tử nhỏ hơn phần tử xoay sang trái và tất cả các phần tử lớn hơn sang bên phải của nó. Quicksort cần thời gian tuyến tính để làm như vậy.
Sau đó, mảng được chia thành hai phần từ phần tử pivot (tức là phần tử nhỏ hơn pivot & phần tử lớn hơn pivot) & cả hai mảng đều được sắp xếp đệ quy bằng thuật toán Quicksort.
Bây giờ chúng ta đã hiểu hoạt động của thuật toán QuickSort. Hãy hiểu cách thực hiện thuật toán Quicksort trong Java.
Sắp xếp nhanh chóng Chức năng:
/ * Hàm Quicksort cần sắp xếp mảng với chỉ số thấp nhất & cao nhất * /
void sort (int arr [], int lowIndex, int highIndex) {// Cho đến khi lowIndex = highIndex if (lowIndexBây giờ chúng ta hãy xem mã phân vùng để hiểu nó hoạt động như thế nào.
Vách ngăn Mã
Trong mã phân vùng, chúng tôi sẽ chọn phần tử cuối cùng làm phần tử xoay. Chúng tôi duyệt qua mảng hoàn chỉnh (tức là sử dụng biến j trong trường hợp của chúng tôi). Chúng tôi theo dõi phần tử nhỏ nhất cuối cùng trong mảng (tức là sử dụng biến i trong trường hợp của chúng tôi). Nếu chúng tôi tìm thấy bất kỳ phần tử nào nhỏ hơn trục, chúng tôi di chuyển hoán đổi phần tử hiện tại a [j] với arr [i], nếu không, chúng tôi tiếp tục di chuyển.
int partition (int arr [], int lowIndex, int highIndex) {// Tạo phần tử cuối cùng là pivot int pivot = arr [highIndex] // Sử dụng i để theo dõi các phần tử nhỏ hơn từ pivot int i = (lowIndex-1) for (int j = lowIndex jBây giờ bạn đã hiểu Quicksort & chức năng phân vùng, hãy cùng chúng tôi xem nhanh mã hoàn chỉnh
Sắp xếp nhanh chóng Mã Java
class QuickSort {// Phương pháp phân vùng int partition (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j// Phương pháp sắp xếp
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// Phương thức in mảng
static void printArray (int arr []) {int n = arr.length for (int i = 0 i// Phương thức chính
cuối cùng cuối cùng hoàn thiện trong java
public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('mảng đã sắp xếp') printArray (arr)}} Đầu ra:
Bây giờ sau khi thực hiện chương trình Java trên, bạn đã hiểu cách QuickSort hoạt động và cách triển khai nó trong Java.Vì vậy, chúng ta đã kết thúc bài viết này về 'Quicksort trong Java'. Nếu bạn muốn tìm hiểu thêm,kiểm tra bởi Edureka, một công ty học trực tuyến đáng tin cậy. Khóa học đào tạo và cấp chứng chỉ Java J2EE và SOA của Edureka được thiết kế để đào tạo bạn về cả khái niệm Java cốt lõi và nâng cao cùng với các khung Java khác nhau như Hibernate & Spring.
Có một câu hỏi cho chúng tôi? Vui lòng đề cập đến nó trong phần nhận xét của blog này và chúng tôi sẽ liên hệ lại với bạn trong thời gian sớm nhất.