This is the 7th day of my participation in Gwen Challenge

  • Bubble Sort

    Bubble sort is a stable sorting algorithm (when there are two adjacent elements of the same size, we do not swap), the time complexity of O(n2){O(n^2)}O(n2), in situ sorting algorithm (space complexity of O(1){O(1)}O(1)). And the idea is that if you switch the order of two numbers, you’ll get at least one number to where it’s supposed to be, n times.

    The code implementation is as follows, the point that can be optimized is to remember the position of the last exchange; There is no exchange, early exit.

    static int[] bubbleSort(int[] items, int length) { if (length <= 1){ return items; } // lastExchange position, optimize int lastExchange = 0; int sortBorder = length - 1; for (int i = 0; i < length; i++) { System.out.println(items[i]); // Early exit flag bit, optimize Boolean flag = false; for (int j = 0; j < sortBorder; j++) { if (items[j] > items[j+1]){ swap(items,j,j+1); flag = true; lastExchange = j; } } sortBorder = lastExchange; if (! Flag){// No data exchange, exit early break; } } return items; } static void swap(int[] sortItems,int a,int b){ int temp = sortItems[a]; sortItems[a] = sortItems[b]; sortItems[b] = temp; }Copy the code

  • Insection Sort

    Insert sort is an in-place sort algorithm. For elements with the same value, we can choose to insert the elements that appear later after the elements that appear before, so that the original order can be kept unchanged. Therefore, insert sort is a stable sorting algorithm. Time complexity O(n2){O(n^2)}O(n2).

    The idea is that the sorted interval, the unsorted interval, the elements of the unsorted interval are inserted one by one into the appropriate place of the sorted interval.

    It’s not as simple as bubbling sort, because it’s sort in place, and it’s kind of like quicksort where you assign one value to another, and then you assign the original value back, so it’s a little bit tricky to write, it’s a lot harder to write than bubbling.

        public static void insertionSort(int[] a, int length) {
        if (length == 1) {
            return;
        }
        for (int i = 1; i < length; i++) {
            int value = a[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (a[j] > value){
                    a[j+1] = a[j];
                } else {
                    break;
                }
            }
            a[j+1] = value; // Set j+1 to value}}Copy the code

    If the first number is greater than the second number, assign the second number to the first number. Then exit the inner loop and assign the (j+1) number to the second number. If the third number is larger than the first or second number, continue the loop. If it is smaller than the second number, repeat the preceding until the end. If you understand the idea, it’s easy to write it down.

    If the last value is the smallest, then the last time you sort, the last value is going to move all the way from the tail to the head.

  • Selection Sort

    Select sort is like insert sort, but there are sorted and unsorted ranges. But select sort will find the smallest element in the unsorted range each time and place it at the end of the sorted range.

    Selection sort is an in-place sort algorithm that destroys stability (and is therefore slightly less efficient than bubbling and insertion sort) by finding the minimum of the remaining unsorted elements each time and swapping places with the preceding element. The best/worst/average time complexity is O(n2){O(n^2)}O(n2).

    The specific code is as follows:

        public static void selectionSort(int[] items, int length) {
        if (length <= 1) return;
        for (int i = 0; i < length - 1; i++) {
            // Find the minimum value
            int minIndex = i;
            for (int j = i + 1; j < length; j++) {
                if(items[j] < items[minIndex]){ minIndex = j; }}/ / exchangeswap(items,i,minIndex); }}private static void swap(int[] items,int i,int j){
        int temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }
Copy the code