Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thuật toán sắp xếp nhanh trong Java, cài đặt Quick Sort Java
Trong bài này mình sẽ giới thiệu đến các bạn thuật toán sắp xếp nhanh (Quick Sort). Đây là một trong những thuật toán sắp xếp trong Java.
Chúng ta sẽ cùng nhau tìm hiều về Quick Sort là gì và cách triển khai thuật toán Quick Sort trong Java. Ở cuối bài viết, mình sẽ giải một bài toán cụ thể để các bạn hiểu hơn về cách áp dụng thuật toán trong thực tế.
Thuật toán Quick Sort trong Java
Quick Sort là một thuật toán sắp xếp dựa trên giải thuật Divide and Conquer (Chia để trị) khá giống với Merge Sort
Thuật toán sẽ chọn mốt phần tử trong mảng làm điểm đánh dấu (pivot). Khi chọn được điểm đánh dấu, nó sẽ chia mảng thành hai mảng con bằng cách so sánh với pivot đã chọn. Một mảng bao gồm các phần tử nhỏ hơn hoặc bằng pivot và mảng còn lại sẽ lớn hơn hoặc bằng pivot.
Bài viết này được đăng tại [free tuts .net]
Tốc độ sắp xếp của thuật toán tùy thuộc vào việc lựa chọn pivot, có một số cách chọn như sau:
- Chọn phần tử đầu tiên của mảng.
- Chọn phần tử cuối cùng của mảng.
- Chọn phần tử có giá trị nằm giữa mảng.
- Chọn Random một phần tử của mảng.
Trên đây là một số cách chọn thông dụng, được sử dụng nhiều nhất. Tùy thuộc vào bài toán mà ta chọn pivot cho phù hợp.
Để dễ hình dung thì chúng ta cùng xem ví dụ sau đây.
Ví dụ minh họa cho thuật toán Quick Sort trong Java
Khi chúng ta chọn số 3 làm pivot, thì mảng được chia làm hai phần. Phần bên trái nhỏ hơn hoặc bằng 3, phần bên phải lớn hơn hoặc bằng 3, cả hai phần đều được sắp xếp tằng dần.
Tiếp tục chọn pivot cho mỗi phần. Phần bên trái có pivot là số 1 và phần bên phải có pivot là số 6.
Cứ như vậy chúng ta sẽ chia phần ra cho đến khi không chia được nữa và sắp xếp theo đúng thứ tự.
Chương trình triển khai thuật toán Quick Sort trong Java
Bây giờ hãy xem đoạn code mà freetuts triển khai dưới đây để hiểu được thuật toán này nhé.
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {9, -3, 5, 2, 6, 8, -6, 1, 3};
System.out.println("Học lập trình miễn phí tại freetuts");
System.out.println("Mảng ban đầu:");
printArray(arr);
quickSort(arr, 0, arr.length - 1);
System.out.println("Mảng sau khi dùng Quick Sort:");
printArray(arr);
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
Giải thích:
- Hàm
quickSortsử dụng đệ quy để chia mảng thành các mảng con và sắp xếp các mảng con đó. - Hàm
partitionlấy phần tử cuối cùng của mảng làm pivot, di chuyển tất cả các phần tử nhỏ hơn pivotvề bên trái của pivot, và di chuyển các phần tử lớn hơn pivotvề bên phải của pivot. Cuối cùng, nó đưa pivot vào giữa các phần tử đã sắp xếp. - Hàm
swapđược sử dụng để đổi chỗ hai phần tử trong mảng. - Hàm
printArrayđược sử dụng để in mảng ra màn hình.
Kết quả:
Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp các phần tử trong mảng, sử dụng thuật toán Quick Sort trong Java. Cũng như kết thúc phần giới thiệu và hướng dẫn triển khai thuật toán Quick Sort trong Java. Chúc các bạn thực hiện thành công!!!
