A simple introduction

The basic concept

  1. Selection sort is a simple and intuitive sorting algorithm.
  2. It first finds the smallest element in the unsorted sequence, places it at the beginning of the sequence, and then continues to find the smallest element from the remaining unsorted elements and places it at the end of the sorted sequence. And so on, until all the data elements to be sorted are sorted.

The principle of interpretation

  • Taking the sequence 41, 34, 19, 17, 2 as an example, the realization principle of selective sorting is illustrated
  1. Before traversal, the effect is shown below
  2. The first traversal finds the minimum element 2 from the sequence and swaps the position of element 2 with the data 41 at the beginning of the sequence, resulting in the following figure

    At this point, element 2 is sorted, but 34, 19, 17, 41 are not sorted. The effect is shown in the figure below

  3. The second traversal finds the smallest element 17 from the unsorted elements in the sequence and swaps the position of element 17 with the element 34 at the end of the sorted sequence, resulting in the following figure

    At this point, elements 2 and 17 are sorted, while elements 19, 34 and 41 are not sorted. The effect is shown in the following figure

  4. The third traversal finds the smallest element 19 from the unsorted elements in the sequence. At this point, element 19 is larger than element 17 at the end of the sorted sequence and its position is already lower than that of element 17. Therefore, element 19 and element 17 do not need to move their positions
  5. The fourth traverse finds the smallest element 34 from the unsorted elements in the sequence. At this point, element 34 is smaller than element 19 at the end of the sorted sequence, and its position is already lower than that of element 19. Therefore, element 34 and element 19 do not need to move, and the effect is shown in the figure below
  6. The fifth iteration found the smallest element 41 from the unsorted elements in the sequence. At this time, element 41 has not been the last element in the sequence, so there is no need for comparison. The final result is shown in the figure below

Time complexity

The time complexity of sorting algorithm is proportional to the number of comparison and movement of two adjacent data in the algorithm. Details are as follows:

The number of data More times Maximum number of moves Minimum number of moves
1 0 0 0
2 1 1 0
3 3 2 0
4 6 3 0
5 10 4 0
10 45 5 0
N 1/2N(N-1) (N-1) 0

So in terms of time complexity, the bubble algorithm is O(N^2).

Results show

Download the source code

  • Please reply “algorithm source code” in the public number to get the top ten classic sorting algorithm source code

For more algorithm learning, please pay attention to my public number