[eight sorts ②] select sort (select sort, heap sort)

Catalog

 

One 、 Selection sort

About selection and sorting  

Algorithm steps ：

Code implementation  

【 Summary of the characteristics of direct selection sorting 】

  Two 、 Heap sort

Basic idea of heap sort algorithm

 【 Summary of the characteristics of direct selection sorting 】

---

One 、 Selection sort

About selection and sorting  

Selection sort is a simple and intuitive sorting algorithm , No matter what data goes in, it's O(n²) Time complexity of . So when you use it , The smaller the data, the better . The only benefit may be that it doesn't take up extra memory space .

Algorithm steps ：

1. First, find the minimum in the unsorted sequence （ Big ） Elements , To the beginning of the collating sequence .
2. Continue to find the smallest from the remaining unsorted elements （ Big ） Elements , And then at the end of the sorted sequence .
3. Repeat step 2 , Until all the elements are sorted .

Code implementation  

/**
     *  Selection sort 
     * @param array
     */
    public static void selectSort(int[]array){
        for(int i = 0;i < array.length-1 ;i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                swap(array, minIndex, i);
            }
        }
    }

【 Summary of the characteristics of direct selection sorting 】

• It's very easy to understand how to think directly , But the efficiency is not very good . It is seldom used in practice
• Time complexity ：O(N^2)
• Spatial complexity ：O(1)
• stability ： unstable

  Two 、 Heap sort

  We have already introduced the big root heap 、 The concept of small root pile , And heap sorting is to use heap （ Build a large root pile in ascending order , Build small piles in descending order ） The method of sorting .

Basic idea of heap sort algorithm

Construct the sequence to be sorted into a large root heap . At this time, the whole sequence Maximum Is the root node at the top of the heap . Remove it （ In fact, that is Swap it with the end element of the heap array , At this point, the last element is the maximum value ）, Then I'll take the rest n-1 A sequence of Restructure into a heap , So you get n The next largest of the elements . Do it over and over again , Then we can get an ordered sequence

  The above dynamic picture comes from elsewhere

Now let's disassemble each step

Pictured , It's a big pile ,90 Is the maximum , take 90 And 20（ End element ） swap

  here 90 It becomes the last element of the whole heap sequence

take 20 After adjustment , To divide 90 Other nodes continue to meet the definition of large root heap （ All nodes are larger than their children ）

I believe you understand the basic idea of heap sorting , But to complete the heap sorting , need Solve the following two problems ：

• How to build a heap from an unordered sequence ?
• If after outputting the top element , Adjust the remaining elements into a new heap ?

Let's look at another picture and experience （ Source elsewhere ）

  

Let's look at the code

   /**
     *  Heap sort 
     * @param array
     * @param root
     * @param len
     */
    public static void shiftDown(int[]array,int root,int len){
        int parent = root;
        int child = (2*parent)+1;
        while(child < len) {
            if(child+1 < len  && array[child] < array[child + 1]) {
                child++;
            }
            if(array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = (2*parent)+1;
            }else{
                break;
            }
        }
    }
    public static void createHeap(int[] array){
        for(int p = (array.length-1-1)/2; p>=0 ; p--){
            shiftDown(array,p, array.length);
        }
    }
    public static void heapSort(int[] array){
        createHeap(array);
        int end = array.length-1;
        while(end>=0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

 【 Summary of the characteristics of direct selection sorting 】

• Heap sort uses heap to select numbers , It's a lot more efficient .
• Time complexity ：O(N*logN)
• Spatial complexity ：O(1)
• stability ： unstable