Java implements quick sort algorithm (Quicktsort)

Introduction to Quick Sort Algorithm
Quick sort and merge sort both use the divide-and-conquer method to design algorithms. The difference is that merge sort divides the array into two sub-arrays of basically equal lengths, and merges them after sorting them respectively. (Merge) operation, and quick sorting is more artistic when splitting subarrays. Take a benchmark element. After splitting, the elements on the left of the benchmark element are smaller than the benchmark element, and the elements on the right are not smaller than the benchmark element. In this way, you only need to separate Just sort the two sub-arrays, and no longer require a merge operation like merge sort. The selection of reference elements has a great impact on the efficiency of the algorithm. The best case is that the two subarrays are basically the same size. For simplicity, we select the last element. A more advanced approach can first find a median and exchange the median with the last element, and then perform the same steps. Splitting is the core of quicksort. The worst-case running time of quick sort is O(n2), but the expected running time is O(nlgn).

Quick Sorting Algorithm Java Implementation
1. Split the array into two subarrays plus a reference element: Select the last element as the reference element, and the index variable records the location of the most recent element that is smaller than the reference element. The position is initialized to start-1. If a new element is found that is smaller than the base element, the index is increased by 1. From the first element to the penultimate element, it is compared with the base element in sequence. If it is less than the base element, the index is increased by 1, and the position index and the element at the current position are exchanged. After the loop ends, index+1 gets the position where the base element should be, and exchanges index+1 with the last element.
2. Sort the two sub-arrays [start, index], and [index+2, end] respectively
Like "Java Implementation of Insertsort", first implement an array tool class. The code is as follows:

public class ArrayUtils {

     public static void printArray(int[] array) {
      System.out.print("{");
      for (int i = 0; i < array.length; i++) {
       System.out.print(array[i]);
       if (i < array.length - 1) {
        System.out.print(", ");
       }
      }
      System.out.println("}");
     }
     public static void exchangeElements(int[] array, int index1, int index2) {
      int temp = array[index1];
      array[index1] = array[index2];
      array[index2] = temp;
     }
    }

The Java implementation and test code of quick sort are as follows:

public class QuickSort {

  public static void main(String[] args) {
   int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
   System.out.println("Before sort:");
   ArrayUtils.printArray(array);
   quickSort(array);
   System.out.println("After sort:");
   ArrayUtils.printArray(array);
  }
  public static void quickSort(int[] array) {
   subQuickSort(array, 0, array.length - 1);
  }
  private static void subQuickSort(int[] array, int start, int end) {
   if (array == null || (end - start + 1) < 2) {
    return;
   }
   int part = partition(array, start, end);
   if (part == start) {
    subQuickSort(array, part + 1, end);
   } else if (part == end) {
    subQuickSort(array, start, part - 1);
   } else {
    subQuickSort(array, start, part - 1);
    subQuickSort(array, part + 1, end);
   }
  }
  private static int partition(int[] array, int start, int end) {
   int value = array[end];
   int index = start - 1;
   for (int i = start; i < end; i++) {
    if (array[i] < value) {
     index++;
     if (index != i) {
      ArrayUtils.exchangeElements(array, index, i);
     }
    }
   }
   if ((index + 1) != end) {
    ArrayUtils.exchangeElements(array, index + 1, end);
   }
   return index + 1;
  }
 }

For more articles related to Java implementation of quick sort algorithm (Quicktsort), please pay attention to the PHP Chinese website!