Bubble sort, quick sort, merge sort

Bubble Sort is a computer science Simpler in the field Sorting algorithm.
It repeatedly visits the element column to be sorted, compares two adjacent elements in turn, and exchanges them if the order (e.g. from large to small and from Z to A) is wrong. The work of visiting elements is repeated until no adjacent elements need to be exchanged, that is, the element column has been sorted.
The name of this algorithm comes from the fact that the smaller elements will slowly "float" to the top of the sequence (in ascending or descending order) through exchange, just as the bubbles of carbon dioxide in carbonated drinks will eventually float to the top, so it is called "bubble sorting".
The total average time complexity of bubble sorting is
Bubble sorting is to move the small elements forward or the large elements backward. Comparison is the comparison of two adjacent elements, and the exchange also occurs between the two elements. Therefore, if two elements are equal, they will not be exchanged again; If two equal elements are not adjacent, even if they are adjacent through the previous pairwise exchange, they will not be exchanged at this time. Therefore, the sequence of the same elements has not changed, so bubble sorting is a Stable sorting algorithm
 
Quicksort is right Bubble sorting An improvement of.
Rapid sorting was proposed by C. A. R. Hoare in 1960. Its basic idea is to divide the data to be sorted into two independent parts through one-time sorting. All the data in one part is smaller than all the data in the other part, and then quickly sort the two parts of data according to this method. The whole sorting process can recursion In order to make the whole data orderly sequence.
 
The quick sort algorithm realizes sorting through multiple comparisons and exchanges. The sorting process is as follows:
(1) First, set a boundary value, and divide the array into left and right parts through the boundary value.  
(2) Gather the data greater than or equal to the boundary value to the right of the array, and the data less than the boundary value to the left of the array. At this time, all elements in the left part are less than or equal to the boundary value, while all elements in the right part are greater than or equal to the boundary value.
(3) Then, the data on the left and right can be sorted independently. For the array data on the left, you can take another boundary value and divide this part of the data into left and right parts. Similarly, place the smaller value on the left and the larger value on the right. The array data on the right can also be processed similarly.
(4) By repeating the above process, we can see that this is a recursive definition. After the left part is arranged recursively, the right part is arranged recursively. When the data of the left and right parts are sorted, the sorting of the whole array is completed.
 
The working principle of merging operation is as follows:
Step 1: apply for space so that its size is two sort The sum of sequences. This space is used to store the merged sequences
Step 2: set two Pointer , the initial position is the starting position of the two sorted sequences
Step 3: compare the elements pointed to by the two pointers, select a relatively small element and put it into the merge space, and move the pointer to the next position
Repeat step 3 until a pointer exceeds the end of the sequence
Copy all the remaining elements of another sequence directly to the end of the merged sequence
 
The code is as follows
 
package pro;

import java.util.Arrays;

//Bubble sort, quick sort, merge sort
public class SortWay {

    //Bubbling
    /*
    The principle of bubble sorting algorithm is as follows: [1]
    Compare adjacent elements. If the first one is bigger than the second, exchange them. [1]
    Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. At this point, the last element should be the largest number. [1]
    Repeat the above steps for all elements except the last one. [1]
    Continue to repeat the above steps for fewer and fewer elements at a time until no pair of numbers need to be compared
     */
    private static void bubbleSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-1; j++) {
                if(arr[j] > arr[j+1]) {
                    int tem = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tem;
                }
            }
        }

        System.out.println(Arrays.toString(arr));
    }

    /*
    The basic idea is to divide the data to be sorted into two independent parts through one sorting,
    All the data in one part is smaller than all the data in the other part, and then
    According to this method, the two parts of data are quickly sorted respectively, and the whole sorting process can be
    Recursively, so that the whole data becomes an ordered sequence
     */
    private static void quickSort(int[] arr) {
        int n = arr.length;
        qSort(arr, 0 , n-1);
        System.out.println(Arrays.toString(arr));
    }

    private static int[] qSort(int[] part, int s, int e) {
        int point = part[s];
        int i = s, j = e;

        // If the start is less than the end, continue to look for replacement
        while (i < j) {
            while (i < j && part[j] > point) { // If the following element is larger than the base element. End point j One step forward
                j--;
            }
            while (i < j && part[i] < point) { // If the preceding element is smaller than the base element. Starting point i One step back
                i++;
            }
            if(part[i] == part[j] && i < j) { // If the start element is equal to the start point of the end element i One step back
                i++;
            } else {        // Exchange values. When the end element is less than the reference point or the start element is greater than the reference point. Exchange location
                int temp = part[i];
                part[i] = part[j];
                part[j] = temp;
            }
        }
        // Until the benchmark element is found, all the smaller ones in front and the larger ones in the back can be sorted recursively on both sides.
        if(i-1 > s) part = qSort(part, s , i-1);
        if(j+1 < e) part = qSort(part, j+1 , e);
        return part;
    }

    /*
        Merge Sort is an effective and stable sorting algorithm based on merge operation,
        The algorithm is a very typical application of Divide and Conquer. Will have
        The ordered subsequences are combined to obtain a completely ordered sequence; That is, first make each subsequence orderly, and then make subsequences
        Sequence segments are ordered. If two ordered tables are merged into one, it is called two-way merging+
        Second only to quick sort
     */
    private static void mergeSort(int[] arr) {
        int n = arr.length;
        mergeSort(arr, 0 , n-1);
        System.out.println(Arrays.toString(arr));
    }

    private static int[] mergeSort(int[] nums, int l, int r) {
        if(l == r) return new int[]{nums[l]};// Subsequence of only one element

        int mid = l + (r-l) / 2;
        //Left ordered array
        int[] leftArr = mergeSort(nums, l, mid);
        //Right ordered array
        int[] rightArr = mergeSort(nums, mid+1, r);
        //New ordered array
        int[] retArr = new int[leftArr.length+rightArr.length];
        int m = 0, i = 0, j = 0;
        // Compare the elements of the left and right arrays one by one and merge them into an ordered new array
        while (i < leftArr.length && j < rightArr.length) { // i/j All satisfied
            retArr[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        //When a left or right array is merged first, then a single merge is performed
        while (i < leftArr.length) {
            retArr[m++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            retArr[m++] = rightArr[j++];
        }

        return retArr;
    }

    public static void main(String[] args) {
        int[] arr = {3,5,1,-7,4,9,-6,8,10,4};
        long s = System.nanoTime();
//        bubbleSort(arr);
//        quickSort(arr);
//        mergeSort(arr);
        long e = System.nanoTime();
        System.out.println(e-s);
    }
}

 

Tags: Java

Posted by apol on Mon, 09 May 2022 14:23:16 +0300