目录

归并排序——分治

 练习题1 逆序对的数量

练习题2 合并俩个有序数组

 快速排序——分治

 二分——整数二分

浮点数二分 

---

归并排序——分治

 

共logn层，每层是O(n)

时间复杂度O(nlogn)

1.确定分界点，将数组按最中间的位置分开（下标的中间值）

2.递归排序左边和右边

3.左边和右边合二为一

俩个有序数组，用指针移动的方法进行比较，min1指针此时所指的数

这种情况当min1指针走到数组末尾时，把min2指针所指的数及其余的数全部放到数组P

 

参考代码：

void merge_sort(int* arr, int l, int r)
{
	if (l >= r)
		return;
	int mid = (l + r) / 2;
	merge_sort(arr, l, mid );
	merge_sort(arr, mid+1, r);
	int tmp[100];
	int i = l;
	int j = mid + 1;
	int k = 0;
	while (i <= mid&&j<=r)
	{
		if (arr[i] < arr[j])
			tmp[k++] = arr[i++];
		else
			tmp[k++] = arr[j++];
	}
	while (i <= mid)
		tmp[k++] = arr[i++];
	while (j <= r)
		tmp[k++] = arr[j++];
 
	for (i = l,j=0; i <=r; i++,j++)
	{
		arr[i] = tmp[j];
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	int arr[100];
	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	merge_sort(arr, 0, n-1);
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

 练习题1 逆序对的数量

给定一个长度为 nn 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 ii 个和第 jj 个元素，如果满足 ia[j]a[i]>a[j]，则其为一个逆序对；否则不是。

输入：6
            2 3 4 5 6 1

输出：5

主要思想：

先给俩边按从小到大顺序排序，当指针l所指元素大于指针j时，由于数组左右半边数组都是有序的说明l前面的元素都小于j所指元素，而l到mid，[l,mid]内的元素都大于j,因此逆序对数为：ret=mid-l+1。

#include
static long long ret = 0;
long long merga_sore(int* arr, int l, int r)
{
    if (l >= r)
        return 0;
    int mid = (l + r) / 2;
 
    merga_sore(arr, l, mid); merga_sore(arr, mid + 1, r);
    int i = l;
    int tmp[100000];
    int k = 0;
    int j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
        {
            tmp[k++] = arr[j++];
            ret += (mid - i + 1);
        }
    }
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];
    for (i = l, j = 0; i <= r; i++, j++)
    {
        arr[i] = tmp[j];
    }
    return ret;
}
int main()
{
    int arr[100000];
    int n;
    int i;
    scanf("%d", &n);
    for (i = 0; i < n; i++) scanf("%d", &arr[i]);
    long long c = merga_sore(arr, 0, n - 1);
    printf("%lld", c);
    return 0;
}

 这里采用C代码解题

练习题2 合并俩个有序数组

点这里跳转

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
 int i=m-1;
 int j=n-1;
 int k=m+n-1;
 while(i>=0&&j>=0)
 {
     if(nums1[i]>nums2[j])
         nums1[k--]=nums1[i--];
      
     else
          nums1[k--]=nums2[j--];
 }
 while(i>=0)
  nums1[k--]=nums1[i--];
  while(j>=0)
   nums1[k--]=nums2[j--];
   return (m+n-1);
}

 比较end1和end2所指的元素，将较大元素放入k所指地址中，较小元素站在原地不动，等一个数组遍历结束后，另一个数组就是较小值，较小值放前面就行

 快速排序——分治

 

1.确定分界点，q[left],q[right],q[(left+right)/2],随机值

2.调整区间，小于等于X的在X左边，大于等于X的在X右边

3.递归处理左右俩边，对左右俩边各进行排序

如何进行第二步？

方法1（暴力法）：创建俩个数组a[]和b[]，把<=x的元素放到a，>=x的元素放到b，然后把a数组放到q中，b也放到q中

