算法练习day4——190321（小和、逆序对、划分、荷兰国旗问题）
归并排序快的原因：
后面的排序利用了前面排序的结果！！！
1.小和问题
在一个数组中， 每一个数左边比当前数小的数累加起来， 叫做这个数组的小和。 求一个数组的小和。
- 例子：[1,3,4,2,5]
- 1左边比1小的数， 没有；
- 3左边比3小的数， 1；
- 4左边比4小的数， 1、 3；
- 2左边比2小的数， 1；
- 5左边比5小的数， 1、 3、 4、 2；
- 所以小和为1+1+3+1+1+3+4+2=16
使用归并排序解决。
大概思路：
先分：
合的时候，比较，确定需要合并的另一部分中比目前这组中的的每个数大的有几个：
5和4，合的时候，两个指针p1，p2，分别指向5和4。
arr[p1]>arr[p2]，不用算小和，因为大的在左边。
所以直接合并。
接下来，合并1、4和5：
arr[p1]
res=(R-p2+1)*arr[p1]=(1-0+1)*1=2; //R是数组中最后一位元素的下标
小和计算完毕，合并：
5和2的合并时：
arr[p1]>arr[p2]，不用算小和，直接合并：
8、5和2合并时：
arr[p1]>arr[p2]，不用算小和，直接合并：
合并1和4和5、2和5和8时：
arr[p1]
res=arr[p1]*(R-P2+1)=1*(2-0+1)=3;
arr[p1]放入result数组（和归并排序一样）；
p1右移：
arr[p1]>arr[p2]，不计算小和，arr[p2]放入result数组；
p2右移：
arr[p1]
res=arr[p1]*(R-p2+1)=4*(2-1+1)=8;
arr[p1]放入result数组；
p1右移：
arr[p1]=arr[p2]，不计算小和，将arr[p2]放入result数组；
p2右移：
arr[p1]
res=arr[p1]*(R-p2+1)=5*(2-2+1)=5;
将arr[p1]放入result数组；
p1右移，左半数组完，将右半数组剩余元素放入result数组。
最终res=2+3+8+5=18；
result={1,2,4,5,5,8};
代码实现：
package Solution;public class SmallSum {public static void main(String[] args) {int[] array= {1,5,4,8,5,2};int value=mergeSort(array);System.out.print(value);}public static int mergeSort(int[] arr) {if(arr==null||arr.length<2)return 0;return sortProcess(arr,0,arr.length-1);//此处注意串的是下标}public static int sortProcess(int[] arr,int L,int R) {if(L==R)return 0;int mid= L + ((R - L) >> 1);/** mid=(L+R)/2不安全，因为R+L可能会溢出，然后除以2结果可能会不准确* mid=L+(R-L)/2是安全的；* a/2=a>>1(一个数除以2，等于它右移一位)* 所以mid=L+(R-L)>>1;* 用右移的原因：位运算比算术运算快很多*/return sortProcess(arr,L,mid)+sortProcess(arr,mid+1,R)+merge(arr,L,mid,R);}public static int merge(int[] arr,int L,int mid,int R) {//注意此处的R是末尾元素的位置，不是长度int[] result=new int[R-L+1];//所以此处求长度应+1int p1=L;int p2=mid+1;int i=0;int value=0;while(p1<=mid&&p2<=R) {//所以此处比较应该包含mid和R，就是≤，而不是＜value+=arr[p1]运行结果：
2.逆序对问题
在一个数组中， 左边的数如果比右边的数大， 则折两个数构成一个逆序对， 请打印所有逆序对。
和计算小和差不多，这个是找要合并的另一半中，比自己小的元素，组成逆序对，打印。
具体：
arr[p1]>arr[p2]时，打印(arr[p1~mid],arr[p2])。
代码实现：
package Solution;public class ReSequen{public static void main(String[] args) {int[] array= {1,5,4,8,3,2};mergeSort(array);for(int i=0;i> 1);/** mid=(L+R)/2不安全，因为R+L可能会溢出，然后除以2结果可能会不准确* mid=L+(R-L)/2是安全的；* a/2=a>>1(一个数除以2，等于它右移一位)* 所以mid=L+(R-L)>>1;* 用右移的原因：位运算比算术运算快很多*/sortProcess(arr,L,mid);sortProcess(arr,mid+1,R);merge(arr,L,mid,R);}public static void merge(int[] arr,int L,int mid,int R) {//注意此处的R是末尾元素的位置，不是长度int[] result=new int[R-L+1];//所以此处求长度应+1int p1=L;int p2=mid+1;int i=0;while(p1<=mid&&p2<=R) {//所以此处比较应该包含mid和R，就是≤，而不是＜if(arr[p1]>arr[p2])for(int k=p1;k<=mid;k++)System.out.println("("+arr[k]+","+arr[p2]+")");result[i++]=arr[p1] 运行结果：
2.给定一个数组arr， 和一个数num， 请把小于等于num的数放在数组的左边， 大于num的数放在数组的右边。
要求额外空间复杂度O(1)， 时间复杂度O(N)。
分析：只说大于的在右边，没要求有序。
方法：
- 设置一个指针X，开始位置位于数组第一个元素位置的前一个；
- 然后从数组第一个元素开始，和num进行比较；
- 大于，继续比较后一个；
- 小于等于，X右移（扩大“小于等于域”）——将这个数和小于等于域的下一个数交换，X+1（扩大X域）——X左边都是小于等于num的，右边是大于num的；
代码实现：
package Solution;public class partSort {public static void main(String[] args) {int[] array= {1,5,4,8,3,2};partsort(array,5);for(int i=0;i运算结果：
3.荷兰国旗问题
给定一个数组arr， 和一个数num， 请把小于num的数放在数组的左边， 等于num的数放在数组的中间， 大于num的数放在数组的右边。
方法1：
- 设置一个指针less，开始位置位于数组第一个元素位置的前一个；
- 设置一个指针more，开始位置位于数组最后一个元素位置的后前一个；
- 然后从数组第一个元素开始，和num进行比较；
- 等于，向后移动；
- 大于，和最后一个位置的元素交换（扩大“more区域”），more前移；
- 小于，和第一个位置的元素交换（扩大“less区域”），less后移；
代码实现：
package Solution;public class HeLan {public static void main(String[] args) {int[] array= {1,5,4,8,3,5,9,5,6,2};helansort(array,5);for(int i=0;i运行结果：
方法2：
- 设置一个指针less，开始位置位于数组第一个元素位置的前一个；
- 设置一个指针more，开始位置位于数组最后一个元素位置的后前一个；
- 然后从数组第一个元素开始，和num进行比较；
- 等于，向后移动；
- 大于，和最后一个位置的元素交换（扩大“more区域”），more前移，i（指向当前元素的指针）指针不动；
- 小于，和第一个位置的元素交换（扩大“less区域”），less后移，i后移一位（因为确定交换过来的元素肯定等于num）；
代码实现：
package Solution;public class HeLan {public static void main(String[] args) {int[] array= {1,5,4,8,3,5,9,5,6,2};int[] result=helansort(array,5,0,array.length-1);for(int i=0;i运行结果：
分析：
若有于区域不存在，会不会出现问题？
不会的。
- 若小于区域不存在，则等于区域开始位置为数组首元素的位置；
- 若大于区域不存在，则等于区域结束位置为数组末元素的位置；
- 若等于区域不存在，则它的开始位置等于结束位置（less+1=more-1）;
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！