Deeply understand Java sorting algorithm

Overview

Sorting algorithms are a basic problem in computer science and an important part of data structure learning. In Java, we can use various sorting algorithms to arrange elements in an array or list. The following are introductions to several common sorting algorithms and their basic ideas:

Introduction to sorting algorithm

1. Bubble Sort

Basic idea: Through comparison and exchange between adjacent elements, the largest (or smallest) element can "float" to one end of the sequence after each order.

Java example:

public static void bubbleSort(int[] arr) {  
    int n = ;  
    for (int i = 0; i &lt; n - 1; i++) {  
        for (int j = 0; j &lt; n - i - 1; j++) {  
            if (arr[j] &gt; arr[j + 1]) {  
                // Exchange arr[j] and arr[j + 1]                int temp = arr[j];  
                arr[j] = arr[j + 1];  
                arr[j + 1] = temp;  
            }  
        }  
    }  
}

2. Select Sort

Basic idea: select the smallest (or largest) element from the elements to be sorted each time and store it in the starting position of the sequence until all the data elements to be sorted are sorted.

Java example:

public static void selectionSort(int[] arr) {  
    int n = ;  
    for (int i = 0; i &lt; n - 1; i++) {  
        int minIndex = i;  
        for (int j = i + 1; j &lt; n; j++) {  
            if (arr[j] &lt; arr[minIndex]) {  
                minIndex = j;  
            }  
        }  
        // Exchange arr[i] and arr[minIndex]        int temp = arr[i];  
        arr[i] = arr[minIndex];  
        arr[minIndex] = temp;  
    }  
}

3. Insertion Sort

Basic idea: Insert the elements to be sorted one by one in the appropriate position in the already sorted sequence one by one until all inserts are completed.

Java example:

public static void insertionSort(int[] arr) {  
    int n = ;  
    for (int i = 1; i < n; ++i) {  
        int key = arr[i];  
        int j = i - 1;  
        while (j >= 0 && arr[j] > key) {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  
}

4. Merge Sort

Basic idea: A very typical application of the method of dividing and conquer. Merge the ordered subsequences to obtain a completely ordered sequence; that is, make each subsequence first order, and then make the subsequence segments order.

Java example:

public static void mergeSort(int[] arr) {  
    if ( < 2) {  
        return;  
    }  
    int mid =  / 2;  
    int[] left = (arr, 0, mid);  
    int[] right = (arr, mid, );  
    mergeSort(left);  
    mergeSort(right);  
    merge(arr, left, right);  
}  
  
private static void merge(int[] arr, int[] left, int[] right) {  
    int i = 0, j = 0, k = 0;  
    while (i <  && j < ) {  
        if (left[i] <= right[j]) {  
            arr[k++] = left[i++];  
        } else {  
            arr[k++] = right[j++];  
        }  
    }  
    while (i < ) {  
        arr[k++] = left[i++];  
    }  
    while (j < ) {  
        arr[k++] = right[j++];  
    }  
}

5. Quick Sort

Basic idea: divide the data to be sorted into two independent parts by sorting one time, and all the data in part are smaller than all the data in the other part, and then quickly sort these two parts of the data according to this method. The entire sorting process can be performed recursively to achieve the entire data becoming an ordered sequence.

Java example:

public static void quickSort(int[] arr, int low, int high) {  
    if (low &lt; high) {  
        int pivotIndex = partition(arr, low, high);  
        quickSort(arr, low, pivotIndex - 1);  
        quickSort(arr, pivotIndex + 1, high);  
    }  
}  
  
private static int partition(int[] arr, int low, int high) {  
    int pivot = arr[high]; // Select the rightmost element as the pivot    int i = low - 1; // Pointer to the smallest element    for (int j = low; j &lt; high; j++) {  
        if (arr[j] &lt;= pivot) {  
            i++;  
            // Exchange arr[i] and arr[j]            int temp = arr[i];  
            arr[i] = arr[j];  
            arr[j] = temp;  
        }  
    }  
    // Put the pivot element in the correct position    int temp = arr[i + 1];  
    arr[i + 1] = arr[high];  
    arr[high] = temp;  
    return i + 1;  
}  
  
// Call the quick sort methodpublic static void quickSort(int[] arr) {  
    quickSort(arr, 0,  - 1);  
}

Summarize

Each sorting algorithm has its advantages and disadvantages. For example, bubble sorting and insert sorting perform well on small arrays or almost ordered arrays, but their performance is poor on large arrays. Selection sorting performs well on small arrays, but is less efficient on large arrays. Merge sorting and quick sorting perform well on large arrays, but merge sorting requires extra space to merge subarrays, and quick sorting can encounter worst-case time complexity in some cases. Therefore, when choosing a sorting algorithm, trade-offs need to be made based on specific circumstances and needs.

This is all about this article about in-depth understanding of Java sorting algorithm. For more related Java sorting algorithm content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!