This is the 19th day of my participation in the August Wenwen Challenge.More challenges in August

Bubble sort

1. Compare in pairs. If the number in front is larger than the number in the back, swap the numbers in these two positions, so that the largest number in the remaining number will be determined after each round and sorted by n-1 round (n is the number of elements).

2. The first order is n-1, then n-2…

3. The number of numbers to be compared in each round is decreasing, because the number of I has been sorted in the previous round of I, and these numbers do not need to be compared

public class Problem02_BubblingSort {
    public static void bubblingSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        for (int i = arr.length - 1; i > 0; i--) {  // N numbers require n-1 rounds
            for (int j = 0; j < i; j++) { // After each round of comparison, we determine the position of a number of comparisons. The number of comparisons is -1
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1); // If the left is larger than the right, switch the two numbers}}}}public static void swap(int[] arr, int i, int j) {
        inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the code

Selection sort

1. Find the smallest unsorted number each time and give its index to minIndex 2. After the loop is completed, swap I and minIndex 3. The first sorted number is 0, then 1, 2…

import java.util.Arrays;
import java.util.Random;

public class Problem03_SelectionSort {
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) { // If the current number is less than the minimum, the minimum is the current valueminIndex = j; } } swap(arr, i, minIndex); }}public static void swap(int[] arr, int i, int j) {
        inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the code

Insertion sort

1. Compare the sorted number with the sorted part on the left. If the sorted number on the left is larger than the current number, switch the two numbers until the number on the left is not smaller than the current number or there is no number on the left, the movement stops.

import java.util.Arrays;
import java.util.Random;

public class Problem04_InsertionSort {
    public static void  insertionSort(int[] arr){
        // Assume that the current number and the left position are sorted
        for(int i=0; i<arr.length-1; i++){// This loop represents the number of rounds to sort, and I represents the part 0- I that has been sorted
            for(intj=i; j>=0&&arr[j+1]<arr[j]; j--){// Sort by j+1
                swap(arr,j,j+1); }}}public static void swap(int[] arr, int i, int j) {
        inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the code

Time complexity

All three simple sorts have O(N^2) time, but insert sort performs better than the other two because it behaves differently depending on the state of the data

Spatial complexity

All three of these simple sorts have order one space.