How to implement sorting algorithm using java

Unstable sorting

Selection sorting:
The smallest record obtained after the first round of comparison is exchanged with the position of the first record, and then the smallest record excluding the first record is The records are compared in the second round, and the smallest record obtained is exchanged with the second record
Time complexity: O(n^2)
Space complexity: O(1)

    public static void selectSort(int[] arr){        
    if (arr == null || arr.length == 0)            
    return;        
    int len = arr.length;        
    for (int i = 0; i < len; i++) {            
        int min = arr[i];            
        int index = i;            
        for (int j = i+1; j < len; j++) {                
        if (arr[j] < min) {                    
            min = arr[j];
          index = j;
          }
       }
       arr[index] = arr[i];
       arr[i] = min;
     }
    }

Fast Sorting:
For a given set of records, after each sorting pass, the original sequence is divided into two parts, where all records in the former part are smaller than all records in the latter part, and then the records of the two parts before and after are sequentially Perform quick sort
Time complexity: O(nlogn) Worst: O(n^2)
Space complexity: O(nlogn)

    public int Partition(int[] a,int start,int end){        int std = a[start];
        while (start < end){
             while(start < end && a[end] >= std)                 
             end--;
             a[start] = a[end];
             while(start < end && a[start] <= std)                 
             start++;
             a[end] = a[start];
        }
        a[start] = std;
        return start;
    }
    public void quickSort(int[] a,int start,int end){        
            if(start >= end){
            return;
        }
        int index = Partition(a,start,end);
        quickSort(a,start,index-1);
        quickSort(a,index+1,end);
    }

Heap sort: complete binary tree
Will The binary tree is adjusted to a big top heap, and then the last element of the heap is exchanged with the top element of the heap (that is, the root node of the binary tree). The last element of the heap is the maximum record; then the first n-1 elements are adjusted to Large top heap, and then exchange the top element of the heap with the last element of the current heap to obtain the second largest record. Repeat this process until there is only one element left in the adjusted heap. This element is the minimum record. At this time, you can get a Ordered sequence
Time complexity: O(nlogn)
Space complexity: O(1)

   public void HeapSort(int[] a){        
            for (int i = a.length/2 - 1; i >= 0 ; i--) {
            HeapAdjust(a,i,a.length-1);
        }        
        for (int i = a.length - 1; i >= 0; i--) {
            swap(a,0,i);
            HeapAdjust(a,0,i-1);
        }
    }    
    private void swap(int[] a, int i, int j) {        
            int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }    
    public void HeapAdjust(int[] arr,int s,int len){        
            int tmp = arr[s];        
            for (int i = s * 2 + 1; i < len ; i = i * 2 + 1) {            
                    if (i < len && arr[i] < arr[i+1]){
                i++;
            }            
            if (tmp > arr[i])                
            break;
            arr[s] = arr[i];
            s = i; //s记录被替换的子结点的索引
        }
        arr[s] = tmp;
    }

Stable sorting

Direct insertion sorting:
The first one The records can be regarded as forming an ordered sequence, and the remaining records are called unordered sequences. Then starting from the second record, insert the currently processed record into the previous ordered sequence in order according to the size of the record until the last record is inserted into the ordered sequence
Time complexity: O(n^2)
Space complexity: O(1)

    public static void insertSort(int[] arr){        
            if (arr == null || arr.length == 0)            
            return;        
            int len = arr.length;        
            for (int i = 1; i < len; i++) {            
            int curr = arr[i];            
            int j = i;            
            if (arr[j-1] > curr){                
                while (j > 0 && arr[j-1]> curr){
                arr[j] = arr[j-1];
                j--;
                }
            }
          arr[j] = curr;
        }
    }

Bubble sorting:
Starting from the first record, two adjacent records are compared in sequence. When the previous record is larger than the following record, the positions are swapped. After a round of comparison and transposition, the largest record among the n records will be located at the nth record. bit, and then perform a second round of comparison on the previous n-1 records, and repeat the process until only one record is compared
Time complexity: O(n^2)
Space complexity: O(1)

    public void bubbleSort(int[] arr){        
            boolean flag = true;        
            for (int i = 0; i < arr.length && flag; i++) {
            flag = false;            
            for (int j = 0; j < arr.length - i - 1; j++) {                
                    if (arr[j] > arr[j+1]){
                flag = true;
                swap(arr,j,j+1);
                }
            }
        }
    }    
    private void swap(int[] arr, int j, int i) {        
            int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

Merge sort: recursion, and: merge separate data in an orderly manner
Merge every two adjacent subsequences of length 1 to obtain n/2 ordered subsequences of length 2 or 1, then merge the two, and repeat this process until an ordered sequence is obtained
Time complexity: O(nlogn)
Space complexity: O(n)

   public static void mergeSort(int[] arr,int begin,int end){        
              int mid = (begin+end)/2;        
              if (begin < end){
            mergeSort(arr,begin,mid);
            mergeSort(arr,mid+1,end);
            Merge(arr,begin,end,mid);
        }
    }    
    public static void Merge(int[] arr,int begin,int end,int mid){        
            int[] temp = new int[end-begin+1];        
            int i = begin;        
            int j = mid+1;        
            int k=0;        
            while (i <= mid && j <= end){            
            if (arr[i] < arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }
        }        
        while (i <= mid){
            temp[k++] = arr[i++];
        }        
        while (j <= end){
            temp[k++] = arr[j++];
        }        
        for (int m = 0;m < temp.length;m++){
            arr[m+begin] = temp[m];
        }
    }

The above is the detailed content of How to implement sorting algorithm using java. For more information, please follow other related articles on the PHP Chinese website!