快排和归并排序思维的应用

1.调整数组顺序使奇数位于偶数前面：输入一个整数数组，调整数组中的的数字的顺序，使得所有奇数位于数组前半部分，所有偶数位于数组的后半部分。
（1）利用快排的思路：首先在数组首部和尾部设置left和right指针，如果left指针遇到奇数则left++即向后移动；如果right指针遇到偶数则right–即向前移动。
当left遇到偶数，right遇到奇数时，交换两者所指的数。如此不断循环，直到left>right
（2）利用归并排序的思路：首先开辟一个辅助数组help,在辅助数组的首部设置current指针；在原数组首部设置left指针，原数组尾部设置right指针；current指针依次扫描辅助数组，遇到奇数赋给left所指的原数组中，current++，left++;遇到偶数赋给right所指的原数组中，current++，right–；直到current扫描完整个辅助数组为止。

public class 调整数组顺序奇数在左偶数在右 { public static void main(String[] args) { int []a= {3,5,2,4,6,1,9,8}; for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); } Quick(a,0,a.length-1); System.out.println(); System.out.println("-----------------"); for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); } } //快排法 private static void Quick(int[] a, int p, int r) { // TODO Auto-generated method stub int left=p;//左指针 int right=r;//右指针 while(left<=right)//截止条件是交错 { if(a[left]%2==1) { left++; } if(left>right) { break; } if(a[right]%2==0) { right--; } if(left>right) { break; } if(a[left]%2==0&&a[right]%2==1) { int term=a[left]; a[left]=a[right]; a[right]=term; } } } //归并法 private static void Merge(int[] a, int p, int r) { // TODO Auto-generated method stub int []help=new int[a.length]; for(int i=p;i<=r;i++) { help[i]=a[i]; } int current=p;//辅助数组指针 int left=p;//原数组的左指针 int right=r;//原数组右指针 while(current<=r) { if(help[current]%2==1)//如果是奇数 { a[left]=help[current]; current++; left++; } else//如果是偶数  { a[right]=help[current]; current++; right--; } } } } 

2.求第k个元素，以尽量高的效率求出一个乱序数组中按数值顺序的第k个元素值
思路：题目要求输入k值，求第k个数（k从1开始计数）。
直接思路：对这一组数直接排序之后，输出数组下标k-1即可。
因为这里要求高效率求，改进之处是在分区之后，先判断一下k和主元下标的关系，如果小于主元下标，就只对左侧区间进行递归；如果大于主元下标，就对右侧区间进行递归，不用两侧都递归求解，这样就可以提升一点效率。
（为什么k直接与主元下标比较，因为一趟排序之后主元会放到这组数的合适位置即最终下标,与主元下标比较就可以判断要求的第k个数所在哪个区间）

import java.util.*; //此题意思是给了一组无序的数，然后输入一个k,求第k个数（k从1开始计数） public class 最快效率求出乱序数组中的第k小的数 { public static void main(String[] args) { int []a= {5,2,3,8,12,0,6}; Scanner sc=new Scanner(System.in); int k=sc.nextInt();//找第k个数 System.out.println("第"+k+"个数为"+Select(a,0,a.length-1,k)); sc.close(); } private static int Select(int[] a, int p, int r, int k) { // TODO Auto-generated method stub int h=index(a,p,r); int s=h-p+1;//从1开始计数的位置 if(k==s) return a[h]; if(s>k) { return Select(a, p, h-1, k); } else { return Select(a,h+1,r,k-s); } } //单向扫描 private static int index(int[] a, int p, int r) { // TODO Auto-generated method stub int x=a[p];//定主元 int scan=p; int bigger=r; while(scan<=bigger) { if(a[scan]<=x) { scan++; } else { int term=a[scan]; a[scan]=a[bigger]; a[bigger]=term; bigger--; } } //最后交换主元和bigger位置 int term=a[p]; a[p]=a[bigger]; a[bigger]=term; return bigger; } } 

3.给了一组数，求哪个数在数组中出现的次数超过了数组长度的一半？
方法一:利用Arrays.sort内置排序函数，将数组排好序。因为一旦排序之后，出现次数超过一半的元素肯定出现在下标为N/2处。
方法二：Arrays.sort底层也是快速排序，但是并不需要都排好；只要求出下标为N/2即可，这样可以提升一点效率。这时可以利用快速排序分区算法，只求第N/2个数，只对一侧进行递归排序。
方法二：

public class 求数组中出现次数超过半数的元素 { public static void main(String[] args) { int []a= {5,2,2,2,3}; for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); } Select(a,0,a.length-1,a.length/2); System.out.println(); System.out.println("--------------"); System.out.println("出现超过半数的元素为"+a[a.length/2]); } private static int Select(int[] a, int p, int r, int k) { // TODO Auto-generated method stub int h=index(a,p,r); int h2=h+1;//从1开始计数时的顺序 if(k==h2) return a[h]; if(k<h2) { return Select(a, p, h-1, k); } if(k>h2) { return Select(a, h+1, r, k-h2); } return -1; } //双向扫描分区算法 private static int index(int[] a, int p, int r) { // TODO Auto-generated method stub //定主元 int x=a[p]; int begin=p+1;//头指针 int end=r;//尾指针 while(begin<=end) { if(a[begin]<=x) { begin++; } if(begin>end)//交错之后立即终止 { break; } if(a[end]>x) { end--; } if(begin>end)//交错之后立即终止 { break; } if(a[begin]>x&&a[end]<=x) { int term=a[begin]; a[begin]=a[end]; a[end]=term; } } //最后交换主元和end指向的元素 int term =a[p]; a[p]=a[end]; a[end]=term; return end; } } 

方法三：如果题目限定不允许移动数组元素，那么就不能使用排序相关的算法了。解决办法：两两消除法
1.首先确定一个候选值（一般是数组第0个元素），设置变量次数t为1
2.从数组中下标为1的元素开始遍历，当与候选值相同时，次数加一即t++；如果与候选值不同时次数减一即t–；如果此时t已经为0，说明前面都已各自消除掉，然后将此时的值取代候选值，次数t为1
3.当遍历完之后，输出次数的候选值即可

//方法三:不允许移动原有数组，找出元素个数超过一半的元素 public class 发帖水王 { public static void main(String[] args) { int []a= {1,2,3,4}; //因为要找个数超过一半的元素，从数组开头两两消掉其他元素，最后剩下的就是要求的 int x=a[0];//候选值 int t=1;//出现次数 for(int i=1;i<a.length;i++) { if(t==0) { x=a[i];//替换候选值 t=1; continue; } if(a[i]==x) { t++; } else { t--; } } System.out.println("这个元素就是"+x); } } 

本文地址：https://blog.csdn.net/Elon15/article/details/107904851