Implementation and performance optimization techniques of Java selection sort algorithm

Complete implementation and optimization techniques of Java selection sorting code

Selection Sort is a simple and intuitive sorting algorithm. Its basic idea is to find un Sorts the smallest (or largest) element in an array and places it at the end of the sorted array. Repeat this step until the entire array is sorted. The following is a detailed description of the complete implementation of selection sort in Java and optimization techniques.

Basic implementation of selection sorting:

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

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

In the above code, we first define the main method of selection sorting selectionSort(int[] arr). In the main method, we first calculate the length of the array and then go through two nested loops to find the smallest element in the unsorted part and swap it with the element at the current position. Repeat this step until the entire array is sorted. Finally, in the main method, we define a sample array and call the selectionSort method for sorting.

The time complexity of selection sort is O(n^2), which means that as the number of elements increases, the time required for sorting will increase quadratically. However, we can use some techniques to improve the efficiency of selection sort.

Optimization Tip 1: Reduce the number of exchange operations

In each round of selection sort, we will find the smallest element of the unsorted part and exchange it with the element at the current position. Although this is necessary, it may impact performance if each swap requires three assignments. We can reduce the number of exchanges by directly recording the index value of the smallest element and then performing only one assignment operation. The modified code looks like this:

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

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Optimization Tip 2: Add a judgment to check the sorted part

In each round, we will traverse the unsorted part to find the smallest element. However, if during the traversal process it is found that the largest element of the sorted part is smaller than the smallest element of the unsorted part, then the sorting has been completed and we can terminate the sorting process early. The modified code is as follows:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            boolean sorted = true;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
                if (arr[j] < arr[j-1]) {
                    sorted = false;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
            if (sorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Through the above optimization techniques, we can improve the execution efficiency of selection sort.

Summary:

Selection sort is a simple but inefficient sorting algorithm. The efficiency of selection sort can be improved by reducing the number of exchange operations and adding judgment on the sorted part. However, although the time complexity of selection sort is O(n^2), it is still an effective sorting algorithm in some specific scenarios.

I hope this article can help you understand and implement selection sorting, and improve algorithm efficiency through some optimization techniques.

The above is the detailed content of Implementation and performance optimization techniques of Java selection sort algorithm. For more information, please follow other related articles on the PHP Chinese website!