Sorting Algorithms:Quick Sort

preface

The blog used for the weak chicken review consolidation, lay a solid foundation, but also hope that the big guy is generous to give advice.

The basic idea

1. For an unsorted sequence, assume that a reference value pivotkey is selected from the elements in the sequence, and the value less than Pivotkey is placed on the left, while the value greater than Pivotkey is placed on the right; 2. Then, with the k as the middle and the partition on the left and right sides as the new sequence, operation 1 is performed again. Because of the use of recursive operations, the performance of quick sorting is not as good as that of direct insert sorting in simple sorting, while the performance impact of the recursion is negligible for the overall performance advantage of the algorithm when sorting a large number of data.

Dynamic figure sample

Quick Sort

Algorithm complexity analysis

On average, The worst The best The stability of Spatial complexity
O(nlogn) O(n^2) O(nlogn) unstable O(logn)

p.s.

  • Worst case: the order to be sorted is positive or reverse order, so that each subsequence after segmentation is one element less than the previous sequence, one is empty. For example, 1, 2, 3, 4, 5 Pivotkey =1; After splitting, one sequence is 2, 3, 4, 5, one is empty, and finally O(n^2).
  • Best case: every split is evenly divided O(nlogn)
  • Average case: O(n*logn) mathematical induction
  • Space complexity: The impact on stack space that results primarily from recursion
  • Best: O (logn)
  • The bad: O (n)
  • Average: O (logn)
  • Stability Instability comparison and exchange occur by leaps

Code implementation 

import java.util.Arrays;

import java.util.Random;



/ * *

 * QuickSort

* 1. For an unsorted sequence, assume that a pivotkey is taken from the elements in the sequence, and place <pivotkey to the left >pivotkey to the right

* 2. Then, with the k as the middle and the partition on the left and right sides as the new sequence, operation 1 is performed again

 * <p>

* Quicksort is not as good as insert sort in simple sorting because it uses recursive operations

* When sorting a large number of data, the performance impact of recursion is negligible for the overall performance advantage of the algorithm

 * <p>

* Time complexity analysis:

* Worst case: the order to be sorted is positive or reverse, so that each subsequence after segmentation is one element less than the previous sequence, one is empty

* If 1, 2, 3, 4, 5 pivotkey=1; After splitting, one sequence is 2, 3, 4, 5 and one is empty

* the end O (n ^ 2)

* Best case: Every split is evenly divided O(n*logn)

* Average case: O(n*logn) mathematical induction

* Space complexity: The impact on stack space is mainly due to the presence of cabinets

* Best: O(logn)

* the worst: O (n)

* Average: O(logn)

* Stability Unstable comparisons and exchanges are performed by jumping

 * <p>

How to base pivotkey properly

* The value has considerable influence on the algorithm. If pivotKey reaches the maximum or minimum value, the algorithm complexity will be increased and performance will be affected

* 1. Random selection: random selection in the sequence to be arranged to reduce the probability of obtaining the maximum or minimum value

* 2. In three-digit selection, select the median of three values at the left end, middle end and right end of the sequence to be arranged to save the time cost of random number generation and reduce the probability of obtaining the maximum or minimum value

* When taking three numbers, the three elements should be rearranged in the middle, small and large order while comparing

* 3. Take the median of nine numbers, sample three times, take three numbers each time, take their median, and then take the median of three medians

* /

public class QuickSort {

    public static void main(String[] args) {

        int[] a = new int[10];

        boolean flag = true;

        //random array

        for (int i = 0; i < a.length; i++) {

            Random rd = new Random();

            a[i] = rd.nextInt(10);

        }



        System.out.println("Random Array :");

        System.out.println(Arrays.toString(a));

        System.out.println();

        System.out.println("Quick Sort :");



        // Quicksort starts

        quickSort(a, 0, a.length - 1);



        System.out.println(Arrays.toString(a));

    }



    / * *

     * @param a

     * @param low

     * @param high

* /

    public static void quickSort(int[] a, int low, int high) {

        // This value defines where to start splitting the sequence

        int pivot;

        // When high-low is greater than a certain value, it is suitable for quicksort

        //if ((high-low) >MAX_LENGTH_INSERT_SORT) the value is 7 or 50

        if (low < high) {

            // The partition method sorts the sequence

            pivot = partition(a, low, high);

            // Split the two sequences to continue the quicksort operation

            quickSort(a, low, pivot - 1);

            quickSort(a, pivot + 1, high);

        }

    }



    / * *

     * @param a

     * @param low

     * @param high

     * @return

* /

    public static int partition(int[] a, int low, int high) {

        // Take the first value of each sequence as the reference value

        int pivotkey = a[low];

        while (low < high) {

            // Start at the right of the sequence and work left until you find an element less than the reference value

            while (high > low && a[high] >= pivotkey) {

                high--;

            }

            // Assign the element directly to the first one on the left, where pivotKey is located

            a[low] = a[high];

            //a[high] = pivotkey;

            // Start from the left side of the sequence and work right until you find an element greater than the reference value

            while (high > low && a[low] <= pivotkey) {

                low++;

            }

            // At this point, a[high]< PivotKey is assigned to the left, so the element can be assigned to A [high].

            a[high] = a[low];

            //a[low] = pivotkey;





        }

        // The last low is where the base value is

        a[low] = pivotkey;

        return low;

    }





}

Copy the code

How to determine the pivotkey properly

  • The value has a significant impact on the algorithm. If pivotKey reaches the maximum or minimum value, the algorithm complexity will be increased and performance will be affected.
  • Random selection, in order to reduce the probability of reaching the maximum or minimum value.
  • In the three-digit selection, select the median of three values at the left end, middle end and right end of the sequence to be arranged to save the time cost of random number generation and reduce the probability of obtaining the maximum or minimum value. When taking three numbers, the three elements should be rearranged in the middle, small and large order while comparing.
  • Take the median of nine numbers, sample three times, take three numbers at a time, take their median, and then take the median of three medians.

reference

GeeksforGeeks：https://www.geeksforgeeks.org/quick-sort/

Top ten classic sorting algorithms: https://www.cnblogs.com/onepixel/articles/7674659.html

Dahua data structure “: https://book.douban.com/subject/6424904/