1. Principle#

For a segment of an unordered sequence, if you want to sort it, you can proceed as follows:

• For a segment of numbers, you can first pick an arbitrary point mid as the pivot. (Where mid is generally the middle of the sequence)
• Perform a single pass on this segment, placing numbers greater than mid to the right, and numbers less than mid to the left.
• Then for the partitioned subsequences, select its [l,p] and [p+1,r] two subsegments to continue the above operation, until the length is 1. (Where p is the boundary between the left and right ends)

2. Implementation (Code)#

This code idea is adapted from Mr. Y

1
void quick_sort(int a[],int l,int r){
2
  if(l>=r) return;//设置退出条件
3
  int i=l-1,j+1,mid = a[l+r>>1];//设置判断点
4
  while(i<j){
5
    do i++;while(a[i]<mid);
6
    do j--;while(a[j]>mid);
7
    if(i<j) swap(a[i],a[j]);
8
  }
9
  quick_sort(a,l,j);//继续对子段排序
10
  quick_sort(a,j+1,r);
11
}

• Time complexity: O(N*logN)

3. Related Problems#

• AcWing 785. Quick Sort
• AcWing 786. The k-th Number

1. Principle#

For an unordered sequence, similar to Quick Sort, if you want to sort it, you can proceed as follows:

• For a segment of numbers, you can first select a point mid as the split point. (Where mid is generally the middle of the sequence)
• First take its [l,mid] and [mid+1,r] two subsegments for sorting, and assume they are already sorted.
• Then for the two already sorted subsegments, place them into array b in sorted order, and then overwrite the original sequence with the sorted numbers.

2. Implementation (Code)#

This code idea is adapted from Mr. Y

1
void merge_sort(int a[],int b[],int l,int r){
2
  if(l>=r) return;//设置退出条件
3
  int mid = l+r>>1,i=l,j=mid+1,k=0;//设置分割点
4
    merge_sort(a,b,l,mid);merge_sort(a,b,mid+1,r);//先对子段排序
5
  while(i<=mid&&j<=r)
6
        if(a[i]<=a[j]) b[k++] = a[i++];
7
      else b[k++] = a[j++];
8
    while(i<=mid) b[k++]=a[i++];
9
    while(j<=r) b[k++]=a[j++];
10
    for(i=l,j=0;i<=r;i++,j++) a[i]=b[j];
11
}

• Time complexity: O(N*logN)

3. Related Applications#

• Inversions

When sorting an array with merge sort, you can observe that when a[i] > a[j] occurs, an inversion is formed, and for the current a[j], there will be mid-i+1 inversions (i.e., a[j] paired with the numbers in [i,mid] form mid-i+1 inversions). Therefore, during sorting, we can compute the number of inversions present in the sequence.

1
long long merge_sort(int a[],int b[],int l,int r){
2
    if(l>=r) return 0;
3
    int mid = l+r>>1,i=l,j=mid+1,k=0;
4
    long long ans = merge_sort(a,b,l,mid)+merge_sort(a,b,mid+1,r);
5
    while(i<=mid&&j<=r)
6
        if(a[i]<=a[j]) b[k++] = a[i++];
7
        else ans += mid-i+1,b[k++]=a[j++];
8
    while(i<=mid) b[k++] = a[i++];
9
    while(j<=r) b[k++] = a[j++];
10
    for(i=l,j=0;i<=r;i++,j++) a[i]=b[j];
11
    return ans;
12
}

4. Related Problems#

• AcWing 787. Merge Sort
• AcWing 788. Number of Inversions

1.1 Algorithm Principle#

For a monotonic sequence, by exploiting its monotonic property, to find the desired number k, you can proceed as follows:

First determine the search range l and r. When l < r, take the midpoint mid, split the interval [l,r] into [l,mid] and [mid+1,r] (here mid = l+r>>1) or [l,mid-1] and [mid,r] (here mid = l+r+1>>1). Then, under the condition l<r, based on the check(mid) function, update l and r until l >= r

1.2 Code Implementation#

This code idea is adapted from Mr. Y

1
//将区间[l,r]分为[l,mid]和[mid+1,r]
2
int bsearch_1(int l,int r){
3
  while(l<r){
4
    int mid = l+r>>1;
5
    if(check(mid)) r=mid;
6
    else l=mid+1;
7
  }return l;
8
}
9
//将区间[l,r]分为[l,mid-1]和[mid,r]
10
int bsearch_2(int l,int r){
11
  while(l<r){
12
    int mid = l+r+1>>1;
13
    if(check(mid)) l=mid;
14
    else r=mid-1
15
  }
16
}

1.3 Related Problems#

• AcWing 789. Range of Numbers

2.1 Algorithm Principle#

For a monotonic sequence, using its monotonic property, similar to integer binary search, to find the desired number k:

First determine the search range l and r. When r-l > eps, take the midpoint mid, mid = (l+r)/2, then, under the condition r-l > eps, based on the check(mid) function, update l and r until r-l <= eps

2.2 Code Implementation#

This code idea is adapted from Mr. Y

1
double bsearch(double l,double r){
2
  while(r-l>eps){
3
    double mid = (l+r)/2;
4
    if(check(mid)) r=mid;
5
    else l=mid;
6
  }return l;
7
}

2.3 Related Problems#

• AcWing 790. Cube Root of a Number