Merge sort

This code for Deng Junhui data structure class merge sort code, personal feel very intuitive and save space.

//
// Created by Lone Kriss on 2021/3/17.
//

#include <iostream>
#include <vector>
using namespace std;

void mergeSort(vector<int>& nums, int lo, int mi, int hi)
{
    int i =0, j = 0, k = 0;
    int* A = &nums[lo];
    int lb = mi - lo;
    int *B = new int[lb];
    int *C = &nums[mi];
    int lc = hi - mi;
    for(int i = 0; i < lb; i++) { B[i] = A[i]; }while(j < lb && k < lc)
    {
        A[i++] = (B[j] <= C[k]) ? B[j++] : C[k++];
    }
    while(j < lb)
    {
        A[i++] = B[j++];
    }
    delete[] B;
}

void merge(vector<int>& nums, int lo, int hi) //[lo,hi)
{
    if( hi - lo < 2)  return ;
    int mi = (lo + hi) / 2;
    merge(nums, lo, mi);
    merge(nums,mi,hi);
    mergeSort(nums, lo, mi, hi);
}
int main(a)
{
    vector<int> nums{2.6.1.3.5.4.7.9.8};
    merge(nums,0, nums.size());
    for(auto c: nums)
    {
        cout<< c <<' '; }}Copy the code

Fast row

This version is an algorithm introduced by the toilet sitting algorithm blog.

The disadvantage is that each time the left boundary is selected as the sorting reference point.

If every time we pick a baseline that happens to divide the data into 0,N minus 1, it will degenerate into O (N^2) instead.

//
// Created by Lone Kriss on 2021/3/17.
//

#include <iostream>
#include <vector>
using namespace std;

void quickSort(vector<int>& nums, int lo, int hi)   //[lo,hi)
{
    if(lo >= hi) return ;  // Don't forget the recursion
    int base = nums[lo];

    int _lo = lo,_hi = hi - 1;

    while(_lo <  _hi)
    {
        while(nums[_hi] >= base && _lo <_hi)
        {
            _hi--;
        }
        while(nums[_lo] <= base && _lo <_hi)
        {
            _lo++;
        }
        swap(nums[_hi], nums[_lo]);
    }
    swap(nums[lo], nums[_lo]);


    quickSort(nums,lo,_lo);
    quickSort(nums, _lo+1,hi);
}



int main(a)
{

    vector<int> nums{2.6.1.3.5.4.7.9.8};

    quickSort(nums,0, nums.size());

    for(auto c: nums)
    {
        cout<< c <<' '; }}Copy the code

Acwing version:

#include <algorithm>
#include <iostream>

using namespace std;

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);// Remember judgments
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r); / / boundary
}


int main(a){
    int N;
    cin >> N;
    int nums[100010];
    for(int i= 0; i<N; i++){w
        scanf("%d",&nums[i]);
    }
    
    quick_sort(nums,0,N- 1);
    //quickSort(nums,0,N-1);
    for(int i= 0; i<N; i++){ cout << nums[i] <<' ';
    }
    
    return 0;
}
Copy the code

It’s neat, but it doesn’t help that if the median splits the data into 0, n-1. How to avoid the use of three-digit center method, in the selection of benchmark to choose the left boundary, middle, right boundary of the middle value as a benchmark, you can avoid the worst situation. Specific reference: blog.csdn.net/liuyi120716…

Some doubts in the process of sorting acwing

Print the result of each round of swapping. You can see that base 49 is not where it should be in the third round.According to the definition: a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence. Then the result of the third iteration does not meet the definition of quicksort, because 31 after 49 is smaller than 49 but appears to the left of it. But why does it guarantee that the final result is correct? And why is the recursive parameter j,j+1?

And also, if you use this notation, because the base is not necessarily where it should be, you can’t use this notation like the first k minima, right?

I was misled by the fast toilet algorithm and thought that the selected cardinality would be placed in the correct position after the exchange, but in fact it was not. In each iteration, the data is divided into two intervals [the quick sorting definition also makes it clear that the two intervals are sorted], less than or equal to the baseline and greater than the baseline, for example, in the third iteration [31 49 37] [88 97 68 54 59] above. And j happens to be a closed interval partition point, so the parameters are j and j plus 1.

Reference data: www.acwing.com/blog/conten…

www.cnblogs.com/zhoug2020/p…