Sorting selection sorting

Catalog

Preface

One 、 What is selective sorting

Two 、 Use code to implement

3、 ... and 、 Time complexity , Spatial complexity and stability

Four 、 Bidirectional selection sorting （ Understanding can ）

summary

---

Preface

Previously, we introduced insertion sorting , Today we will learn about other common sorting , That is, select sorting , Selection sorting includes direct selection sorting and heap sorting , And today we mainly learn to choose sorting directly , Its idea is relatively simple ！

---

One 、 What is selective sorting

As the name suggests, select sorting is to select the elements to sort , If you want to sort in ascending order, choose the smallest , In descending order, choose the largest , Exchange with the first element of the sequence , Then the whole sequence can be ordered again and again .

 

Two 、 Use code to implement

public class Choice {
    /**
     *  Selection sort 
     * @param array  Sequence to be sorted 
     */
    public static void selectSort(int[] array) {

        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]){
                    minIndex = j;// Record the minimum subscript 
                }
            }
            int tmp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = tmp;

        }
    }

}

3、 ... and 、 Time complexity , Spatial complexity and stability

Time complexity ：O(N^2) Whether optimized or not, it is O(N^2) After optimization, only unnecessary exchanges are reduced

Spatial complexity ：O(1)  No more memory is used

stability ： unstable There was a jump exchange

Four 、 Bidirectional selection sorting （ Understanding can ）

Each time, the smallest... Is selected from the disordered interval and The largest element subscript , Stored at the top and bottom of the unordered interval , Until all the data elements to be sorted are finished .

---

summary

        The sorting of this choice is still very simple , Just know how to choose and sort , Another option is sorting ： Heap sorting is more interesting , It is also a more important sort , Therefore, selecting sorting directly can lay a foundation for the following heap sorting , Facilitate the learning of heap sorting later ！