前馈知识：
所有排序总结与二分查找
1.冒泡排序
冒泡排序是所有排序方法中最简单，最易懂的排序，示意图如下:
public class BubbleSort{
public static void sort(int[] arr){
for(int i=0;i<arr.length-1;i++){
for(int j=arr.length-1;j>i;j--){
if(arr[j]<arr[j-1]){
swap(arr,j-1,j);
}
}
}
public static void swap(arr,i,j){
tmp=arr[j];
arr[j]=arr[i];
arr[i]=tmp;
}
分析：时间复杂度为o(n^2),空间复杂度为o(n).
2.选择排序
选择排序与冒泡排序比较类似，可以认为是选择排序是对于冒泡排序的一种优化。选择排序在确定了最小的数后才进行交换。
public class SelectSort{
public static void sort(int[] arr){ if(arr==null||arr.length==0){ return; } for(int i=0;i<arr.length;i++){ int minIndex=i; for(int j=i+1;j<arr.length;j++){ if(arr[j]<arr[minIndex]){ minIndex=j; } } if(minIndex!=i){ swap(arr,i,minIndex); } } } public static void swap(int[] arr, int i,int j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; }
}
总结：如何更好理解选择排序与冒泡排序？
冒泡排序拆解：
i=0时，冒泡排序是从最后一位开始计算，与前一位进行比较，得出最小值后与i=0所在的值互换；
接下来i=1,继续进行交换。
选择排序拆解：
i=0时，设i=minindex,则向后遍历，找到最小的数之后互换。
i=1时，设i=minIndex,则依旧同上，进行交换。
3.插入排序
插入排序跟扑克牌有相似之处，插入排序要求插入数之前的数必须有序。
确定第一个数，再跟第二个数比较，先后移，在插入。
public class InsertSort { public static void sort(int[] arr){ if(arr==null||arr.length==0){ return; } for(int i=1;i<arr.length;i++){ int j=i; int target=arr[i]; /** * * * 后移操作 */ while(j>0&&target<arr[j-1]){ arr[j]=arr[j-1]; j--; } /** * * * 插入操作 */ arr[j]=target; } } public static void main(String[] args) { } }
4.快速排序（quickSort）
pivot:支点，中心
思想：冒泡+二分+递归分治
上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。
快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。
package sort; public class QuickSort { public static int partition(int[] arr,int left,int right){ int paviotKey=arr[left]; int paviotPointer=left; //交换开始，大的放右边，小的放左边 while(left<right){ while(left<right&&arr[left]<=paviotKey){ left++; } while(left<right&&arr[right]>=paviotKey){ right++; } swap(arr,left,right); } swap(arr,paviotPointer,left); return left; } //现在left所在的索引是标准数所在的索引 public static void quickSort(int[] arr,int left,int right){ if(left>=right){ return; } int paviotPos=partition(arr,left,right); quickSort(arr,0,paviotPos-1); quickSort(arr,paviotPos+1,right); } public static void sort(int[] arr,int left,int right){ if(arr==null||arr.length==0){ return; } quickSort(arr,0,arr.length-1); } public static void swap(int[] arr,int left,int right){ int tmp=arr[left]; arr[left]=arr[right]; arr[right]=tmp; } }
堆排序的原理：
升序排序，造个大顶堆，将顶元素与尾元素兑换，在构造大顶堆。
public class HeapSort { public static void heapSort(int[] arr){ if(arr==null||arr.length==0){ return; } int len=arr.length; buildMaxHeap(arr,len); //开始重置堆 for(int i=len-1;i>0;i--){ swap(arr,0,i); len--; heapify(arr,0,len); } } private static void buildMaxHeap(int[] arr,int len){ //从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆 //注意：最后一个非叶节点的索引值为Math.floor(len/2)-1 for(int i = (int) (Math.floor(len/2)-1); i>=0; i--){ heapify(arr,i,len); } } private static void heapify(int[] arr,int i,int len){ int left=2*i+1; int right=2*i+2; int largestIndex=i; if(left<len&&arr[left]>arr[largestIndex]){ largestIndex=left; } if(right<len&&arr[right]>arr[largestIndex]){ largestIndex=right; } if (largestIndex!=i){ swap(arr,i,largestIndex); heapify(arr,largestIndex,len); } } public static void swap(int[] arr, int i,int j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } }
堆排序的核心：建好大顶堆后最后一个子节点与根节点互换，重新组成新的大顶堆。
因为堆排序无关乎初始序列是否已经排序已经排序的状态，始终有两部分过程，构建初始的大顶堆的过程时间复杂度为O(n)，交换及重建大顶堆的过程中，需要交换n-1次，重建大顶堆的过程根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以它最好和最坏的情况时间复杂度都是O(nlogn)，空间复杂度O(1)。
##希尔排序：
将序列分割成几个若干序列进行插入排序，再将序列合并再进行一次插入排序。
希尔排序：按照/2来分配增量，接下来继续分小组进行插入排序。时间复杂度为O(n^1.3)
归并排序：递归划分子问题，然后合并解决问题。
public class MergeSort { public static void mergeSort(int[] arr){ mSort(arr,0,arr.length-1); } /** * * * 递归分治 */ public static void mSort(int[] arr,int left,int right){ if(left>=right){ return; } int mid=(left+right)/2; mSort(arr,0,mid); mSort(arr,mid+1,right); merge(arr,left,mid,right); } public static void merge(int[] arr,int left,int mid,int right){ int[] tmp=new int[right-left+1]; int i=left; int j=mid+1; int k=0; while(i<=mid&&j<=right){ if(arr[i]<=arr[j]){ tmp[k++]=arr[i++]; }else{ tmp[k++]=arr[j++]; } } for(int p=0;p<arr.length;p++){ arr[left+p]=tmp[p]; } } }
##计数排序:最特殊的排序，时间复杂度可以认为是线性的，即O(n).
如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是O(nlogn)。但是确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
计数排序经典例题：数组里有20个随机数，取值范围为从0到10，要求用最快的速度把这20个整数从小到大进行排序。
思路：以取值范围为下标，统计数字，然后遍历数组。
public class CountSort { public static void countSort(int[] arr){ if(arr==null||arr.length==0){ return; } int max=max(arr); int[] count=new int[max+1]; Arrays.fill(count,0); for(int i=0;i<=max;i++){ count[arr[i]]++; } int k=0; for(int i=0;i<=max;i++){ for(int j=0;j<count[i];j++){ arr[k++]=i; } } } public static int max(int[] arr){ int max=Integer.MIN_VALUE; for (int ele:arr) { if(ele>max){ max=ele; } } return max; } }
##桶排序：
public class BucketSort { /** * * * 桶排序 */ public static void bucketSort(int[] arr){ if(arr==null&&arr.length==0){ return; } int bucketNums=10;//默认桶的数量为10 List<List<Integer>> buckets = new ArrayList<>(); for(int i=0;i<10;i++){ buckets.add(new LinkedList<Integer>()); } //划分桶 for(int i=0;i<arr.length;i++){ buckets.get(f(arr[i])).add(arr[i]);//arr[i]/10对应相应的那个桶 } //对桶进行排序 for(int i=0;i<buckets.size();i++){ if(!buckets.get(i).isEmpty()){ Collections.sort(buckets.get(i)); } } //还原排好序的数组 int k=0; for (List<Integer> bucket : buckets) { for (Integer ele : bucket) { arr[k++]=ele; } } /** * * * 映射函数 */ } public static int f(int x){ return x/10; } }
基数排序：也是一种较为复杂的排序。限定条件，限定映射条件的重要度。比如设定区分度。
public class RadixSort { public static void radixSort(int[] arr){ if(arr==null||arr.length==0){ return; } int maxBit = getMaxBit(arr); for(int i=1;i<maxBit;i++){ List<List<Integer>> buf=distribute(arr,i);//分配 collecte(arr,buf);//收集 } } public static List<List<Integer>> distribute(int[] arr,int iBit){ List<List<Integer>> buf = new ArrayList<List<Integer>>(); for(int j=0;j<10;j++){ buf.add(new LinkedList<Integer>()); } for(int i=0;i<arr.length;i++){ buf.get(getNBit(arr[i],iBit)).add(arr[i]); } return buf; } public static void collecte(int[] arr,List<List<Integer>> buf){ int k=0; for (List<Integer> bucket : buf) { for (Integer ele : bucket) { arr[k++]=ele; } } } public static int getMaxBit(int[] arr){ int max = Integer.MIN_VALUE; for (int ele : arr) { int len=(ele+"").length(); if(len>max){ max=len; } } return max; } /** * * * * 获取x的第n位，如果没有则为0 */ public static int getNBit(int x,int n){ String sx=x+""; if(sx.length()<n){ return 0; }else{ return sx.charAt(sx.length()-n)-'0'; } } }
· 
##好了，接下来我们看看题目：
##备注：Integer.MIN_VALUE:极小值，几乎用不到。
Integer.MAX_VALUE：极大值，同样几乎用不到。
public class Solution4 { public double findMedianSortedArrays(int[] nums1,int[] nums2){ if(nums1.length>nums2.length){ int[] tmp=nums1; nums1=nums2; nums2=tmp; } /** * * * * 为了便于比较，我们选择互换 */ int m=nums1.length; int n=nums2.length; //分割线左边要求的元素数量为m+n+1/2 int totalLeft=(m+n+1)/2; //在nums1的区间内寻找恰当的分割线。 //使得nums1[i-1]<=nums2[j]&&nums2[j-1]<=nums1[i] int left=0; int right=m; while(left<right){ int i=left+(right-left+1)/2;//原因：如果不加一，则会无限循环，理由如下： /**if right=i-1;-->right=right/2-1; * if left=i;-->i=(3/4)*right-->永远小于right造成死循环 * * * * * * */ int j=totalLeft-i; if(nums1[i-1]>=nums2[j]){ right=i-1; }else{ left=i; } } int i=left;//第一个数组的边界，即分割线的右边第一个数的索引值，对应了前面的数数量 int j=totalLeft-i;//第二个数组的边界 int nums1LeftMax=i==0?Integer.MIN_VALUE:nums1[i-1]; int nums1RightMin=i==m?Integer.MAX_VALUE:nums1[i]; int nums2LeftMax=j==0?Integer.MIN_VALUE:nums2[j-1]; int nums2RightMin=j==n?Integer.MAX_VALUE:nums2[j]; if(((m+n)%2)==1){ return Math.max(nums1LeftMax,nums2LeftMax); }else { return (double)((Math.max(nums1LeftMax,nums2LeftMax)+Math.min(nums1RightMin,nums2RightMin))/2); } } /** * * 这种方法思路总结：因为两个数组是有序数组，则按照总数划分后，第二个索引大的数组大致划分完毕， * 则需要配置第一行数组， * 使得第一行的数组划分后的左边小于 * 右边的任意一个数。继续二分查找，然而考虑到一些特殊情况，比如分割线在数组尽头的情况， * 这种也是可以在包含范围之内的。 * * 时间复杂度O（log(min)(m,n)）,空间复杂度O（1） */