Classic sorting algorithm

Several common sorting algorithms are listed here: 1. Selective sorting, 2. Bubble sorting, 3. Insert sorting, 4. Merge sorting, 5. Quick sorting, 6. Heap sorting, 7. Count sorting, 8. Cardinal sorting.

Catalog

1. Select Sort

2. Bubble sorting

3. Insert Sort

4. Merge Sort

5. Quick Sort

6. Heap Sorting

7. Count Sort O(N)

8. Cardinal Sort O(N)

Time ComplexitySpatial Complexitystability
Select SortO(N^2)O(1)NO
Bubble sortO(N^2)O(1)YES
Insert SortO(N^2)O(1)YES
Merge SortO(N*logN)O(N)YES
Quick SortO(N*logN)O(logN)NO
Heap SortingO(N*logN)O(1)NO

1. Select Sort

That is, after each round, find the smallest one and put it first. After each round, select one, N-1 round complete.

The first round traverses N data, the second round N-1 data..., and the time complexity is O(n^2) from the sum formula of equal difference columns.

The Java code is as follows:

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++){
            minIndex=arr[j]<arr[minIndex]?j:minIndex;
        }
        swap(arr,i,minIndex);
    }
    
}

//If i and j are in one place, errors will occur;
public static void swap(int[] arr,int i,int j){
    arr[i]=arr[i]^arr[j];
    arr[j]=arr[i]^arr[j];
    arr[i]=arr[i]^arr[j];

}

2. Bubble sorting

That is, the two compare with each other, and the larger one goes forward to continue the comparison. After each round, place the largest one at the end of the unplanned data and complete the N-round.

Sum Formula from Equal Difference Sequence: Easy Time Complexity O(n^2)

The Java code is as follows:

public static void bubbleSort(int[] arr){
    if(arr==null||arr.length<2){
        return ;
    }

    for(int e=arr.length-1;e>0;e--){
        for(int i=0;i<e;i++){
            if(arr[i]>arr[i+1]){
                swap(arr,i,i+1);
            }
        }    
    }
}

3. Insert Sort

That is, traverse each value in the array, compare it with the previous one, swap if it is less than, and continue to compare forward;

As the image shows, the efficiency of insertion sorting varies with the data, with the worst time complexity being O(n^2).

The Java code is as follows:

public static void insertionSort(int[] arr){
    if(arr==null||arr.length<2){
        return;
    }
    //0~0 is ordered
    //0~i if you want order
    for(int i=1;i<arr.length;i++){
        for(int j=i-1;j>=0&&arr[j]>arr[j+1];j--){
            swap(arr,j,j+1);
        }
    }

}

4. Merge Sort

The whole is a simple recursion, ordered on the left and ordered on the right so that the whole is ordered.

Each time half of the array is divided, recursively so that the left side is ordered and the right side is ordered, then the merge process is performed to make the array ordered as a whole. Merge procedure: The left and right sides are placed together to compare the sizes of each other, the small side enters the auxiliary array first, and the small side continues traversing until a larger number is found.

Time Complexity O(N*logN), Extra Space Complexity O(N).

The Java code is as follows:

public static void porcess(int[] arr,int L,int R){
    if(L==R){
        return;
    }
    int mid =L+((R-L)>>1);
    process(arr,L,mid);//Left Ordered
    process(arr,mid+1,R);//Right Ordered
    merge(arr,L,R);
}

public static void merge(int[] arr,int L,int M,int R){
    int[] help=new int(R-L+1);
    int i=0;
    int p1=L;
    int p2=M+1;
    while(p1<=M&&p2<=R){
        help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
    }
    while(p1<=M){
        help[i++]=arr[p1++];
    }
    while(p2<=M){
    help[i++]=arr[p2++];
    }
    for(i=0;i<help.length;i++){
        arr[L+i]=help[i];
    }
}

5. Quick Sort

