1. 原理#

对于一段无序的数列，若要将其排序，可以以此步骤进行：

• 对于一段的数列，可以先任取一点mid作为判断点。(其中mid一般为数列中点)
• 对于这段数列进行一次遍历，将大于mid的数放于右端，小于mid的数放于左端。
• 然后对于分配过的序列，选取其[l,p],[p+1,r]两个子段继续上述操作，直到长度为1。(其中p为上述左右两端的分界点)

2. 具体实现(代码)#

本代码思路参考自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
}

• 时间复杂度：O(N*logN)

3. 相关题目#

• AcWing 785. 快速排序
• AcWing 786. 第k个数

1. 原理#

对于一段无序的数列，与快速排序相似，若要将其排序，可以以此步骤进行：

• 对于一段的数列，可以先任取一点mid作为分割点。(其中mid一般为数列中点)
• 先选取其[l,mid],[mid+1,r]两个子段继续排序，并假定其已经排序完成。
• 然后对于已经排序过的两段子段，按照排序顺序先放入b数组中，然后再将排序过的数列覆盖原数列。

2. 具体实现(代码)#

本代码思路参考自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
}

• 时间复杂度：O(N*logN)

3. 相关应用#

• 求逆序对

当用归并排序对数组进行排序时，可以发现，当出现a[i]>b[j]时，即出现了逆序对，且对于当前a[j]来说，会出现mid-i+1个逆序对(即a[j]与[i,mid]共mid-i+1个数配对组合成逆序对)。由此我们可以在排序时求出对应数列中存在的逆序对。

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. 相关题目#

• AcWing 787. 归并排序
• AcWing 788. 逆序对的数量

1.1 算法原理#

对于一个单调的队列，我们可以通过其单调的特性，对于要找到的数k可以通过以下方法找到：

先确定寻找的范围l和r当l<r时，先取范围中点mid，将区间[l,r]分为[l,mid]和[mid+1,r]（此时mid=l+r>>1）或[l,mid-1]和[mid,r]（此时mid=l+r+1>>1）然后，在l<r条件下，根据check(mid)函数，对l，r进行更新，直到l>=r

1.2 代码实现#

本代码思路参考自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 相关题目#

• AcWing 789. 数的范围

2.1 算法原理#

对于一个单调的队列，我们可以通过其单调的特性，与整数二分相似，对于要找到的数k可以通过以下方法找到：

先确定寻找的范围l和r当r-l>eps时，先取范围中点mid，mid=(l+r)/2然后，在r-l>eps条件下，根据check(mid)函数，对l，r进行更新，直到r-l<=eps

2.2 代码实现#

本代码思路参考自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 相关题目#

• AcWing 790. 数的三次方根

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

1. 原理#

無秩序な数列を並べ替えるには、以下の手順で進めることができる：

• 一段の数列に対して、まず任意の点をmidとして判定点とする。（このmidは一般に数列の中央の要素である）
• この数列を一度走査し、midより大きい数は右端へ、midより小さい数は左端へ置く。
• その後、分割された列について、[l,p]、[p+1,r] の2つのサブ区間を選び、上記の操作を続け、長さが1になるまで繰り返す。（pは前述の左右の端の境界点）

2. 具体的な実装（コード)#

本コードの考え方は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
}

• 計算量：O(N*logN)

3. 関連問題#

• AcWing 785. クイックソート
• AcWing 786. 第k個の数

1. 原理#

無秩序な数列について、クイックソートと同様、これを並べ替えるには次の手順で進める：

• 一段の数列に対して、まず任意の点をmidとして分割点とする。（このmidは一般に数列の中点である）
• その後、[l,mid]、[mid+1,r] の2つのサブ区間を選択して並べ替えを続け、すでに整列済みと仮定する。
• その後、すでに整列済みの2つの区間を、整列順に先にb配列へ格納し、次に整列済みの数列で元の数列を上書きする。

2. 具体的な実装（コード)#

本コードの考え方は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
}

• 計算量：O(N*logN)

3. 関連アプリケーション#

• 逆順対

マージソートで配列を並べ替える際、a[i]>b[j] が現れた時、それは逆順対が現れたことを意味し、かつ現在のa[j]については、mid - i + 1 個の逆順対が現れる。すなわちa[j]と[i, mid]が合計でmid - i + 1個の数の組み合わせとなって逆順対を成す。これにより、並べ替え時に対応する配列に存在する逆順対を求めることができる。

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. 関連問題#

• AcWing 787. マージソート
• AcWing 788. 逆順対の数

1.1 アルゴリズムの原理#

単調な列について、その単調性を利用して、探している数kを以下の方法で見つけることができる：

まず探索範囲lとrを決定し、l<r の場合、範囲の中点midを取り、区間[l,r]を [l,mid] と [mid+1,r]（このとき mid = l+r>>1）または [l,mid-1] と [mid,r]（このとき mid = l+r+1>>1）に分け、l<r の条件の下で check(mid) 関数に基づき、lとrを更新し、l>=r になるまで続ける。

1.2 コード実装#

本コードの考え方は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 相关题目#

• AcWing 789. 数的范围

2.1 アルゴリズムの原理#

単調な列について、その単調性を活用して、整数の二分探索と同様に、探している数kを見つけることができる：

まず探索範囲lとrを決定し、r-l>eps のとき、範囲の中点midを取り、mid=(l+r)/2、次に r-l>eps の条件の下で check(mid) 関数に基づき、lとrを更新し、r-l<=eps になるまで続ける

2.2 コード実装#

本コードの考え方は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 関連題目#

• AcWing 790. 数の三次方根