Sorting, java code implementation

Seven major rankings based on comparison

The seven major rankings are:
1. Insertion sort
2. Hill Sorting
3. Selective Sorting
4. Heap sorting
5. Bubble Sorting
6. Quick Sorting
7. Merge Sort

These seven sorts belong to the In-Place type, i.e. in-place sort.

Insert Sort:
Sorting of subtraction algorithms
Select the first number each time from the disordered period and insert it into the proper position of the ordered interval
Process:
Each time the first number of the disordered area is traversed in the ordered area to find the appropriate location and move the original data.

Time Complexity: Best O (n) Worst O (n_) Average O (n_)
Spatial complexity: O (1)
Stability: Stability

Note: Stability: Ensuring that the relative order of the same data in the sorting process remains unchanged
Insert sorting, the closer to ordering, the more efficient execution time

Code implementation:

public static void insertSort(int[] array) {//Insertion sort
        for (int i = 0; i < array.length - 1; i++) {
            //Ordered interval [0,i]
            //Disordered interval [i+1,array.length]
            //Data array[i+1] to be inserted
            int j;
            int key = array[i + 1];
            for (j = i; j >= 0; j--) {
                if (key >= array[j]) {
                    break;
                }
                array[j + 1] = array[j];//Move and empty the insertion position.
            }
            array[j + 1] = key;
        }
    }

Hill Sort:
Prerequisite: The closer the data is to order, the more efficient the time is in insertion sort.
Pre-grouping (grouping and arranging) before inserting and sorting to make the data as orderly as possible
Dynamic grouping: A lot at first, then less and less

Time complexity:
Best o(n) Mean O(n^1.3-1.4) Worst O (n^2)
Spatial complexity: O(1)
Stability: Instability (equal numbers do not necessarily fall into the same group)

Code implementation:

 private static void insertSortGap(int[]array,int gap){//Insertion sort used in Hill sort
        for (int i = 0; i < array.length - gap; i++) {

            int j;
            int key = array[i + gap];
            for (j = i; j >= 0; j-=gap) {
                if (key >= array[j]) {
                    break;
                }
                array[j + gap] = array[j];//Move and empty the insertion position.
            }
            array[j + gap] = key;
        }
    }

    public static void shellSort(int[] array){//Hill Sort Main Part
        int gap = array.length;
        while(true){
            gap=gap/3 +1;
            insertSortGap(array,gap);
            if (gap==1){
                return;
            }

        }
    }

Selective Sorting (Direct Selective Sorting/Heap Sorting)

Every time I traverse the disordered interval, I find the maximum number of disordered intervals.
Put the maximum in the left back door of the disordered interval
After selecting n - 1 (n) number all the time, the data is completely ordered.

Time complexity O(n^2) data is insensitive
Spatial complexity O(1)
Stability: instability

Code implementation:

public static void selectSort(int[] array){//Selective Sorting
        for (int i = 0;i<array.length - 1;i++){
            //Unordered interval [0,array.length - 1]
            //Ordered interval [array.length - 1,array.length]
            int max = 0;
            for (int j = 1;j<array.length - 1;j++){
                if (array[j]>array[max]){
                    max = j;
                }
            }
            swap(array,max,array.length-i-1);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i]= array[j];
        array[j]= array[i];
    }

Heap sorting
Use the idea of heap to sort by heap and heap array

Time complexity: O (n*log(n)) data insensitive
Spatial complexity: O (1)
Stability: instability

Code implementation:

 public static void heapify(int[] array,int size, int index) {
        while (true) {
            int left = index * 2 + 1;
            if (left >= size) {
                return;
            }

            int max = left;
            if (left + 1 < size && array[left + 1] > array[left]) {
                max = left + 1;
            }
            if (array[index] >= array[max]) {
                return;
            }

            swap(array, index, max);
            return;
        }
    }

    public static void createHeap(int[] array, int size){
        //parent = (child-1)/2
        for(int i =(size-2)/2;i>=0;i--){
            heapify(array,size,i);
        }
    }

    public static void heapSort(int[] array){//Main body
        createHeap(array,array.length);
        for (int i = 0;i<array.length - 1;i++){
            swap(array,0,array.length-i-1);
            heapify(array,array.length-i-1,0);
        }
    }

Tags: less

Posted on Tue, 27 Aug 2019 22:50:48 -0700 by vaavi8r