For simplicity, all examples are in positive order by default, and reverse order is not considered!

To prepare

Before starting, I made the following preparations:

  • A computer with power on
  • JDK8 OR JDK11
  • JUnit5
  • Idea
  • Lombok (optional, I’m used to using this to print logs)

An abstract interface:

public interface Sort<E> {
    E[] sort();
}
Copy the code

A test case:

@Slf4j
class SortTest {
    Integer[] integers;

    Sort<Integer> sort;

    @BeforeEach
    void setUp(a) {
        integers = new Integer[]{3.7.2.1.4.8.9.8.5.6.0};
        log.info("Before sort: {}", Arrays.toString(integers));
    }

    @AfterEach
    void tearDown(a) {
        assertSort(sort.sort());
    }

    @Test
    void bubbleSortTest(a) {
        sort = new BubbleSort(integers);
    }

    @Test
    void insertSortTest(a) {
        sort = new InsertSort(integers);
    }

    @Test
    void selectSortTest(a) {
        sort = new SelectSort(integers);
    }

    private void assertSort(Integer[] sort) {
        log.info("After sort: {}", Arrays.toString(sort));
        assertAll(
                () -> assertEquals(integers.length, sort.length),
                () -> assertEquals(0, sort[0]),
                () -> assertEquals(9, sort[sort.length - 1]),
                () -> assertEquals(1, sort[1]),
                () -> assertEquals(2, sort[2]),
                () -> assertEquals(3, sort[3]),
                () -> assertEquals(4, sort[4]),
                () -> assertEquals(5, sort[5]),
                () -> assertEquals(6, sort[6]),
                () -> assertEquals(7, sort[7]),
                () -> assertEquals(8, sort[8]),
                () -> assertEquals(8, sort[9])); }}Copy the code

Bubble sort

When it comes to bubble sorting, all descriptions are pale, but watch this diabolical video and you’ll see

www.bilibili.com/video/BV1xW…

public class BubbleSort implements Sort<Integer> {

    private final Integer[] elements;

    public BubbleSort(Integer[] elements) {
        this.elements = elements;
    }

    @Override
    public Integer[] sort() {
        int length = elements.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - i - 1; j++) {
                // If the current digit is greater than the next digit, then switch places and continue to compare backwards
                if (elements[j] > elements[j + 1]) {
                    Integer temp = elements[j];
                    elements[j] = elements[j + 1];
                    elements[j + 1] = temp;
                }
                // Currently less than or equal to the next digit, starting from the next digit}}returnelements; }}Copy the code

Insertion sort

  1. Insert sort divides the array into two regions, sorted and unsorted
  2. When sorting begins, the first element of the array defaults to the sorted region
  3. Each round of sorting compares the first element in the unsorted area with the element in the sorted area. If the unsorted element is smaller than the current sorted element, this is the insertion point
    • The element after the insertion point is shifted backwards
    • Insert the unsorted elements here
  4. Otherwise, the unsorted element is inserted to the end of the sorted area, that is, the array is not moved and the next bit of the unsorted area is compared again
public class InsertSort implements Sort<Integer> {

    private Integer[] elements;

    public InsertSort(Integer[] elements) {
        this.elements = elements;
    }

    @Override
    public Integer[] sort() {
        int sortedLength = 1;
        int unSortedLength = elements.length - 1;

        for (int i = 0; i < unSortedLength; i++) {
            // The first element in the unsorted range
            Integer unSort = elements[sortedLength];
            // Compare to sorted elements
            for (int j = 0; j < sortedLength; j++) {
                // 1. Sorted area: if unSort is larger than all of them, it is the last one in the sorted area
                // 2. Sorted area: if unSort is less than this bit, the sorted area is before this bit
                if (unSort < elements[j]) {
                    rightMoveOnePlace(sortedLength, j, elements);
                    elements[j] = unSort;
                    break;
                }
                // 3. Sorted region: if unSort is greater than this, the next digit is compared
            }
            sortedLength++;
        }

        return elements;
    }

    /** * moves the array 1 bit to the right from the specified position@paramEndMoveElementIndex Number of elements to end a move *@paramStartMoveElementIndex Where the element starts to move *@paramElements The array to operate on */
    private void rightMoveOnePlace(int endMoveElementIndex, int startMoveElementIndex, Integer[] elements) {
        for (int k = 0; k < endMoveElementIndex - startMoveElementIndex; k++) {
            elements[endMoveElementIndex - k] = elements[endMoveElementIndex - k - 1]; }}}Copy the code

Selection sort

  1. Selection sort is also divided into sorted and unsorted areas
  2. When the sort starts, there are no elements in the unsorted region
  3. Starting with the first element in the unsorted area, compare the smallest element to all subsequent elements and place it at the end of the sorted area
public class SelectSort implements Sort<Integer> {

    private Integer[] elements;

    public SelectSort(Integer[] elements) {
        this.elements = elements;
    }

    @Override
    public Integer[] sort() {
        for (int unSortIndex = 0; unSortIndex < elements.length - 1; unSortIndex++) {
            int min = elements[unSortIndex];
            int minIndex = unSortIndex;
            for (int j = unSortIndex + 1; j < elements.length; j++) {
                if(elements[j] < min) { min = elements[j]; minIndex = j; }}// If the value is equal, the first element in the unsorted area is already the minimum value, and there is no need to swap places
            if (minIndex != unSortIndex) {
                elements[minIndex] = elements[unSortIndex];
                elements[unSortIndex] = min;
            }
        }
        returnelements; }}Copy the code

The last

The time complexity of these sorting algorithms is O(n2)O(n^2)O(n2).

In the process of sorting, no new array space is applied, all are completed on the basis of the original array, so these are in situ sorting algorithm, their space complexity is O(n)O(n)O(n) O(n)

Next we’ll look at merge and quicksort

If you feel helpful to yourself, please give a thumbs-up, this will be the biggest encouragement to me ~~~