1. Direct insert sort

Basic idea: insert one record to be sorted into the previously ordered subsequence according to its keyword size until all records are inserted.
Time complexity: O ( n 2 ) O(n^2) O(n2)

void insertSort(vector<int>& array) {
    for (int i = 1; i < array.size(); i++) {
        if (array[i] < array[i - 1]) {
            int temp = array[i];
            int index = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (array[j] > temp) {
                    array[j + 1] = array[j];
                } else {
                    index = j + 1;
                    break;
                }
            }
            array[index] = temp;
        }
    }
}

2. Hill sort (reduce incremental sort)

Basic idea: first divide the table to be sorted into several special sub tables in the form of [i, i+d, i+2d, '', i+kd], that is, the records separated by a certain "increment" form a sub table, and directly insert and sort each sub table respectively. When the elements in the whole table are "basic order", then directly insert and sort all records once.
Time complexity: O ( n 2 ) O(n^2) O(n2)

void shellSort(vector<int>& array) {
    for (int i = array.size()/2; i>=1; i/=2) {
        for (int j = i; j < array.size(); j++) {
            if (array[j] < array[j - i]) {
                int temp = array[j];
                int index = j % i;
                for (int k = j - i; k >= 0; k-=i) {
                    if (array[k] > temp) {
                        array[k + i] = array[k];
                    } else {
                        index = k + i;
                        break;
                    }
                }
                array[index] = temp;
            }
        }
    }
}

3. Bubble sorting

Basic idea: compare the values of adjacent elements from front to back (or from back to front). If it is in reverse order, exchange them until the sequence comparison is completed.
Time complexity: O ( n 2 ) O(n^2) O(n2)

void bubbleSort(vector<int>& array) {
    for (int i = 0; i < array.size(); i++) {
        bool flag = false;
        for (int j = 0; j < array.size() - 1 - i; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
                flag = true;
            }
        }
        if (!flag) {
            return;
        }
    }
}

4. Quick sort

Basic idea: the basic idea of quick sort is based on divide and conquer. Take any element pivot in the table to be sorted L[0... n-1] as the pivot, and divide the table into two parts L[0... k-1] and L[k... n-1] through one sort, so that the elements in L[0... k-1] are less than or equal to pivot, and the elements in L[k... n-1] are greater than or equal to pivot. Finally, put the pivot on its final position L(k), This process is called a partition, and then repeat the above process for the two sub tables respectively until each part has only one element or is empty. At this time, all elements are placed in their final position.
Time complexity: O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)

int partition(vector<int>& array, int low, int high) {
    int pivot = array[low];
    while (low < high) {
        while (low < high && array[high] >= pivot) {
            high--;
        }
        array[low] = array[high];
        while (low < high && array[low] <= pivot) {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = pivot;
    return low;
}

void quickSort(vector<int>& array, int low, int high) {
    if (low < high) {
        int pivot = partition(array, low, high);
        quickSort(array, low, pivot - 1);
        quickSort(array, pivot + 1, high);
    }
}

5. Simple selection sort

Basic idea: select the smallest element in the elements to be sorted in each trip (such as the i-th trip) and take it as the i-th element of the ordered sequence until all elements are sorted.
Time complexity: O ( n 2 ) O(n^2) O(n2)

void selectSort(vector<int>& array) {
    for (int i = 0; i < array.size(); i++) {
        int min = i;
        for (int j = i + 1; j < array.size(); j++) {
            if (array[min] > array[j]) {
                min = j;
            }
        }
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}

6. Heap sort

Basic idea: build the n elements to be sorted into the initial heap. Due to the characteristics of the heap itself, the top element of the heap is the maximum value. Output the top elements, then send the bottom elements to the top, repeat the process, and sort n elements in turn.
Time complexity: O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)

void headAdjust(vector<int>& array, int k, int len) {
    int temp = array[k];
    for (int i = 2*k+1; i <= len; i = 2*i+1) {
        if (i < len && array[i] < array[i+1]) {
            i++;
        }
        if (temp > array[i]) {
            break;
        } else {
            array[k] = array[i];
            k = i;
        }
    }
    array[k] = temp;
}

void buildMaxHead(vector<int>& array, int len) {
    for (int i = (len-1)/2; i >= 0; i--) {
        headAdjust(array, i, len);
    }
}

void headSort(vector<int>& array) {
    buildMaxHead(array, array.size()-1);
    for (int i = array.size()-1; i > 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        headAdjust(array, 0, i-1);
    }
}

7. Merge sort

Basic idea: assuming that the table to be sorted contains n elements, it can be regarded as n ordered sub tables. The length of each sub table is 1, and then merge them in pairs to obtain a new sub table with a length of 2 or 1. Repeat this until it is merged into an ordered table with a length of n.
Time complexity: O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)

void merge(vector<int>& arr, int low, int mid, int high) {
    vector<int> temp(high - low + 1);
    int left = low, right = mid + 1;
    int index = 0;
    while (left <= mid && right <= high) {
        while (left <= mid && arr[left] <= arr[right]) {
            temp[index++] = arr[left++];
        }
        while (right <= high && arr[left] >= arr[right]) {
            temp[index++] = arr[right++];
        }
    }
    while (left <= mid) {
        temp[index++] = arr[left++];
    }
    while (right <= high) {
        temp[index++] = arr[right++];
    }
    for (int i = 0; i < temp.size(); i++) {
        arr[low + i] = temp[i];
    }
}

void mergeSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int mid = (low + high) >> 1;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

8. Cardinality sort

Basic idea: split the elements to be sorted into multiple keywords (when comparing two elements, first compare the first keyword, if the same, then compare the second keyword...), then stably sort the first keyword, then stably sort the second keyword,... Finally, stably sort the nth keyword, This completes the stable sorting of the whole sequence to be sorted.
Time complexity: O ( d ∗ ( n + k ) ) O(d*(n+k)) O(d * (n+k)), D is the number of digits of the maximum value, and K is base

int getMaxBit(vector<int>& arr) {
    int max = arr[0];
    int bit = 0;
    for (int num : arr) {
        max = max > num ? max : num;
    }
    while (max > 0) {
        bit++;
        max /= 10;
    }
    return bit;
}

void radixSort(vector<int>& arr) {
    int max_bit = getMaxBit(arr);
    vector<int> count(10);
    vector<int> temp(arr.size());
    int radix = 1;
    for (int i = 0; i < max_bit; i++) {
        for (int j = 0; j < count.size(); j++) {
            count[j] = 0;
        }
        for (int num : arr) {
            int x = (num/radix)%10;
            count[x]++;
        }
        for (int j = 1; j < count.size(); j++) {
            count[j] = count[j-1] + count[j];
        }
        for (int j = arr.size() - 1; j >= 0; j--) {
            int x = (arr[j]/radix)%10;
            temp[count[x]-1] = arr[j];
            count[x]--;
        }
        for (int j = 0; j < arr.size(); j++) {
            arr[j] = temp[j];
        }
        radix = radix * 10;
    }
}