Bubble sort

The simplest sort algorithm

Time complexity

O (N squared)

Train of thought

For each element I, if equal to the next adjacent element, the position is swapped

code

function bubbleSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        for(let j = 0; j < arr.length - 1 - i; j++){
            if(arr[j] > arr[j+1]){
                swap(arr,j,j+1); }}}console.log(arr);
}
function swap(arr,i,j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
bubbleSort([1.3.5.4.3.2.1.5.7.4.3.1])
Copy the code

public class BubbleSort{
    public static void main(String[] rgs){
        int[] nums = {1.3.5.7.6.5.4.3.2.1.7};
        bubbleSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void bubbleSort(int[] arr){
        for(int i = 0; i < arr.length-1; i++){
            for(int j = 0; j < arr.length - 1 - i; j++){
                if(arr[j] > arr[j+1]) {int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}
Copy the code

Selection sort

Time complexity

O (n squared)

Train of thought

In each cycle, the smallest element in the unsorted interval is found, and the first element of the unsorted interval is swapped, and the whole interval is gradually sorted into the sorted interval

code

function selectSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        let min = i;
        for(let j = i + 1; j < arr.length; j++){
            if(arr[j] < arr[min]){ min = j; } } swap(arr,i,min); }}function swap(arr,i,j){
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
Copy the code

public class SelectSort{
    public static void main(String[] args){
        int[] nums = {1.3.5.6.5.4.3.2.1};
        selectSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void selectSort(int[] nums){
        for(int i = 0; i < nums.length - 1; i++){
            int min = i;
            for(int j = i + 1; j < nums.length; j++){
                if(nums[j] < nums[min]){ min = j; } } swap(nums,i,min); }}public static void swap(int[] nums, int i, int j){
        inttemp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Copy the code

Insertion sort

Time complexity

O (N squared)

Train of thought

Divide the entire interval into two pieces, sorted and unsorted. Starting with the first element, look forward and swap if nums[I] < nums[i-1]

code

function insertSort(nums){
    for(let i = 1; i < nums.length; i++){
        const temp = nums[i];
        let j = i;
        while(j > 0 && nums[j-1] > temp){
            nums[j] = nums[j-1];
            j--;
        }
        nums[j] = temp
    }
    console.log(nums);
}
Copy the code

public class InsertSort{
    public static void main(String[] args){
        int[] nums = {1.3.5.7.2.4.6.8.7.6.5.4.3.2.1};
        insertSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void insertSort(int[] nums){
        for(int i = 1; i < nums.length; i++){
            int temp = nums[i];
            int j = i;
            while(j > 0 && nums[j-1] > temp){
                nums[j] = nums[j-1]; j--; } nums[j] = temp; }}}Copy the code

Hill sorting

Insert an optimized version of sort

Time complexity

• Worst time complexity: O(N²), O(N*log²N) with special Hill increments, less than O(N²)
• Optimal time complexity: O(N)
• Average time complexity: depends on the choice of Hill increments

Train of thought

Hill sort is an optimization of insertion sort. In insert sort, each element move can only be swapped with neighboring elements, so when a smaller element appears at the back of the array, it takes multiple moves to move to the front. In hill sort, select a step size step, coordinate adjacent elements of step form a group. Insert sort is carried out within each group, which enables fast movement of elements and avoids the extreme situations that occur in insert sort. Step size selection is an important part of Hill sorting, and reasonable step size selection can reduce time complexity. The best known step size sequence is proposed by Sedgewick (1, 5, 19, 41, 109…). In practical coding, length/2 can be used as the starting step and gradually halved

code

function shellSort(nums){
    // Take the step size and halve it each time
    for(let step = nums.length>>1; step >= 1; step = step>>1) {// Insert sort forward
        for(let i = step; i < nums.length; i++){
            let temp = nums[i];
            let j = i;
            while(nums[j-step] > temp){ nums[j] = nums[j-step]; j -= step; } nums[j] = temp; }}console.log(nums);
}
Copy the code

public class ShellSort{
    public static void main(String[] args){
        int[] nums = {1.3.5.7.6.5.4.3.2.1.7};
        sort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void sort(int[] nums){
        for(int step = nums.length / 2; step > 0; step /= 2) {for(int i = step; i < nums.length; i++){
                int temp = nums[i];
                int j = i;
                while(j > 0 && nums[j-1] > temp){
                    nums[j] = nums[j-1]; j--; } nums[j] = temp; }}}}Copy the code

Quick sort

Time complexity

O(N*logN)

Train of thought

1. Each round takes the first element as standard V and divides the range of the array into two parts: those greater than v and those less than v
2. After finding v’s final coordinates, recursively call quickSort to sort the two parts

code

JS version

function sort(arr){
    quickSort(arr,0,arr.length-1);
    return arr;
}

function quickSort(arr,start,end){
    if(start < 0 || end >= arr.length || start >= end)  return;
    const index = partition(arr,start,end);
    quickSort(arr,start,index-1);
    quickSort(arr,index+1,end);
}

function partition(arr,start,end){
    let left = start, right = end, p = start + 1;
    while(left < right){
        if(arr[p] < arr[start]){
            left++;
            p++;
        }else{
            swap(arr,p,right);
            right--;
        }
    }
    swap(arr,start,left);
    return left;
}

function swap(arr,i,j){
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

console.log(sort([1.3.5.7.8.6.4.2.1.4.5.6.3]))
Copy the code

Java version

public class QuickSort{
    public static void main(String[] args){
        int[] arr = {1.3.5.7.9.8.6.4.2.4.7};
        quickSort(arr,0,arr.length-1);
        for(int n : arr)
            System.out.println(n);
    }
    public static void quickSort(int[] arr,int start,int end){
        if(start < 0 || end >= arr.length || start >= end) return;
        int index = partition(arr,start,end);
        quickSort(arr, start, index-1);
        quickSort(arr, index+1, end);
    }

    public static int partition(int[] arr, int start, int end){
        int left = start, 
            right = end,
            p = start + 1;
        while(left < right){
            if(arr[p] < arr[start]){
                p++;
                left++;
            }else{
                swap(arr,p,right);
                right--;
            }
        }
        swap(arr,start,left);
        return left;
    }

    public static void swap(int[] arr, int i, int j){
        inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the code

Merge sort

The classic application of divide-and-conquer

Time complexity

O(N*logN)

Train of thought

Now divide the array into two parts, sort the two subarrays separately and merge them together, which is the answer

code

function sort(arr){
    mergeSort(arr,0,arr.length-1);
    console.log(arr);
}
function mergeSort(arr,start,end){
    if(end === start) return;
    let mid = Math.floor((end + start) / 2);
    mergeSort(arr,start,mid);
    mergeSort(arr,mid+1,end);
    merge(arr,start,mid,end);
}
function merge(arr,start,mid,end){
    let l = start, r = mid+1, temp = [];
    while(l <= mid && r <= end){
        if(arr[l] < arr[r]){
            temp.push(arr[l++]);
        }else{ temp.push(arr[r++]); }}while(l <= mid){
        temp.push(arr[l++]);
    }
    while(r <= end){
        temp.push(arr[r++]);
    }
    for(let i = start; i <= end; i++){
        arr[i] = temp[i-start];
    }
}

sort([1.3.5.7.2.4.6.8.7.6.5.4.3.2.1])
Copy the code

public class MergeSort{
    public static void main(String[] args){
        int[] nums = {1.3.5.7.2.4.6.8.7.6.5.4.3.2.1};
        mergeSort(nums,0,nums.length-1);
        for(int n : nums)
            System.out.println(n);
    }
    public static void mergeSort(int[] nums, int start, int end){
        if(start == end)    return;
        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, end);
    }
    public static void merge(int[] nums, int start, int mid, int end){
        int l = start, r = mid + 1, cur = 0;
        int[] temp = new int[end-start+1];
        while(l <= mid && r <= end){
            if(nums[l] < nums[r]){
                temp[cur++] = nums[l++];
            }else{ temp[cur++] = nums[r++]; }}while(l <= mid){
            temp[cur++] = nums[l++];
        }
        while(r <= end){
            temp[cur++] = nums[r++];
        }
        for(inti = start; i <= end; i++){ nums[i] = temp[i-start]; }}}Copy the code

Heap sort

Time complexity

O(NlogN)

Train of thought

1. Collates the given array into a large top heap
   

   Big top heap: A special binary tree. For each node, the value of its children must be less than itself

2. Swap the top element with the last element in the heap, treating it as moving out of the big top heap
3. Rearrange the remaining elements into the big top heap
4. Repeat the process until there is only one element in the heap

code

function heapSort(nums){
    // Build a big top heap
    buildMaxHeap(nums);

    // Swap the top element of the big top heap with the last element in the heap and move it out of the big top heap
    for(let i = nums.length-1; i > 0; i--){
        swap(nums,0,i);

        // Rearrange the rest into a big top heap
        heapify(nums,0,i-1);
    }
    console.log(nums);
}

/** * assembles numbers into a big top heap */
function buildMaxHeap(nums){
    const len = nums.length;
    let leaf = len>>1;
    for(; leaf>=0; leaf--){
        heapify(nums,leaf,len-1); }}/** * collate the subtree of nums with I as root into a large top heap */
function heapify(nums,i,len){
    // The child pointer points first to the left child
    let child = i*2+1;

    // If out of range, return
    if(child > len) return;

    // If the right child exists, point the child to the larger of the child nodes
    if(child < len && nums[child+1] > nums[child]){
        child++;
    }

    // If the child node is larger than the root node, the two nodes are switched and heapify is recursively called
    if(nums[child] > nums[i]){ swap(nums,i,child); heapify(nums,child,len); }}function swap(nums,i,j){
    const temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

heapSort([1.3.5.7.2.4.6.8.7.6.5.4.3.2.1])
Copy the code

public class HeapSort{
    public static void main(String[] args){
        int[] nums = {1.3.5.7.2.4.6.8.7.6.5.4.3.2.1};
        HeapSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void HeapSort(int[] nums){
        buildMaxHeap(nums);
        for(int i = nums.length-1; i > 0; i--){
            swap(nums,0,i);
            heapify(nums,0,i-1); }}public static void buildMaxHeap(int[] nums){
        int len = nums.length;
        int leaf = len>>1;
        for(; leaf >= 0; leaf--){
            heapify(nums,leaf,len-1); }}public static void heapify(int[] nums, int root, int len){
        int child = root * 2 + 1;
        if(child > len) return;
        if(child < len && nums[child+1] > nums[child]){
            child++;
        }
        if(nums[child] > nums[root]){ swap(nums,child,root); heapify(nums,child,len); }}}Copy the code

Count sorting

Time complexity

When the input element is n integers between 0 and k, its running time is O(n + k)

Train of thought

Counting sort is a non-comparison algorithm.

1. First determine the maximum value of the array. Construct an extra spacebucketIs used to store the number of occurrences of each data
2. Go through the number group and count the number of occurrences of each data
3. traversebucketWrites the number to the array to be sortednums

code

function countSort(nums,max){
    const bucket = Array(max+1).fill(0);
    let index = 0;
    for(let item of nums){
        bucket[item]++;
    }
    for(let i = 0; i < bucket.length; i++){while(bucket[i] > 0){ nums[index++] = i; bucket[i]--; }}console.log(nums);
}
Copy the code

import java.util.Arrays;
public class CountSort{
    public static void main(String[] args){
        int[] nums = {1.3.5.7.2.4.6.8.7.6.5.4.3.2.1};
        countSort(nums,8);
        for(int n : nums)
            System.out.println(n);
    }
    public static void countSort(int[] nums, int max){
        int[] bucket = new int[max+1];
        int index = 0;
        Arrays.fill(bucket,0);
        for(int i:nums){
            bucket[i]++;
        }
        for(int i = 0; i <= max; i++){
            while(bucket[i] > 0){ nums[index++] = i; bucket[i]--; }}}}Copy the code

Bucket sort

Time complexity

Bucket sorting uses linear time, O (n), when the values in the array to be sorted are evenly distributed.

Train of thought

1. Now allocate the array into a limited number of buckets (try to distribute evenly)
2. Sort the elements in each bucket (recursively calling bucket sort or using other sorting methods)
3. Consolidates the bucket elements into the array to be sorted

code

function bucketSort(nums){
    if(nums.length <= 1)    return;
    // The maximum and minimum values in the array
    const min = Math.min(... nums);const max = Math.max(... nums);// The volume of the bucket is set to 5
    const bucketSize = 5;

    // The number of barrels
    const bucketNum= Math.floor((max - min) / bucketSize) + 1;

    // The bucket used to store each group of data
    const bucket = Array(bucketNum).fill(0).map(() = > []);

    for(let n of nums){
        const idnex = Math.floor((n-min) / bucketSize);
        bucket[idnex].push(n);
    }
    let cur = 0;
    for(let i = 0; i < bucketNum; i++){
        if(bucket[i].length > 0) {// Sort the elements in the bucket by insertion sort. You can use any sort algorithm
            insertSort(bucket[i]);
            for(let j = 0; j < bucket[i].length; j++){
                nums[cur++] = bucket[i][j]
            }
        }
    }
    console.log(nums);
}
Copy the code

import java.util.Arrays;
public class BucketSort{
    public static void main(String[] args){
        int[] nums = {1.3.5.7.2.4.6.8.7.6.5.4.3.2.1};
        bucketSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void bucketSort(int[] nums){
        int max = nums[0], min = nums[0];
        for(int i:nums){
            if(i > max) max = i;
            else if(i < min) min = i;
        }
        int bucketNum = 5, bucketSize = nums.length;
        int[][] bucket = new int[bucketNum][bucketSize];
        int[] bIndex = {0.0.0.0.0};
        for(int i=0; i<bucketNum; i++){ Arrays.fill(bucket[i],-1);
        }
        for(int i: nums){
            int index = (i-min) / bucketSize - (i-min) % bucketSize == 0 ? 0 : 1;
            bucket[index][bIndex[index]++] = i;
        }
        int cur = 0;
        for(int i = 0; i < bucketNum; i++){
            Arrays.sort(bucket[i]);
            for(int n:bucket[i]){
                if(n ! = -1){
                    nums[cur++] = n;
                }
            }
        }
    }
}
Copy the code

Radix sort

Only applicable to integers, decimals with a finite number of digits, and well-formed strings (such as dates)

Train of thought

For some n – bit integers, n rounds of sorting from the lowest to the highest are required. Ten buckets are used, each representing the data whose digits are 0-9. In each cycle, it allocates and collects

• distribution: Allocates data to a bucket based on a digit
• recycling: Retrieves all data from each bucket in turn and writes it to the original array

After the last collection, the original array is updated.

code

function radixSort(nums){
    // Find the length of the number
    const len = String(Math.max(... nums)).length;const bucket = Array(10).fill(0).map(() = > []);
    
    for(let i = 0; i < len; i++){
        // Sort each digit, starting with the last
        assign(bucket,nums,i);

        // After a round of sorting is complete, recycle
        recycle(bucket,nums);
    }
    console.log(nums)
}

function assign(bucket,nums,i){
    for(let n of nums){
        constbit = getBit(n,i); bucket[bit].push(n); }}function recycle(bucket,nums){
    let cur = 0;
    for(let i = 0; i < bucket.length; i++){
        for(let n ofbucket[i]){ nums[cur++] = n; } bucket[i] = []; }}/** * get the i-th bit from the right of the number n, counting from 0 */
function getBit(n,i){
    const str = String(n);
    const index = str.length - 1 - i;
    return index >= 0 ? Number(str[index]) : 0;
}

radixSort([99.189.204.357.100.121.156.80])
Copy the code

import java.util.Arrays;
public class RadixSort{
    public static void main(String[] args){
        int[] nums = {999.189.204.357.100.121.156.800};
        radixSort(nums);
        for(int n : nums)
            System.out.println(n);
    }
    public static void radixSort(int[] nums){
        int len = (nums[0] + "").length();
        int[][] bucket = new int[10][nums.length];
        for(int i = 0; i < 10; i++){
            Arrays.fill(bucket[i],-1);
        }
        for(int i = 0; i < len; i++){
            int[] cur = {0.0.0.0.0.0.0.0.0.0}; assign(bucket, cur, nums, i); recycle(bucket, nums); }}public static void assign(int[][] bucket, int[] cur, int[] nums, int i){
        for(int n: nums){
            intbit = getBit(n,i); bucket[bit][cur[bit]++] = n; }}public static void recycle(int[][] bucket, int[] nums){
        int cur = 0;
        for(int i = 0; i < 10; i++){
            for(int n: bucket[i]){
                if(n ! = -1){
                    nums[cur++] = n;
                }
            }
            bucket[i] = new int[nums.length];
            Arrays.fill(bucket[i],-1); }}public static int getBit(int n, int i){
        int len = (n + "").length();
        if(len <= i) return 0;
        int x = n % (int)Math.pow(10,i);
        int y = n % (int)Math.pow(10,i+1);
        return (y - x) / (int)Math.pow(10,i); }}Copy the code