The Good Programmer Java tutorial teaches you about quicksort in 5 minutes.

Quicksort is a kind of sorting algorithm that is often asked in interviews, and the average time of quicksort is relatively small compared to some other sorting algorithms.

Introduction to quicksort idea

Quicksort uses the idea of divide-and-conquer. Through a round of sorting, a sequence can be divided into two independent parts, one part of which is smaller than the base value, and the other part of which is larger than the base value. Then the sequence of the two parts is sorted according to the same algorithm until the whole sequence is in order.

The following sequence ARR is taken as an example to illustrate the basic algorithm of quicksort



The value 23 in the first position is used as the base value and is compared from the right, if ARr [high]>base,high moves forward.



Arr [high]<base,arr[low]=arr[high], then low moves back



Arr[low]<base, not swapped, low moved later

Arr[low]>base, Arr[high]= Arr[low], high forward



Arr[high]<base, Arr[low]=base, Arr[low]=base,



Low and high point to the same place,

Assign the base data to the same position as low and high point to, and the comparison ends. Then, the data before 23 and the data after 23 are compared and sorted according to the above algorithm respectively, and so on until all elements are in order.



Quicksort code implementation

Since all subsequences are sorted by the same algorithm, the recursive idea can be used to achieve quick sorting

  1. package com.qfedu.vo;
  3. public class QuickSort {
  4. public static void quickSort(int[] arr,int low,int high){
  5. int i,j,temp,t;
  6. if(low>high){
  7. return;
  8. }
  9. i=low;
  10. j=high;
  11. // Temp Specifies the number of storage benchmarks
  12. temp = arr[low];
  14. while (i<j) {
  15. // Start from the right side of the development judge, the condition is true, high decreases left
  16. while (temp<=arr[j]&&i<j) {
  17. j–;
  18. }
  19. arr[i]=arr[j];
  20. // From the left, low increases to the right
  21. while (temp>=arr[i]&&i<j) {
  22. i++;
  23. }
  24. arr[j]=arr[i];
  25. arr[i]=temp;
  27. }
  28. // Recursively calls the content on the left to sort
  29. quickSort(arr, low, j-1);
  30. // Recursively call the content on the right to sort
  31. quickSort(arr, j+1, high);
  32. }
  35. public static void main(String[] args){
  36. 15,23,7,87,34,56 int [] arr = {};
  37. quickSort(arr, 0, arr.length-1);
  38. for (int i = 0; i < arr.length; i++) {
  39. System.out.println(arr[i]);
  40. }
  41. }
  42. }

conclusion

The above is the introduction of ordinary quicksort, for quicksort, there are some improved algorithms, which can further improve the execution efficiency.