C++ programming: common sorting algorithms

Bubble sort

Algorithmic ideas:

1. Compare adjacent elements. If the first is larger than the second, swap the two;
2. Do the same work for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end, so that the number of elements at the end should be the maximum;
3. Repeat the above steps for all elements except the last one;
4. Repeat steps 1~3 until the sorting is complete.

void mySort(vector<int>& nums){
    if(nums.size()<2){
        return;
    }
    for(int i = 0; i<nums.size()-1; i++){
        for(int j = 0; j<nums.size()-1-i; j++){
            if(nums[j] > nums[j+1]){ //Ascending (descending with <then)
                swap(nums[j], nums[j+1]);
            }
        }
    }
}

Select Sort

Algorithmic ideas:
Selection-sort is a simple and intuitive sorting algorithm. How it works: first find the smallest (large) element in the unsorted sequence, store it at the beginning of the sorted sequence, then continue to find the smallest (large) element from the remaining unsorted elements, and then place it at the end of the sorted sequence. And so on until all the elements are sorted.

//There are problems below but they haven't been sorted out yet
void mySort(vector<int>& nums){
    if(nums.size()<2){
        return;
    }
    int minNum;//With subscripts here, saving values directly will cause errors
    int tmp;
    for(int i=0; i<nums.size()-1;i++){ //Notice that i doesn't take the last one, because j is behind i
        minNum = i;
        for(int j=i+1; j<nums.size();j++){
            if(nums[j] < nums[minNum]){
                minNum = j;
            }
        }
        swap(nums[minNum], nums[i]);
    }
}

Insert Sort

Algorithmic ideas:
By building an ordered sequence, for unsorted data, scan backwards and forwards in the ordered sequence to find the corresponding location and insert it. The first data is generally considered ordered.

void mySort(vector<int>& nums){
    if(nums.size()<2){
        return;
    }
    int preIndex;//Record the last subscript of an ordered array
    int current;
    for(int i=1; i<nums.size();i++){
        preIndex = i-1;
        current = nums[i];
        while(preIndex>=0 && nums[preIndex]>current){
            nums[preIndex+1] = nums[preIndex];
            preIndex--;
        }
        nums[preIndex+1]=current;
    }
}

Shell Sort

Algorithmic ideas:
The first sorting algorithm that breaks through O(n2) is an improved version of simple insert sorting. It differs from insert ordering in that it takes precedence over elements that are farther away. Hill sort is also known as reduced incremental sort.

//The reason for the time has not yet been understood.
void mySort(vector<int>& nums){
    if(nums.size()<2){
        return;
    }
    for(int gap=nums.size()/2; gap>0; gap=gap/2){
        for(int i=gap; i<nums.size(); i++){
            int j = i;
            int current = nums[i];
            while(j-gap>=0 && current<nums[j-gap]){
                nums[j] = nums[j-gap];
                j = j-gap;
            }
            nums[j] = current;
        }
    }
}

Merge Sort

Algorithmic ideas:
This algorithm is a very typical application of Divide and Conquer, which is second only to fast sorting. Merge the existing ordered subsequences to obtain a completely ordered sequence. That is, each subsequence is ordered before the subsequence segments are ordered. Merging two ordered tables into an ordered table is called a 2-way merge.

//Using tmp to save results
void mySort(vector<int>& nums,int begin,int end,vector<int>& tmp){
    if(begin == end){
        return;
    }
    int mid = (begin+end)/2;
    mySort(nums, begin, mid, tmp);
    mySort(nums, mid+1, end, tmp);
    
    int i = begin;
    int j = mid+1;
    int s = begin;//s points to a temporary result array
    
    // Compare the elements of two ordered decimal arrays and place them in a large array in turn
    while (i <= mid && j <= end) {
        if(nums[i] < nums[j]){
            tmp[s++] = nums[i++];
        }
        else{
            tmp[s++] = nums[j++];
        }
    }
    // The right decimal array is sorted and the left decimal array is left. Place the left decimal array elements at the end of the large array in turn
    while (i <= mid) {
        tmp[s++] = nums[i++];
    }
    // The left decimal array is sorted, and the right decimal array is left. Place the right decimal array elements at the end of the large array in turn
    while (j <= end) {
        tmp[s++] = nums[j++];
    }
}

Quick Sort

//Quick Sort
void func(vector<int>& nums,int begin,int end){
    if(begin < end){
        int tmp = nums[begin];//Select a benchmark, usually the first one
        int i = begin;
        int j = end;//j Points to the rightmost element
        
        while (i < j) {
            //nums[j] needs to be moved if it is less than tmp
            while (i<j && nums[j] >= tmp) {
                j--;
            }
            nums[i] = nums[j];
            //nums[i] needs to be moved if it is larger than tmp
            while (i<j && nums[i] <= tmp) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = tmp;
        func(nums,begin,i-1);
        func(nums,i+1,end);
    }
}

Quick Sort Algorithm Reference

Merge sort algorithm reference

Top 10 Sorting Algorithms Reference