All the sorting algorithms you want are here!

Bubble Sort is a simple sorting algorithm in the field of computer science. It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if they are in the wrong order (from largest to smallest, from A to Z). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element has been sorted.

The total mean time complexity of bubble sort is O(N2) O(N^2) O(N2). Bubble sort is to move small elements forward or large elements back. A comparison is a comparison of two adjacent elements, and an exchange occurs between the two elements. So, if two elements are equal, they don’t swap; If two equal elements are not adjacent, then even if the two elements are adjacent by the previous pairwise swap, they will not swap, so the order of the same elements does not change, so bubble sort is a stable sorting algorithm.

Quicksort, also known as partition-exchange sort, is a sort algorithm first proposed by Tony Hall. Quicksort is usually significantly faster than other algorithms because its inner loop can be implemented efficiently on most architectures.

On average, sorting items takes O(n L O gn) O(nlogn) O(nlogn) O(nlogn). In fact, quicksort O(n L O gn) O(nlogn) O(nlogn) O(nlogn) is usually significantly faster than other algorithms. Swap a[r] and a[mid] to complete a quicksort. When the central element is exchanged with a[r], it is possible to disrupt the stability of the previous elements, such as the sequence 5, 3, 3, 4, 3, 8, 9, 10, 11. Now the exchange of the central element 5 and 3 (the fifth element, subscript starting from 1) will change the sequence, The stability of the three elements is disrupted (i.e. the last three goes to the front), so quicksort is an unstable sorting algorithm.

Here is a separate hybrid algorithm, based on quicksort, sort of pruning, for the KTH K K large (small) number. The average time complexity of the fast selection algorithm is O(N) O(N) O(N). Like quicksort, this algorithm was invented by Tony Hoare, so it is also known as the Hoare selection algorithm. This method is roughly the same as quicksort. For simplicity, note that the KTH largest element is also the n-k smallest element, so the KTH smallest algorithm can be used to solve this problem.

First, we select a pivot and define its position in the sorted array in linear time. This can be done with the help of partitioning algorithms.

To achieve partitioning, move along the array, compare each element to the pivot, and move all elements smaller than the pivot to the left of the pivot.Copy the code

Thus, in the output array, the pivot is in its proper position. Everything less than the pivot is to its left, and everything greater than or equal to its right. Thus, the array is split into two parts. If it is a quicksort algorithm, it will recursively sort the two parts in order O(N L O gN) O(NlogN) O(NlogN). Here, since we know which part of the smallest n-k element we are looking for, we don’t need to deal with both parts, thus reducing the average time complexity to O(N) O(N) O(N). The final algorithm is quite straightforward:

• Choose a pivot at random.
• Use the partitioning algorithm to place the pivot pos at the appropriate position in the array. Move elements less than the pivot to the left and elements greater than or equal to the pivot to the right.
• Compare POS and n-k to determine which side to continue recursive processing on.

• First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence.
• Find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.
• Repeat the second step until all elements are sorted.