方法2（双指针）：使用俩个指针，分别从左端点和右端点开始遍历数组，当左端点遇到>=x的元素时，左指针不再进行移动，此时左指针指向>=x的元素，然后等右端点遇到<=x的元素时，此时将这俩个元素进行交换，交换完之后俩指针继续往中间移动，同样的右端点若先遇到<=x的元素，则右端点停止遍历，在原地等左端点即可

用3作为分界点，此时left=3则left指针停止前进，right满足>3，right向中间靠拢

right此时不再满足>3，right停止前进，此时交换right和left所指向的俩个元素，交换完之后，各自向中间靠拢

left所指元素满足<3，right所指元素不满足>3，right停止前进，left继续遍历

left已经>right了，此时就不能交换俩个数，我们这个时候可以发现 <=3的在左边，>=3的在右边

#include
void quick_qsort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int i = left-1;
	int j = right+1;
	int x = arr[left];
	while (i < j)
	{
		do
		{
			i++;
		} while (arr[i] < x);
		do
		{
			j--;
		} while (arr[j] > x);
		if (i < j)
		{
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
	}
    		quick_qsort(arr, 0, j);
		quick_qsort(arr, j+1, right);
}
int main()
{
	int arr[50];
	int n;
	scanf("%d", &n);
	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	quick_qsort(arr, 0, n - 1);
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

注：当quick_qsort(arr, 0, j);函数里面为j时，x不能为arr[right],函数里面为i时，x不能为arr[left]，这是边界问题，不然会陷入死循环

当x=arr[left],qsort函数传参为i时，若给1，2排序，让x=1，i=left-1=-1，j=2-1+1=2； 之后i++,i=0,arr[0]=1,不满足x，然后j--，俩个都指向了1，j和i此时都是0，后面还有quick_qsort(arr, left, i-1);quick_qsort(arr, i, right);这俩个语句都是[0,1]，会陷入死循环，当x=arr[right],qsort函数传参为j时，也会陷入死循环

时间复杂度nlog（n），共logn层，每层是O(n)

 二分——整数二分

整数二分：如果有单调性可以二分，部分没单调性的也可以二分

本质：一个数组在绿色部分满足某种性质，在红色部分不满足，我们可以通过二分找到红色和绿色的边界点

这里以红色为例

1.找一个中间值mid=(l+r+1)/2

2.判断这个中间值是否满足性质，看mid是否满足红色性质，若满足红色部分的性质，则mid在红色区域内，答案可能在[mid,r]中，因此让l=mid，

当mid不满足红色性质，mid在绿色区域内，答案在[l,mid-1]，之后让r=mid-1

以绿色为例

观察上式，l=mid，需要补1，r=mid不需要补1

#include
int main()
{
    int n;
    int m;
    scanf("%d%d", &n, &m);
    int i = 0;
    int arr[100000];
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    int k = 0;
​
    while (m--)
    {
        scanf("%d", &k);
        int l=0;
        int r=n-1;
        while(l
        {
            int mid=(l+r)/2;
            if(arr[mid]>=k)
            r=mid;
            else
            l=mid+1;
        }
        if(arr[l]!=k)
        printf("-1 -1");
        else
        {
            printf("%d ",l);
            int l=0;
            int r=n-1;
            while(l
            {
                int mid=(l+r+1)/2;
                if(arr[mid]<=k)
                l=mid;
                else
                r=mid-1;
            }
            printf("%d ",l);
        }
        printf("\n");
    }
    return 0;
}

总结：从前面往后面判断k的位置，if(arr[mid]>=k),先判断k在不在前面，若不在前面，则往后找，找出来之后再对第二个k进行查找，if(arr[mid]<=k)，此时从k在不在后面判断，若不在后面则往前找，这样查找会避免重复查找

浮点数二分 

浮点数二分不需要严格的处理边界，保证答案落在区间内

当区间长度很小的时候，就可以当作答案，相当于估读

1.先求一个浮点数的平方根

2.每次找中间点（在0-x）

3.如果mid*mid>=x，则说明，mid在根号x和x区间内，让r=mid，否则l=mid，之后打印就行