归并排序——分治
共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<stdio.h> 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<stdio.h> 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<stdio.h> 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<r) { 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<r) { 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，之后打印就行
