Take, for example, sorting from smallest to largest. Three methods of time complexity O(n2)O\left(n^2 \right) O(n2) are introduced.

Reference post blog.csdn.net/meibenxiang…

1. Bubble sort

1. Compare adjacent elements. If the first one is bigger than the second one, they swap. From the first pair at the beginning to the last pair at the end. And finally, the maximum sort area.

2. Repeat the above steps for all elements except the values in the sorting area.

Keep repeating the above steps for fewer and fewer elements until all the numbers are in the sorting area.

/ / ascending public static int [] the bubbleSort (int [] array) {if (array. The length = = 0 | | array. The length = = 1) return array; for(int i = array.length - 1; i >= 0; i--){ for(int j = 0; j < array.length - 1; j++){ if(array[j] > array[j + 1]){ int tmp = array[j]; array[j] = array[j + 1]; array[j + 1] = tmp; } } } return array; }Copy the code

Post a very detailed blog www.cnblogs.com/bigdata-sto…

2. Select sort

1. Locate the smallest element in the unsorted sequence and place it at the top of the sorted sequence.

2. Continue to find the smallest element in the unsorted element and place it at the end of the sorted sequence.

The first unsorted element is used as a baseline, and the rest of the elements are traversed to find the smallest. If the minimum is found among the remaining elements, it is swapped.

Repeat the second step until all elements are sorted.

public static int[] selectionSort(int[] array){ if(array.length == 0 || array.length == 1) return array; for(int i = 0; i < array.length; i++){ int minIndex = i; for(int j = i; j < array.length; j++){ minIndex = array[j] < array[minIndex] ? j: minIndex; } if(minIndex ! = i){ int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp; } } return array; }Copy the code

3. Insert sort

1. Starting with the first element, the element can be considered sorted;

2. Take out the next element and scan from back to front in the left sorting area;

3. If the element in the left sorting area is greater than the new element, the new element moves to the next position until the sorted element is found to be less than or equal to the new element;

4. Insert the new element into this position and repeat until all elements are sorted.

public static int[] insertionSort(int[] array){
    if(array.length == 0 || array.length == 1) return array;

    for(int i = 1;  i < array.length; i++){
        for(int j = i - 1; j >= 0; j--){
            if(array[j] > array[j + 1]){
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array;
}
Copy the code