Detailed explanation of commonly used sorting algorithms and implementation methods in Java

1. Selection sort

Selection sort is a simple and intuitive sorting algorithm. No matter what data is entered, the time complexity is O(n²). So when using it, the smaller the data size, the better. The only advantage may be that it does not occupy additional memory space.

First find the smallest (large) element in the unsorted sequence and store it at the starting position of the sorted sequence.

Continue to find the smallest (large) element from the remaining unsorted elements, and then put it at the end of the sorted sequence.

Repeat the second step until all elements are sorted.

public static void selectSort(int[] arr) {
        //选择排序
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int minValueIndex = i;
            for (int j = i+1; j < n; j++) {
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            swap(arr,i,minValueIndex);
        }
    }
    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {7,5,1,9,4,2,6};
        printArray(arr);
        selectSort(arr);
        printArray(arr);
    }

2. Bubble sorting

**The principle of bubble sorting algorithm is as follows: **

1. Compare adjacent Elements. If the first one is bigger than the second one, swap them both.

2. Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element should be the largest number.

3. Repeat the above steps for all elements except the last one.

4. Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers to compare.

public static void bubbleSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }
     public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = {14,6,3,10,2};
        printArray(arr);
        bubbleSort(arr);
        printArray(arr);
    }

3. Insertion sort

Insertion sort means that among the elements to be sorted, assume that the first n-1 (n>=2) The numbers are already in order. Now insert the nth number into the previously arranged sequence, and then find a suitable position so that the sequence in which the nth number is inserted is also in order. The process of inserting all elements according to this method until the entire sequence is in order is called insertion sort

public static void insertSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int currIndex = i;
            while(currIndex - 1 >= 0 && arr[currIndex-1] > arr[currIndex]) {
                swap(arr,currIndex,currIndex-1);
                currIndex--;
            }
        }
    }

    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = {3,6,1,5,2};
        printArray(arr);
        insertSort(arr);
        printArray(arr);
    }

Insertion sort Optimization

public static void insertSort1(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            for (int j = i-1; j >= 0; j--) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }else {
                    break;
                }
            }
        }
    }

The above is the detailed content of Detailed explanation of commonly used sorting algorithms and implementation methods in Java. For more information, please follow other related articles on the PHP Chinese website!