​​

The opening is introduced

Hello everyone, the public account [Java Geek Mind] will soon sort out some Java high frequency interview questions to share with partners, also hope to see partners in the job search process can be enough! This section shares the implementation of Java quicksort algorithm.

First, take a look at the dynamic diagram of the implementation of quicksort:

​

Quicksort introduction:

Quicksort, according to the textbook, is an improvement on bubble sort.

Quick sort, with an array to sort, and three variables to find:

  • Pivot value

  • Left value

  • Right value

With pivot adjustment, the array is divided into three parts:

  • Part 1: Pivot, a single number, in the “center” of each order;

  • Part 2: The left array (part of array) that is “to the left” of the first pivot value (pivot value), where each value in the left array (not necessarily sorted, but possibly out of order) is smaller than the pivot value and the right array;

  • Part 3: The right-side array (part of array) that is “right” of the first pivot value, where each value in the right-side array (not necessarily sorted, but possibly out of order) is greater than the pivot value and the left-side array

That’s the first step in quicksort, separating the array from the left, central, and right.

Then according to the recursive idea, the left array, the central value, the right array recursive loop operation, constantly split out of three parts, and finally achieve the effect of quick sorting.

Core logic:

​

Recursive call of fast sorting algorithm:

​

Next, attach the complete implementation code:

Public class QuickSort {/** * QuickSort call method ** @param ary array to be sorted * @param left rvalue * @param right rvalue * @return int value * @author Cansluck */ public static int getSortNum(int[] ary, int left, int right) {// Define a pivot value that is equal to the left value of the array. Int pivot = ary[left]; While (left < right) {// ary[right] > pivot While (left < right &&ary [right] >= pivot) {right--; Pivot = pivot; pivot = pivot; pivot = pivot; pivot = pivot; pivot = pivot; pivot = pivot; While (left < right && ary[left] <= pivot) {left++; // If the above loop does not meet the conditions, then one of the values in the left array is greater than the pivot value (pivot value), then replace it with the right array ary[right] = ary[left]; Ary [left] = pivot; ary[left] = pivot; // return left; } /** * quick sort recursive method ** @author Cansluck * @param ary array * @param left rvalue * @param right rvalue */ public static void QuickSort (int[] ary, int left, int right) {// Define pivot value int pivot; Pivot = getSortNum(ary, left, right); pivot = getSortNum(ary, left, right); // Recursively call quickSort(ary, left, pivot - 1) on the left array according to pivot value (pivot value); // Recursively call quickSort(ary, pivot + 1, right) on the right array according to the pivot value (pivot); } } public static void main(String[] args) { int[] ary = {97, 58, 12, 88, 77, 22, 33, 44, 66, 22}; quickSort(ary, 0, ary.length - 1); for (int i = 0; i < ary.length; i++) { if (i ! = ary.length - 1) System.out.print(ary[i] + ", "); else System.out.println(ary[i]); }}}Copy the code

Above is the detailed introduction and complete implementation of quicksort. If you are interested, you can do it yourself

Focus, don’t get lost

If you think the article is good, please pay attention to it, like it, and save it. Your support is the motivation for my creation. Thank you all.

If there is a problem with the article, please don’t be stingy, welcome to point out the message, I will check and modify in time.

If you want to know more about me, you can search “Java Geek thinking” on wechat to follow me. Every 8:00 on time push technical articles, so that your way to work is not lonely, and there are monthly book activities, to help you improve hard power!