Quicksort is widely used, and it is an in situ, unstable sorting algorithm. I’ve always known this noun, but this sort is quick! I can’t tell you why every time I go to an interview. Simply manual implementation again, also thanks to Wang’s column on the beauty of data structures and algorithms. Well ~ O (~ ▽ ~) O really understood for a long time!

First, the idea of quicksort is this: If we want to sort a set of data in an array with subscripts between P and R, we choose any data between P and R as the pivot (partition point).

We go over the numbers between P and R, putting anything less than pivot on the left, anything greater than pivot on the right, and pivot in the middle. After this step, the data in the array p through R is divided into three parts, with p through Q-1 being less than Pivot in the front, pivot in the middle, and q+1 through R being greater than Pivot in the back.

According to the idea of divide-and-conquer and recursion, we can recursively sort the data with subscripts from P to Q-1 and the data with subscripts from q+1 to R until the interval is reduced to 1, indicating that all data are in order.

If we write the above process down using a recursive formula, it looks like this:

Quick_sort (p... R) = quick_sort (p... Q-1) + quick_sort(q+1, rCopy the code

Turn recursive formulas into recursive code.

Quick_sort (A, n) {quick_sort_c(A, 0, n-1)} // Quick_sort_c (A, p,r) {if p >= r then returnQuick_sort_c (A, p, q-1) quick_sort_c(A, q+1, r)}Copy the code

The partition() function needs A lot of extra memory space. In order to implement the quicksort algorithm, the space complexity of the partition() function is O(1). The partition() function can not occupy much extra memory space. R] completes the partitioning operation in place. Meanwhile, the time complexity of quicksort is O(nlogn), the worst case is O(n2), and the space complexity is O(n).

Use Java to implement:

package com.sqt;
import java.util.Arrays;

/ * * *@Description:
 * @author: ListenerSun(male, single) wechat :810548252 *@Date: Created in 2019-12-28 18:47
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {1.8.23.7.3.5};
        quickSort(arr,6);
        System.out.println(Arrays.toString(arr));
    }

    /** * quicksort **@paramArray arr *@paramN Array size */
    public static void quickSort(int[] arr, int n) {
        quickSortPar(arr, 0, n - 1);

    }
    // Quicksort recursive function, p,r are subscripts
    private static void quickSortPar(int[] arr, int p, int r) {
        // when p = r, there is only one element left
        if (p >= r) {
            return;
        }
        // Get partition point subscript
        int q = partition(arr, p, r);
        quickSortPar(arr,p,q-1);
        quickSortPar(arr,q+1,r);

    }

    /** The elements to the left of the partition point are smaller than the elements to the right of the partition point, and vice versa@param arr
     * @param p
     * @param r
     * @return* /
    private static int partition(int[] arr, int p, int r) {
        // Operate directly within the array to save memory space
        // I is used to store the index of the boundary value
        int i = p;
        // Partition the value of the point element
        int pro = arr[r];
        for (int j = p; j < r; j++) {
            if (arr[j] < pro) {
                if (i == j) {
                    // if I == j, this element is the first element, and we need to move I forward one bit
                    i++;
                } else {
                    // Replace arr[j] with arr[I]
                    inttemp = arr[i]; arr[i++] = arr[j]; arr[j] = temp; }}}// Replace arr[r] with arr[I]
        int temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;
        returni; }}Copy the code