It is also a recursive method to randomly select a number in an array so that it is larger on one side than it is, and smaller on the other, and it is skipped when it is encountered. Then recursively, the array is ordered as a whole.

Time Complexity O(N*logN), Extra Space Complexity O(logN), Worst O(N)

The Java code is as follows:

public static void quickSort(int[] arr,int L,int R){
    if(L<R){
        swap(arr,L+(int)(Math.random()*(R-L+1)),R);
        int[] p= partition(arr,L,R);
        quickSort(arr,L,p[0]-1);
        quickSOrt(arr,p[1]+1,R);
    }
}

//This is a function that handles arr[L~R]
//Ar[R] as the default partition value
// Returns the equal area (left boundary, right boundary), so returns an array of length 2.
public static int[] partition(int[] arr,int L,int R){
    int less=L-1;
    int more=R;
    while(L<more){
        if(arr[L]<arr[R]){
            swap(arr,++less,L++);
        }else if(arr[L]>arr[R]){
            swap(arr,--more,L);
        }else{
            L++;
        }
    }
    swap(arr,more,R);
    return new int[] {less+1,more};
}

6. Heap Sorting

1. First, the array to be sorted is constructed into a large root heap, where the maximum value of the entire array is at the top of the heap structure

2. Swap the number at the top with the number at the end, where the number at the end is the maximum and the number of remaining arrays to sort is n-1

3. Construct the remaining n-1 numbers into a large root heap, and then swap the top number with the number at the n-1 position. If this is repeated, an ordered array can be obtained.

Time Complexity O(N*logN), Space Complexity O(1)

The Java code is as follows:

public static void heapSort(int[] arr){
    if(arr==null||arr.length<2){
        return ;
    }
    for(int i=0;i<arr.length;i++){
        heapInsert(arr,i);
    }
    int heapSize=arr.length;
    swap(arr,0,--heapsize);
    while(heapSize>0){
        heapify(arr,0,heapSize);
        swap(arr,0,--heapSize);
    }
}
public static void heapInsert(int[] arr,int index){
    while(arr[index]>arr[(index-1)/2]){
        swap(arr,index,(index-1)/2);
        index=(index-1)/2;
    }
}

public static void heapify(int[] arr,int index,int heapSize){
    int left=index*2+1;

    while(left>heapSize){
        int largest=left+1<heapSize&&arr[left+1]>arr[left]?left+1:left;
        largest=arr[largest]>arr[index]?largest:index;
        if(lagest==index){
            break;
        }
        swap(arr,largest,index);
        index=largest;
        left=index*2+1;
    }
}

public static void swap(int[] arr,int i,int j){
    int tmp=arr[i];
    arr[i]=arr[j];
    arr[j]=tmp;
}

Sorting under the idea of bucket sorting is not based on comparison and has limited application scope.

7. Count Sort O(N)

Is to prepare a container for storage, similar to word frequency statistics

eg: Give a list of ages, sorted by size

Such as 2, 2, 15, 18, 18, 18, 56, 65

Prepare an array with a minimum of 65, help[65]={0};

Traverse to 2, help[2]++;

Traverse to 15, help[15]++;

Finally, output in sequence, the number of outputs is the value at each location.

8. Cardinal Sort O(N)

To deal with the binary problem, comparing each digit separately is really not very easy to understand and needs to be studied.

1. First find the maximum number of digits, then add 0 to the front of the decimal places.

2. Containers (arrays, queues...) where numbers appear in the data to be given (e.g. 123, 23, 45, 88, 64)

Buckets need to be prepared [1], [2], [3], [4], [5], [6], [8]

3. Look at the position first in order and sort it. If 123 places are 3, put him in barrel 3, 23 places are 3, and put him in barrel 3 as well... and then 10 places until the highest position.

4. Drum out in order to complete sorting;

Tags: Java Algorithm

Posted by slak on Thu, 25 Aug 2022 02:29:44 +0300