Writing in the front

  • Sorting classical sorting algorithm
  • Record learning

1. QuickSort

1.1 concept

Quicksort mainly adopts the basic idea of divide and conquer. Each time the data in a position is repositioned, all the data on the left of the number is smaller than the number, and all the data on the right is larger than the number. Then, the left and right sides of the data that has been repositioned are fast-sorted again, so as to realize the repositioning of all the data.

1.2 Algorithm Description

  1. Pick an element from the sequence, called a reference (temp),
  2. Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition ends, the benchmark is in the middle of the array. This is called a partition operation.
  3. There is a recursive correlation between subarrays of values less than the reference element and those of values greater than the reference element.

Schematic diagram

1.3 Code Demonstration

package com.zhuang.algorithm;

import java.util.Arrays;

/ * * *@Classname QuickSort
 * @DescriptionQuicksort@Date2021/6/13 parts: *@Created by dell
 */

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5.2.4.8.1.9.3.15};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Divide the array into two parts
            int index = getIndex(arr, low, high);
            // Sort the left subarray recursively
            quickSort(arr, low, index - 1);
            // Sort the right subarray recursively
            quickSort(arr, index + 1, high); }}public static int getIndex(int[] arr, int low, int high) {
        / / benchmark temp
        int temp = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= temp) {
                high--;
            }
            // Swap records larger than the baseline to the left end
            arr[low] = arr[high];
            while (low < high && arr[low] <= temp) {
                low++;
            }
            Swap records smaller than the baseline to the right end
            arr[high] = arr[low];
        }
        // The scan is complete and the benchmark is in place
        arr[low] = temp;
        // return the base position
        returnlow; }}Copy the code

1.4 Algorithm Analysis

  • Best case: T(n) = O(nlog^n^)
  • Worst case: T(n) = O(n^2^)
  • Average case: T(n) = O(nlog^n^)

1.5 stability

Quicksort is not stable. This is because we cannot guarantee that equal data will be scanned and stored sequentially.

1.6 Application Scenarios

Quicksort works in most cases, especially when there is a large amount of data. But when necessary, consider optimizations to improve its performance in the worst case

Write in the last

  • Learning stage, improper description, please also point out in the comments section
  • Keep it up!