The profile

Quicksort, proposed by C. A. R. Hoare in 1960, is one of the most commonly used classical sorting algorithms among the eight sorting algorithms. The main reason for its wide application is high efficiency, and the core algorithm idea is divide and conquer. Quicksort is often examined as an interview question, and is usually examined in terms of the idea of quicksort, handwritten quicksort of coding practice, and further optimization of quicksort. In fact, the Sort method of the Arrays class in the Java standard library also uses the optimized quicksort algorithm. It is very important to know how to get started with data structures and algorithms.

The principle of

Quick sort the core idea is divided: choose a number in an array as a base, a trip through sort to sort data split into separate two parts, one part of all the number of smaller than base, another part of the all number is larger than the base, and then of the two parts data respectively according to the method of quick sort, cycle recursion, eventually make the whole array orderly.

Base to choose

Because quicksort needs to select a radix for sorting, there are many ways to select radix, and the radix selection is directly related to the efficiency of quicksort. In fact, the selection of the base element should follow the principle of balancing the subproblem: even if the length of the two subsequences is the same, the first element of the sorted array will be used as the base. This article illustrates the principle of quicksort using the first element of an array as the radix.

A trip to the sorting

Int n[] = {6, 5, 2, 7, 3, 9, 8, 4, 10, 1}

  • 1. I searches from left to right for the first digit greater than the base (6), j searches from right to left for the first digit less than the base (6);

  • 2. Swap the two numbers when you find them. Continue cyclic switching until I >=j completes the loop;

  • 3. The final pointer I =j, then the array can be divided into three parts less than base (6)/base (6)/larger than base (6) by exchanging the base and the number pointed to by I (j), that is, to complete a quick row;

Pseudo code

See coding notes

Coding practices

public class Test {

	public static void main(String[] args) {
		int n[] = { 6.5.2.7.3.9.8.4.10.1 };
		quicksort(n);
		System.out.print("Quick row result:");
		for (int m : n) {
			System.out.print(m + ""); }}public static void quicksort(int n[]) {
		sort(n, 0, n.length - 1);
	}

	public static void sort(int n[], int l, int r) {
		if (l < r) {
			// A quick row and return the index of the swapped radix
			int index = patition(n, l, r);
			// Recursively sort the array to the left of the cardinality
			sort(n, l, index - 1);
			// Recursively sort the array to the right of the cardinality
			sort(n, index + 1, r); }}public static int patition(int n[], int l, int r) {
		// p is the cardinality, which is the first number in the array to be sorted
		int p = n[l];
		int i = l;
		int j = r;
		while (i < j) {
			// Find the first number that is less than the cardinality from right to left
			while (n[j] >= p && i < j) {
				j--;
			}
			// Find the first number greater than the cardinality from left to right
			while (n[i] <= p && i < j) {
				i++;
			}
			// Switch the two numbers
			swap(n, i, j);
		}
		// divide the numbers on both sides of the cardinality
		swap(n, l, i);
		return i;
	}

	private static void swap(int n[], int i, int j) {
		inttemp = n[i]; n[i] = n[j]; n[j] = temp; }}Copy the code
  • The results of
Quick sorting result: 1 2 3 4 5 6 7 8 9 10Copy the code

conclusion

This article explains the core idea and concrete implementation of quicksort, one of the eight kinds in the simplest form. Quicksort is the most frequent sorting algorithm relative to other kinds. As for the eight sorting algorithms, the recommended zero-based learning route is to understand the algorithm idea before coding practice. Finally, if you found this article inspiring or helpful, keep an eye on the 0.0 wave