Click “programmer small Grey” above, choose to pay attention to the public account
Interesting and meaningful articles are delivered at the first time!
————— the next day —————
public class QuickSort {
-
public static void quickSort(int[] arr, int startIndex, int endIndex) {
-
// End recursion condition: startIndex is equal to endIndex
-
if (startIndex >= endIndex) {
-
return;
-
}
-
// Get the base element position
-
int pivotIndex = partition(arr, startIndex, endIndex);
-
// Divide and conquer two parts of a recursive sequence
-
quickSort(arr, startIndex, pivotIndex – 1);
-
quickSort(arr, pivotIndex + 1, endIndex);
-
}
-
-
-
private static int partition(int[] arr, int startIndex, int endIndex) {
-
// Take the element in the first position as the base element
-
int pivot = arr[startIndex];
-
int left = startIndex;
-
int right = endIndex;
-
// The position of the pit, initially equal to the position of pivot
-
int index = startIndex;
-
-
// The major loop ends when the left and right Pointers overlap or interlace
-
while ( right >= left ){
-
// The right pointer is compared from right to left
-
while ( right >= left ) {
-
if (arr[right] < pivot) {
-
arr[left] = arr[right];
-
index = right;
-
left++;
-
break;
-
}
-
right–;
-
}
-
// The left pointer is compared from left to right
-
while ( right >= left ) {
-
if (arr[left] > pivot) {
-
arr[right] = arr[left];
-
index = left;
-
right–;
-
break;
-
}
-
left++;
-
}
-
}
-
arr[index] = pivot;
-
return index;
-
}
-
-
-
public static void main(String[] args) {
-
Int [] arr = new int[] {4,7,6,5,3,2,8,1};
-
quickSort(arr, 0, arr.length-1);
-
System.out.println(Arrays.toString(arr));
-
}
}
public class QuickSort {
-
public static void quickSort(int[] arr, int startIndex, int endIndex) {
-
// End recursion condition: startIndex is equal to endIndex
-
if (startIndex >= endIndex) {
-
return;
-
}
-
// Get the base element position
-
int pivotIndex = partition(arr, startIndex, endIndex);
-
// Sort by base element recursively
-
quickSort(arr, startIndex, pivotIndex – 1);
-
quickSort(arr, pivotIndex + 1, endIndex);
-
}
-
-
-
private static int partition(int[] arr, int startIndex, int endIndex) {
-
// Take the element in the first position as the base element
-
int pivot = arr[startIndex];
-
int left = startIndex;
-
int right = endIndex;
-
-
while( left ! = right) {
-
// Control the right pointer to compare and move to the left
-
while(left<right && arr[right] > pivot){
-
right–;
-
}
-
// Control the right pointer to compare and move right
-
while( left<right && arr[left] <= pivot) {
-
left++;
-
}
-
// Swap left and right elements
-
if(left<right) {
-
int p = arr[left];
-
arr[left] = arr[right];
-
arr[right] = p;
-
}
-
}
-
-
// Pivot and pointer overlap point switch
-
int p = arr[left];
-
arr[left] = arr[startIndex];
-
arr[startIndex] = p;
-
-
return left;
-
}
-
-
-
public static void main(String[] args) {
-
Int [] arr = new int[] {4,7,6,5,3,2,8,1};
-
quickSort(arr, 0, arr.length-1);
-
System.out.println(Arrays.toString(arr));
-
}
}
Compared with the digging method, the pointer swap method performs fewer element swaps in the partition method.
Let’s look at the code below:
public class QuickSortWithStack {
-
public static void quickSort(int[] arr, int startIndex, int endIndex) {
-
// Use a collection stack instead of a recursive function stack
-
Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();
-
// Start and end indices of the entire sequence are hashed into the stack
-
Map rootParam = new HashMap();
-
rootParam.put(“startIndex”, startIndex);
-
rootParam.put(“endIndex”, endIndex);
-
quickSortStack.push(rootParam);
-
-
// The loop ends when the stack is empty
-
while (! quickSortStack.isEmpty()) {
-
// The top element goes off the stack to get the start and end indices
-
Map<String, Integer> param = quickSortStack.pop();
-
// Get the base element position
-
int pivotIndex = partition(arr, param.get(“startIndex”), param.get(“endIndex”));
-
// Divide the base element into two parts and push the start and end indices of each part onto the stack
-
if(param.get(“startIndex”) < pivotIndex -1){
-
Map<String, Integer> leftParam = new HashMap<String, Integer>();
-
leftParam.put(“startIndex”, param.get(“startIndex”));
-
leftParam.put(“endIndex”, pivotIndex -1);
-
quickSortStack.push(leftParam);
-
}
-
if(pivotIndex + 1 < param.get(“endIndex”)){
-
Map<String, Integer> rightParam = new HashMap<String, Integer>();
-
rightParam.put(“startIndex”, pivotIndex + 1);
-
rightParam.put(“endIndex”, param.get(“endIndex”));
-
quickSortStack.push(rightParam);
-
}
-
}
-
}
-
-
private static int partition(int[] arr, int startIndex, int endIndex) {
-
// Take the element in the first position as the base element
-
int pivot = arr[startIndex];
-
int left = startIndex;
-
int right = endIndex;
-
-
while( left ! = right) {
-
// Control the right pointer to compare and move to the left
-
while(left<right && arr[right] > pivot){
-
right–;
-
}
-
// Control the right pointer to compare and move right
-
while( left<right && arr[left] <= pivot) {
-
left++;
-
}
-
// Swap left and right elements
-
if(left<right) {
-
int p = arr[left];
-
arr[left] = arr[right];
-
arr[right] = p;
-
}
-
}
-
-
// Pivot and pointer overlap point switch
-
int p = arr[left];
-
arr[left] = arr[startIndex];
-
arr[startIndex] = p;
-
-
return left;
-
}
-
-
public static void main(String[] args) {
-
Int [] arr = new int[] {4,7,6,5,3,2,8,1};
-
quickSort(arr, 0, arr.length-1);
-
System.out.println(Arrays.toString(arr));
-
}
}
Compared to the recursive implementation, the code changes are only in the quickSort method. In this method, a stack of Map type elements is introduced to store the starting and ending subscripts for each swap.
Each time through the loop, the top element is removed from the stack, sorted, and divided into left and right parts according to the position of the base element, which are pushed into the stack separately. When the stack is empty, the sorting is complete and the loop exits.
