[interview: Basics 03: selection sort]

【 interview ： The basic chapter 03： Selection sort 】

00. Preface

If you have any questions, please also point out , thank .

01. brief introduction

Selective sorting is a kind of basic sorting , The idea is , The original sequence is divided into ordered and disordered parts , Every time from the disordered part Pick out the extreme value and put it into the ordered sequence

02. Algorithm steps

For sequence {5,3,7,2,1,9,8,4} Sort from small to large

initial The ordered part is empty The unordered part is 5 3 7 2 1 9 8 4

The first trip ：1 3 7 2 5 9 8 4, The ordered part is 1 The unordered part is 3 7 2 5 9 8 4, Elements 1 Location and elements of 5 Position exchange of

The second trip ：1 2 7 3 5 9 8 4 , The ordered part is 1 2 The unordered part is 7 3 5 9 8 4 , Elements 2 Location and elements of 3 Position exchange of

The third time ：1 2 3 7 5 9 8 4, The ordered part is 1 2 3 The unordered part is 7 5 9 8 4, Elements 3 Location and elements of 5 Position exchange of

The fourth trip ：1 2 3 4 5 9 8 7 , The ordered part is 1 2 3 4 The unordered part is 5 9 8 7 , Elements 4 Location and elements of 7 Position exchange of

The fifth trip ：1 2 3 4 5 9 8 7, The ordered part is 1 2 3 4 5 The unordered part is 7 9 8, Elements 5 Location and elements of 5 Position exchange of

Sixth lie down ：1 2 3 4 5 7 8 9, The ordered part is 1 2 3 4 5 7 The unordered part is 8 9, Elements 7 Location and elements of 9 Position exchange of

The seventh time ：1 2 3 4 5 7 8 9, The ordered part is 1 2 3 4 5 7 8 The unordered part is 9, Elements 8 Location and elements of 8 Position exchange of , But now there is only one element out of order So in fact, the sorting is over

We can see several problems

1. It can be seen that 8 Order of elements 7 Trip to

2. Selective sorting is to exchange the first element of the unordered part with the extreme value of the remaining elements , Finally, add the first element of the unordered part to the ordered part

3. It can be seen that the fifth and seventh trips are carried out Exchange with oneself , Here is the optimization point

03. Code

public static void main(String[] args) {
    
    int[] a = {
    5,3,7,2,1,9,8,4};
    int len = a.length;
    for (int i=0;i<len-1;i++){
    
        int pos=i;
        for (int j=pos+1;j<len;j++){
    
            if (a[j]<a[pos]) {
    
                pos = j;
            }
        }
        if (pos!=i){
    //  If the exchange element is not itself 
            System.out.println(" The first "+(i+1)+" Trip to ");
            int t=a[pos];
            a[pos]=a[i];
            a[i]=t;
            for (int k=0;k<len;k++)
                System.out.printf("%d ",a[k]);
            System.out.println();
        }
    }
}

result

The first 1 Trip to
1 3 7 2 5 9 8 4
The first 2 Trip to
1 2 7 3 5 9 8 4
The first 3 Trip to
1 2 3 7 5 9 8 4
The first 4 Trip to
1 2 3 4 5 9 8 7
The first 6 Trip to
1 2 3 4 5 7 8 9

It can be seen that the exchange of the fifth and seventh trips is missing after optimization

04. Comparison between selective sorting and bubbling sorting

The same thing :

1. Both of them are basic sorting The time complexity is zero O($n^2$)

2. Both of them sort based on Exchange

Difference :

1. Selection sort is unstable sort ¹, Bubble sort is stable sort

2. In the case of disordered order, the time complexity of selective sorting is better than bubble sorting , Because every time you choose to sort, you only record the subscript value, and finally you only exchange it once , And bubble sorting needs to be exchanged many times per trip .

3. The time complexity of the optimized bubble sort is better than that of the selective sort , Because the optimized bubble sorting The number of trips and exchanges will be greatly reduced , But choosing sorting is not good

---

1. Unstable sorting refers to , After sorting, the relative front and back positions of elements have changed , for example 5 8 5 2 9, Select Yes after sorting 2 5 5 8 9, But at this time 5 5 The position before and after the original sequence changes . The bubbling order is unchanged , So bubble sort is stable sort . ︎