How to implement simple sorting in Java

Sorting is a very common and core operation in data processing. Although there is a small chance that we will need to implement it manually in actual project development, after all, there are classes in each language’s class library. There are many implementations of sorting algorithms. But it is still of great benefit to us to understand these subtle ideas. This article briefly reviews the three most basic types of algorithms: selection, bubbling, and insertion.

First define a function to exchange array elements, which can be called when sorting

/**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }

Simple selection sorting

Simple selection sorting is the simplest and most intuitive algorithm. The basic idea is Each pass selects the smallest (or largest) element from the data elements to be sorted as the first element until all elements are sorted. Simple selection sorting is an unstable sorting.

When the algorithm is implemented, each time the minimum element is determined, the first position will be the current minimum through constant comparison and exchange. Exchange is a relatively time-consuming operation. In fact, we can easily find that these exchanges are meaningless before the current minimum element is completely determined. We can set a variable min to store only the array subscript of the smaller element for each comparison. When the loop ends, this variable stores the subscript of the current smallest element, and then perform the exchange operation. The code implementation is very simple, let’s take a look.

Code implementation

/**
     * 简单选择排序
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;//每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换，如果min发生变化，则进行交换
            if (min != i) {
                swap(arr,min,i);
            }
        }
    }

After simple selection sorting is optimized above, the number of comparisons remains unchanged regardless of the original arrangement of the array; for exchange operations, in the best case, the array is completely When the array is in reverse order, there is no need for any exchange moves. In the worst case, that is, when the array is in reverse order, the number of exchanges is n-1. Taken together, the time complexity is O(n2)

Bubble sort

The basic idea of ​​bubble sort is to compare adjacent elements pairwise, and exchange them if the order is reversed. In this way, each pass will "float" the smallest or largest element to the top, and finally achieve complete order

Code implementation

In bubble sort During the process, if a certain trip is completed without any exchange operation, for example, the array [5,4,1,2,3] performs bubbling twice, that is, after two outer loops, 5 and 4 are adjusted to the final position [1,2,3,4,5]. At this time, after executing the third loop, no exchange has been done, which means that the remaining sequences are already in order, and the sorting operation can be completed. Let’s take a look at the code

/**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;//设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

according to The above bubble implementation, if the original array itself is ordered (this is the best case), can be completed with only n-1 comparisons; if it is in reverse order, the number of comparisons is n-1 n-2 ... 1= n(n-1)/2, the number of exchanges and the number of comparisons are equal. Therefore, its time complexity is still O(n2). Overall, the performance of bubble sort is still slightly worse than the selection sort above.

Direct insertion sorting

The basic idea of ​​direct insertion sorting is to insert a record to be sorted into the previously sorted sequence at each step until all elements have been inserted. .

Code implementation

/**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr,j,j-1);
                j--;
            }
        }
    }

In the best case, simple insertion sort needs to be compared n-1 times without exchanging elements, and the time complexity is O( n); In the worst case, the time complexity is still O(n2). But when the array elements are randomly arranged, insertion sort is still better than the above two sorts.

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