Introduction to algorithm

Learning objective: Master the principles and ideas of ten sorting algorithms

Sorting algorithm

What is sorting algorithm

A Sorting algorithm is an algorithm that sorts a stream of data in a specific way.

Second, the sorting algorithm needs to follow the principle

  1. The output is an increasing sequence (increasing in terms of the desired sort order)
  2. The output is a permutation or reorganization of the original input

Three, sorting algorithm of several kinds of classification

  1. By time complexity, by the size of the list (n)

    For a sorting algorithm:

    1. Worst performance: O(n^2)
    2. Best performance: O(n log n)
    3. Ideal performance: O(N)

  2. Memory usage: The space dimension is one of the tricks

  3. The stability of

    1. A stable sorting algorithm will allow an ordered sequence to remain sorted, assuming the following sequence

      {(4,1), (3,1), (3,7), (5,6)} needs to be sorted by the first number

      The stable sorting algorithm order is as follows: {(3,1), (3,7), (4,1), (5,6)}

      The unstable sort algorithm order may be as follows: {(3,7), (3,1), (4,1), (5,6)}

  4. According to the sorting method

    1. Insertion sort, swap sort, selection sort, merge sort, radix sort….

Talk about time complexity

What is time complexity

In computer science, the time complexity of an algorithm is a function that describes the running time of the algorithm

How to express the time complexity of an algorithm

Time complexity: in big O notation, when it comes to time complexity, there’s something called time frequency

What is time frequency: The number of statements executed in an algorithm is called statement frequency or time frequency. Notes for T (n). The number of times the algorithm statement is executed is directly proportional to the time taken, then T(n) = O(f(n))

For example, there is an algorithm that uses a double-layer for loop. Both of these cycles end up at n. Then we can say that the time frequency of this algorithm is T(n) = O(n^2), and the time complexity is O(n^2).

3. Classification of time complexity

Common algorithms in descending order of time complexity are as follows: Constant step TWO (1) < log step two (LOGnn) < Linear step two (n) < Linear step two (NLOGnn) < square step two (N ^2) < cube step two (N ^3) < exponential step two (2^n)

Iv. Introduction of time complexity

  • Constant order O(1) : it can be said that there is no complex structure such as loop, == the number of code execution depends on the number of lines of code ==

  • Log order two (lognN) : No matter how large N is, the number of times of executing code == depends on the small N == in the middle. Log order greatly reduces the number of times of executing code. If the small N is 1, this step is meaningless

    private static void m(int n){
    int i = 1;
    while (i <= n){
        i = i * 2; }}Copy the code

    So if you look at the code above, regardless of what the function is, as the number 2 gets bigger, the algorithm gets smaller and smaller, and in extreme cases, just one, okay

    What is logarithm: First, this is an exponential function [N = a ^ x], and the logarithm function is a [x = logaN], and the logarithm is x, which is called the logarithm of N base A. When a is larger, x will be smaller if N is fixed, that is, the number of executions will be less.

    For example, if N = 1024, a = 2, and x = 10, this code only needs to be executed 10 times. If the complexity is linear, it might need to be executed 1024 times

  • Linear order two (n) : Simple for loops, == The number of times that the code is executed depends on n==. Generally, there is only one FOR loop. In special cases, n for loops may achieve one for loop

  • Linear log order two (nlognN) : Specifies that the time complexity of the log order code is executed n times. == The number of times the code is executed depends on the small n of the log order and depends on the n of the linear order. Note that the n of the two are different

    • private static void m(int n){
    for(int f = 1; f < n; f++) {int i = 1;
        while (i < n) {
            i = i * 2;  // The little n is set to 2·}}}Copy the code

  • Square two o (n^2) : Nesting two layer N loops, that is, the number of execution times is n^2

Ten sorting algorithms

Our ultimate goal is to master these ten sorting algorithms

Let’s start with bubble sort 02_ bubble sort in the first exchange sort