Tôi đang học Java ở trường ngay bây giờ và chủ đề mới nhất của chúng tôi là sắp xếp các thuật toán trong Java. Cái mà tôi đang cố gắng hiểu là quicksort.Java Quicksort tại sao/giá trị thay đổi ở đâu?
Để hiểu cách thuật toán đó sắp xếp các số trong một mảng, tôi quyết định thực hiện bước mã của mình cho bước trong cửa sổ trình gỡ lỗi Eclipse.
Bây giờ có một bước mà tôi không thể hiểu được ngay cả sau khi trải qua những gì cảm thấy như hàng trăm lần.
mảng ban đầu của tôi là [10, 5, 3, 22, 11, 2]
Khi tôi đi qua các mã chương trình bắt đầu bằng cách trao đổi 10 và 2, sau đó 5 và 3 và sau đó 2 và 2. Tại thời điểm đó, giá trị cho i là 1 và giá trị cho j là -1.
Bây giờ cách tôi nhìn thấy nó là có ba điều kiện
while(i<=j)nào trảfalse, vìi = 1vàj = -1if(left < j)nào trảfalse, vìleft = 0vàj = -1if(i < right)Mà còn trảfalse, vìi = 1vàright = 1
Nhưng tôi ngạc nhiên khi chương trình được cho khung cuối cùng ngay trước khi public static void display chương trình bỏ qua trở lại dòng 40 if(i < right) nhưng đột nhiên các giá trị cho right, i, j và pivot đã thay đổi từ lần lượt là 5, 2, -1 và 3.
Tôi sẽ là rất biết ơn nếu ai đó có thể giải thích lý do tại sao các giá trị được thay đổi.
Tôi cũng đã bổ sung thêm hai hình ảnh mà hiển thị những gì tôi nhìn thấy trên cửa sổ Eclipse của tôi step I don't understand
public class QSort {
public static void quickSort(int[] arr, int left, int right){
int i = left;
int j = right;
int temp;
int pivot = arr[(left+right)/2];
System.out.println("\n\nleft = " + left + "\tright = " + right);
System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")");
while(i <= j){
while(arr[i] < pivot){
System.out.println("i is: " + arr[i] + "(" + i + ")");
i++;
System.out.println("i is: " + arr[i] + "(" + i + ")");
}
while(arr[j] > pivot){
System.out.println("j is: "+ arr[j] + "(" + j + ")");
j--;
System.out.println("j is: "+ arr[j] + "(" + j + ")");
}
if(i <= j){
System.out.println("i is: " + arr[i] + "(" + i + ")");
System.out.println("j is: "+ arr[j] + "(" + j + ")");
System.out.println("Swapped " + arr[i] + "(" + i + ")"+ " with " + arr[j] + "(" + j + ")");
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
System.out.println("i is: (" + i + ")");
System.out.println("j is: (" + j + ")");
System.out.println("Pivot is: " + pivot + "(" + (left+right)/2 + ")");
}
}
if(left < j){
System.out.println("j is: (" + j + ")");
quickSort(arr, left, j);
}
if(i < right){
System.out.println("i is: (" + i + ")");
quickSort(arr, i, right);
}
}
public static void display(int[] arr){
if(arr.length > 0){
System.out.print(arr[0]);
}
for(int i = 1; i < arr.length; i++){
System.out.print(", " + arr[i]);
}
}
public static void main(String[] args) {
int[] data = new int[]{10,5,3,22,11,2};
System.out.println("Before: ");
display(data);
quickSort(data, 0, data.length-1);
System.out.println("\nAfter: ");
display(data);
}
}
Cảm ơn rất nhiều!
Bạn có thể muốn có một sneek @ [Java Thực hiện sắp xếp nhanh] (http://codereview.stackexchange.com/questions/4022/java-implementation-of-quick-sort) – Abhijeet