This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

One, foreword

Selection sort: is a simple and intuitive sorting algorithm

This algorithm divides the array into ordered and unordered regions. Each time, the largest or smallest value in the unordered region is selected and placed in the ordered region until the entire array is ordered.

Similarly, select sort, each traversal determines an ordered position.

Ju Li, the GIF is as follows:





Two, knowledge points

Knowledge points, as follows:

  1. Time complexity
  2. The reverse of
  3. Implementation: Simple implementation

PS: Intern interview, will encounter


(1) Time complexity

  • Worst case: Reverse order, time complexity O(N ^ 2)

  • Stability: unstable.

    For example, the original array {4, 1, 4}

    Unstable: The second 4 is ranked before the first 4 in the sorting process.

General sorting diagram, as shown in figure:


(2)

If arr[I] > A [j] for subscript I < j, (I, j) is an inversion pair.

For example, sequence{34, 8, 64, 51, 32, 21}How many inversions are there?

Nine: (34, 8), (34, 32), (34, 21), (64, 51), (64, 32), (64, 21), (51, 32), (51, 21), (32, 21)Copy the code

Obtained theorem:

  • Theorem: ArbitraryNA sequence of different elements has an average ofN(N-1)/4A reverse order to
  • Theorem: The average time complexity of any algorithm that sorts only by swapping two adjacent elements isO(N^2)

So what’s the use of reverse pairs?

  1. It’s the number of swaps you have to make.

  2. It provides the basis for improving the efficiency of the algorithm

In order to improve the efficiency of the algorithm, it is necessary to:

  1. It cancels out more than one inversion pair at a time

  2. Swap two elements far apart at a time


(3) implementation

Sort from front to back as follows:

public class SelectSort {

    // Time: O(n^2), Space: O(1)
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int n = arr.length;
        for (int i = 0; i < n; ++i) {
            int minIdx = i;
            for (int j = i+1; j < n; ++j)
                if(arr[j] < arr[minIdx]) minIdx = j; swap(arr, i, minIdx); }}private void swap(int[] arr, int i, int j) {
        if (i == j) return;
        inttmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}Copy the code