Detailed explanation of common sorting algorithms implemented in Java

Sorting algorithms are an important concept in computer science and are a core part of many applications. In daily life and work, we often need to sort data, such as sorting lists, sorting values, etc. Java, as a widely used programming language, provides many built-in sorting algorithms. This article will provide a detailed introduction to common sorting algorithms implemented in Java.

1. Bubble Sort

Bubble sort is one of the simplest but slowest sorting algorithms. It iterates through the entire array, comparing adjacent elements and moving larger values ​​to the right step by step, eventually moving the largest element to the end of the array. This process is similar to the process of bubbles rising from the bottom of the water to the surface, hence the name bubble sort.

The following is the bubble sorting algorithm implemented in Java:

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Time complexity: O(n^2)

2. Selection Sort

Selection sort is another simple sorting algorithm that continuously selects the smallest unsorted element and moves it to the end of the sorted part. Selection sort is similar to bubble sort, but it does not require constant exchange of elements in each iteration, making it faster.

The following is the selection sort algorithm implemented in Java:

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        int temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

Time complexity: O(n^2)

3. Insertion Sort

Insertion sort is a more efficient sorting algorithm. It finds the position in the sorted array and inserts the unsorted elements into the correct position. Insertion sort is suitable for smaller data sets due to fewer swaps.

The following is the insertion sort algorithm implemented in Java:

public static void insertionSort(int[] arr) {
    int n = arr.length;
    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--;
        }
        arr[j + 1] = key;
    }
}

Time complexity: O(n^2)

4. Quick Sort (Quick Sort)

Quick sort is an efficient sorting algorithm that uses the divide-and-conquer idea to split the array into smaller sub-arrays, then sort the sub-arrays through recursion, and merge them to form the final sort result. The key to quick sort is to select the middle element and sort by size.

The following is the quick sort algorithm implemented in Java:

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Time complexity: O(n log n)

5. Merge Sort (Merge Sort)

Merge sort is another common sorting algorithm that uses the divide-and-conquer idea to split the array into smaller sub-arrays, and then sort and merge them one by one to generate the final sort result. Merge sort is generally slower than quick sort, but it is more stable.

The following is the merge sort algorithm implemented in Java:

public static void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

public static void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[m + j + 1];
    }
    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Time complexity: O(n log n)

Conclusion

The above are common in Java sorting algorithms and their implementation details. Bubble sort and selection sort are simpler but have higher time complexity; insertion sort is faster and suitable for smaller data sets; quick sort is faster but unstable; merge sort is stable but slower. In actual use, selection needs to be made based on different data samples and actual needs.

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