public void selectSort(int[] sourceArray){
    // There are N-1 rounds of comparisons
    for (int i = 0; i < sourceArray.length - 1; i++){
        int cur = i;
        // The number of comparisons per round N- I
        for (int j = i + 1; j < sourceArray.length; j++){
            if (sourceArray[cur] > sourceArray[j]) {
                // Records the index of the smallest element that can be found so farcur = j; }}// Swap the minimum found with the value of the I position
        if(i ! = cur){ sourceArray[i] = sourceArray[i] ^ sourceArray[cur]; sourceArray[cur] = sourceArray[i] ^ sourceArray[cur]; sourceArray[i] = sourceArray[i] ^ sourceArray[cur]; }}}Copy the code

• Start with the first element, which can be considered sorted
• Takes the next element and scans back to front in the sorted element sequence
• If the element (sorted) is larger than the new element, move the element to the next position
• Repeat step 3 until you find a place where the sorted element is less than or equal to the new element
• After inserting the new element into the location
• Repeat steps 2 to 5

public void insertSort(int[] sourceArray){
    // Select the appropriate place to insert from the element with subscript 1, since there is only one element with subscript 0 and the default is ordered
    for (int i = 1; i < sourceArray.length; i++){
        // Record the data to be inserted
        int temp = sourceArray[i];
        // Start from the rightmost of the sorted sequence and find the number less than it
        int j = i;
        while (j > 0 && temp < sourceArray[j - 1]){
            sourceArray[j] = sourceArray[j - 1];
            j--;
        }

        // There is a smaller number, insert
        if (j != i) sourceArray[j] = temp;
    }
}
Copy the code

• The first step is to apply for a space equal to the sum of the two sorted sequences. This space is used to store the combined sequence
• Step 2: Set two Pointers, starting at the start of two sorted sequences
• Step 3: Compare the two Pointers to the element, select the smaller element into the merge space, and move the pointer to the next position
• Repeat step 3 until a pointer exceeds the end of the sequence
• Copies all remaining elements of the other sequence directly to the end of the merged sequence

public int[] mergeSort(int[] sourceArray){
    if (sourceArray.length < 2) return sourceArray;
    int mid = (int) Math.floor(sourceArray.length / 2);
    int[] left = Arrays.copyOfRange(sourceArray, 0, mid);
    int[] right = Arrays.copyOfRange(sourceArray, mid, sourceArray.length);

    return merge(mergeSort(left), mergeSort(right));
}

private int[] merge(int[] left, int[] right){
    int[] nums = new int[left.length + right.length];
    int l = 0;
    int r = 0;
    int i = 0;
    while (l < left.length && r < right.length){
        if (left[l] < right[r]) {
            nums[i] = left[l];
            l++;
        }else {
            nums[i] = right[r];
            r++;
        }
        i++;
    }

    while(l < left.length){ nums[i] = left[l]; l++; i++; }while(r < right.length){ nums[i] = right[r]; r++; i++; }return nums;
}
Copy the code

Suppose there is an original string of values as follows: 73, 22, 93, 43, 55, 14, 28, 65, 39, 81. First assign them to buckets numbered 0 to 9 when visiting values based on the single-digit values:

0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
Copy the code

The buckets are then reconcatenated to form the following sequence of numbers: 81, 22, 73, 93, 43, 14, 55, 65, 28, 39. The allocation is made again, this time by ten digits:

0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
Copy the code

The values in these buckets are then reconcatenated to form the following sequence:14, 22, 28, 39, 43, 55, 65, 73, 81, 93At this time, the whole sequence has been sorted; If the sorted object has more than three digits, the above actions continue until the highest digit is reached.LSDThe cardinality sort of is used for sequences with small bits, or if there are many bitsMSDWill be more efficient.MSDThe way toLSDInstead, allocations are made from the base of the high digit, and instead of being merged back into an array immediately after allocation, subbuckets are created within each bucket, and the values in each bucket are assigned to the next digit. After allocating the lowest number of digits, merge it back into a single array.

public void radixSort(int[] sourceArray){
    int maxDigit = getMaxDigit(sourceArray);
    int mod = 10;
    int dev = 1;

    for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {int[][] counter = new int[mod * 2] [0];
        for (int j = 0; j < sourceArray.length; j++){
            int bucket = ((sourceArray[j] % mod) / dev) + mod;
            counter[bucket] = arrayAppend(counter[bucket], sourceArray[j]);
        }

        int pos = 0;
        for (int[] bucket : counter){
            for (intvalue : bucket){ sourceArray[pos++] = value; }}}}private int getMaxDigit(int[] arr){
    int maxValue = getMaxValue(arr);
    return getNumLength(maxValue);
}

private int getMaxValue(int[] arr){
    int maxValue = arr[0];
    for (int value : arr){
        if(maxValue < value){ maxValue = value; }}return maxValue;
}

private int getNumLength(long num){
    if (num == 0) {return 1;
    }
    int length = 0;
    for (longtemp = num; temp ! =0; temp /= 10){
        length++;
    }
    return length;
}

private int[] arrayAppend(int[] arr, int value){
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
}
Copy the code

So let’s take something less thannThe integerd1As the first increment, group all the records of the file. All distances ared1Records that are multiples of are placed in the same group. Direct insertion sequencing was performed in each group. And then we take the second changeD2 = 1 (<... <d2<d1), that is, until all records are placed in the same group for direct insertion sort.

public void shellSort(int[] sourceArray){
    int gap = sourceArray.length;

    while (true){
        gap /= 2;
        for (int i = 0; i < gap; i++){
            for (int j = i + gap; j < sourceArray.length; j += gap){
                int temp = sourceArray[j];
                int k = j - gap;
                while (k >= 0&& sourceArray[k] > temp){ sourceArray[k + gap] = sourceArray[k]; k -= gap; } sourceArray[k + gap] = temp; }}if (gap == 1) break; }}Copy the code

• Create a heap H[0…… n-1];
• Swap the heap head (maximum) with the heap tail;
• Reduce the size of the heap by 1 and call shift_down(0) to move the top of the new array into position.
• Repeat step 2 until the heap size is 1.

public void heapSort(int[] sourceArray){
    int len = sourceArray.length;
    buildMaxHeap(sourceArray, len);
    for (int i = len - 1; i > 0; i--){
        swap(sourceArray, 0, i);
        len--;
        heapify(sourceArray, 0, len); }}private void buildMaxHeap(int[] arr, int len){
    for (int i = (int) Math.floor(len / 2); i >= 0; i--){ heapify(arr, i, len); }}private void heapify(int[] arr, int i, int len){
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;

    if (left < len && arr[left] > arr[largest]){
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]){
        largest = right;
    }

    if (largest != i){
        swap(arr, i, largest);
        heapify(arr, largest, len);
    }
}

private 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];
}
Copy the code

• Find the largest and smallest elements in the array to be sorted
• Count the number of occurrences of each element of value I in the array, stored in the i-th entry of array C
• Add up all the counts (starting with the first element in C, adding each term to the previous one)
• Reverse populating the target array: place each element I in the C(I) item of the new array, subtracting C(I) by 1 for each element

private static void countingSort(int[] arr, int maxValue) {
    int bucketLen = maxValue + 1;
    int[] bucket = new int[bucketLen];

    for (int value : arr) {
        bucket[value]++;
    }

    int sortedIndex = 0;
    for (int j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; }}}private static int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
        if(maxValue < value) { maxValue = value; }}return maxValue;
}
Copy the code