Simple select sort and heap sort

1、 Simple selection sort

1.1、 Basic introduction

• Selective sorting also belongs to internal sorting , Is from the pre sorted data , Select an element according to the specified rules , And then exchange positions according to regulations to achieve the purpose of sorting .

• Selection sort （select sorting） It's also a simple sort method .

• The basic idea is ： First time from arr[0]~arr[n-1] Select the minimum value in , And arr[0] In exchange for , Second times from arr[1]~arr[n-1] Select the minimum value in , And arr[1] In exchange for , The third time from arr[2]~arr[n-1] Select the minimum value in , And arr[2] In exchange for ,…, The first i Secondary slave arr[i-1]~arr[n-1] Select the minimum value in , And arr[i-1] In exchange for ,…, The first n-1 Secondary slave arr[n-2]~arr[n-1] Select the minimum value in , And arr[n-2] In exchange for , Total pass n-1 Time , To get an ordered sequence from small to large .

1.2、 Code implementation

// Ascending sort 
// Select sorting time complexity O(n²)
public class SelectSort {
    
    public static void main(String[] args) {
    
        int[] arr = {
    9,4,2,6,3,7,4,1};
        selectSort(arr);
        System.out.println(" After ordering ");
        System.out.println(Arrays.toString(arr));
    }

    public static void selectSort(int[] arr){
    

        for (int i = 0; i < arr.length - 1; i++) {
    
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
    
                if(min > arr[j]){
     // Explain assumed min Not the minimum ; If sorting from large to small , Change the greater than sign to the less than sign 
                    min = arr[j];
                    minIndex = j;
                }
            }
            if(minIndex != i){
    
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
}

2、 Heap sort

2.1、 Basic introduction

• Heap sorting is a sort algorithm designed by using heap data structure , Heap sorting is a kind of Selection sort , It's the worst , best , The average time complexity is O(nlogn), It's also an unstable sort .

• A heap is a complete binary tree with the following properties ： The value of each node is greater than or equal to the value of its left and right child nodes , It's called the big top reactor ; Be careful ： There is no relationship between the value of the left child of the node and the value of the right child .

• The value of each node is less than or equal to the value of its left and right child nodes , It's called the small top reactor

• commonly In ascending order, large top reactor is used , In descending order, small top reactor is used

2.2、 The basic idea

• The basic idea of heap sorting
  • The column order to be sorted is constructed into a large top heap ==> Array ( Store binary trees in sequence )
  • here , The maximum value of the whole sequence is the root node at the top of the heap .
  • Exchange it with the last element , At the end of this time is the maximum value .
  • And then there will be the rest n-1 Elements are restructured into a heap , This will get n-1 The minor value of an element . Do it over and over again , Then we can get an ordered sequence .
• You can see that in the process of building the big top heap , The number of elements decreases gradually , Finally, we get an ordered sequence
• The basic idea of heap sorting
  • Build an unordered sequence into a heap , According to the demand of ascending and descending order, choose big top heap or small top heap ;
  • Exchange the top element with the end element , Will be the largest element " sink " To the end of the array ;
  • Restructure , Make it meet the heap definition , Then continue to exchange the heap top element with the current end element , Repeat the adjustment + Exchange steps , Until the whole sequence is in order .

2.3、 The heap sort steps are illustrated

• requirement : An array {4,6,8,5,9}, Requires heap sort , Sort the array in ascending order .

• Step one ： Construct the initial heap . Construct a given unordered sequence into a large top heap ( Generally, large top reactor is used in ascending order , In descending order, small top reactor is used ).

  • Let's assume that the structure of the given unordered sequence is as follows
    

  • At this point, start from the last non leaf node ( The leaf node naturally does not need to be adjusted , The first non leaf node arr.length/2-1=5/2-1=1, That's what's down here 6 node ）, From left to right , Adjust from bottom to top .

  

  • Find the second non leaf node 4, because [4,9,8] in 9 The biggest element ,4 and 9 In exchange for .

  

  • At this time , Exchange leads to child roots [4,5,6] Structural chaos , Continue to adjust ,[4,5,6] in 6 Maximum , In exchange for 4 and 6.

  

• Step two ： Exchange the top element with the end element , Make the last element the largest . Then continue to adjust the pile , Then exchange the top element with the end element , Get the second element . Exchange so repeatedly 、 The reconstruction 、 In exchange for .

  • Put the top element 9 And the last element 4 swapping

  

  • Restructure , Let it continue to meet the heap definition

  

  • Then the top element 8 And the last element 5 swapping , Get the second element 8

  

  • Follow up process , Keep adjusting , In exchange for , So repeatedly , Finally, it makes the whole sequence orderly

  

2.4、 Code implementation

// Heap sort 
// requirement : Use heap sorting , Sort the array in ascending order （ Big pile top ）
public class HeapSort {
    
    public static void main(String[] args) {
    
        int[] arr = {
    4, 6, 8, 5, 9};
        System.out.println(" After heap sorting ");
        heapSort(arr);
    }

    // Write a heap sort method 
    public static void heapSort(int[] arr) {
    
        int temp = 0;
        
        // Build an unordered sequence into a heap , According to the demand of ascending and descending order, choose big top heap or small top heap 
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
    
            adjustHeap(arr, i, arr.length);
        }

        // Exchange the top element with the end element , Will be the largest element " sink " To the end of the array ;
        // Restructure , Make it meet the heap definition , Then continue to exchange the heap top element with the current end element , Repeat the adjustment + Exchange steps , Until the whole sequence is in order .
        for (int j = arr.length - 1; j > 0; j--) {
    
            // Exchange the top element with the end element , That is, the first element and the last element of the array are exchanged 
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.println(Arrays.toString(arr));

    }

    // Put an array （ Corresponding to binary tree ）, Adjust to a big top pile 

    /** *  function : The completion will be i The corresponding non leaf node of the tree is adjusted to a large top heap  *  give an example  int arr[] = {4,6,8,5,9}; =Ii = 1 => adjustHeap => obtain {4,9,8,5,6} *  If we call again adjustHeap What's coming in is i = 0 =>  obtain {4,9,8,5, 6} => {9,6,8,5,4} * * @param arr  Array with adjustments  * @param i  Indicates that non leaf nodes are indexed in the array  * @param length  Represents how many elements to adjust ,length It's gradually decreasing （ That is, the length of the array or the number of nodes ） */
    public static void adjustHeap(int[] arr, int i, int length) {
    

        int temp = arr[i]; // Take the value of the current element first , Save in temporary variables 
        // Began to adjust 
        /* explain  1.k = i * 2 + 1  yes  i  The left child of a node  */
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
    
            if (k + 1 < length && arr[k] < arr[k + 1]) {
     // The value of left child node is less than that of right child node 
                k++; //k  Point to the right child node 
            }
            if (arr[k] > temp) {
     // If the child node is larger than the parent node 
                arr[i] = arr[k]; // Assign a larger value to the current node 
                i = k; //！！！i  Point to k, Continue the loop comparison 
            } else {
    
                break;
            }
        }
        // When for At the end of the cycle ,, Has been set to i The maximum value of the tree that is the parent node , It's on the top （ Local ）
        arr[i] = temp; // take temp Put the value in the adjusted position 
    }
}