排序

「排序算法sorting algorithm」用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有
序数据通常能够被更有效地查找、分析和处理。

归并排序

1.确定分界点：mid=（l+r）/2

2.递归排序左边和右边

3.==归并==：合二为一

// === File: merge_sort.java ===
/* 合并左子数组和右子数组*/
void merge(int[] nums, int left, int mid, int right) {
// 左子数组区间[left, mid], 右子数组区间[mid+1, right]
// 创建一个临时数组tmp ，用于存放合并后的结果
int[] tmp = new int[right - left + 1];
// 初始化左子数组和右子数组的起始索引
int i = left, j = mid + 1, k = 0;
// 当左右子数组都还有元素时，比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else
tmp[k++] = nums[j++];
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
// 将临时数组tmp 中的元素复制回原数组nums 的对应区间
for (k = 0; k < tmp.length; k++) {
nums[left + k] = tmp[k];
}
}
/* 归并排序*/
void mergeSort(int[] nums, int left, int right) {
// 终止条件
if (left >= right)
return; // 当子数组长度为1 时终止递归
// 划分阶段
int mid = (left + right) / 2; // 计算中点
mergeSort(nums, left, mid); // 递归左子数组
mergeSort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
merge(nums, left, mid, right);
}

快速排序

// === File: quick_sort.java ===
/* 元素交换*/
void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/* 哨兵划分*/
int partition(int[] nums, int left, int right) {
// 以nums[left] 作为基准数
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[left])
j--; // 从右向左找首个小于基准数的元素
while (i < j && nums[i] <= nums[left])
i++; // 从左向右找首个大于基准数的元素
swap(nums, i, j); // 交换这两个元素
}
swap(nums, i, left); // 将基准数交换至两子数组的分界线
return i; // 返回基准数的索引
}

二分

二分的本质不是单调性，而是找到一种性质划分成2个区间，一个满足性质，一个不满足。

整数二分

    #include<iostream>
    using namespace std;

    const int N=100010;
    int n,m;
    int q[N];
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%d",&q[i]);
        while(m--)
        {
            int x;
            scanf("%d",&x);
            int l=0,r=n-1;
            while(l<r)
             {
                int mid = l+r>>1;
                if (q[mid]>=x)r=mid;
                else l=mid+1;
            }
            if(q[[l]!=x])cout<<"-1 -1"<<endl;
            else
            {
                cout<<1<<' ';
                int l=0,r=n-1;
                while(l<r)
                {
                    int mid = l+r>>1;
                    if(q[mid]<==x)l=mid;
                    else r=mid-1;
                }
                cout<<1<<endl;
            }
        }
        return 0;
    }

浮点二分

#include<iostream>
    using namespace std;

    const int N=1000010;
    int n;
    int q[n];

    int main(){
        double x;
        cin>>x;
        double l=0,r=x;
        while(r-l>1e-8)
        {
            double mid=(l+r)/2;
            if(mid*mid>=x)r=mid;
            else l=mid;
        }
        print("%lf\n",1);
        return 0;
    }

前缀和差分