一)颜色划分:
算法原理:
使用三指针算法解决此问题:
index索引是用来遍历整个数组的
left索引:标记0区域的最右侧
right索引:标记2区域的最左侧
[0，left]全部都是0
[left+1，index-1]全部都是1
[index，right-1]全部都是待扫描的元素
[right，n)全部是等于2的元素
class Solution { public void swap(int i,int j,int[] array){ int temp=array[i]; array[i]=array[j]; array[j]=temp; } public void sortColors(int[] array) { int left=-1; int right=array.length; int index=0; while(index<right){//注意此时index应该小于right if(array[index]==1){ index++; }else if(array[index]==2){ right--; swap(index,right,array); }else if(array[index]==0){ left++; swap(left,index,array); index++; } } } }二)快速排序:
1)之前学习过的快排是将整个数组分成两部分，左边的区域全部是小于等于基准元素的，右边的区域全部是大于基准元素的，但是假设数组已经处于完全有序的情况下，那么基准元素会被分配到最右边，接下来再次将基准值的右边进行排序，此时时间复杂度就达到了O(N^2)
使用数组分三块的思想实现快排，此时我们还是使用上面的颜色划分的思想来进行实现快排
class Solution { public static void swap(int[] array,int i,int j){ int temp=array[i]; array[i]=array[j]; array[j]=temp; } public static int[] Sort(int left,int right,int[] array) { int temp=array[left]; int leftindex=left-1; int rightindex=right+1; int index=left; while(index<rightindex){ if(array[index]==temp){ index++; }else if(array[index]>temp){ rightindex--; swap(array,rightindex,index); }else{ leftindex++; swap(array,leftindex,index); index++; } } return new int[]{leftindex,rightindex}; } public static void QuickSort(int left,int right,int[] array){ if(right<=left){ return; } int[] temp=Sort(left,right,array); int leftIndex=temp[0]; int rightIndex=temp[1]; QuickSort(left,leftIndex,array); QuickSort(rightIndex,right,array); } public static void main(String[] args) { int[] array={10,8,19,100,8,102}; QuickSort(0,array.length-1,array); System.out.println(Arrays.toString(array)); } }2) 为什么说这个算法效率更快呢？
假设现在数组中的元素都是重复的元素，将数组划分成三段数组就直接排完序了，要是采用划分成两端的方式，时间复杂度就是O(N^2)
3)用随机的方式选取基准元素:
三)数组中第K大的元素
215. 数组中的第K个最大元素 - 力扣（LeetCode）
一)堆排序:使用优先级队列(集合类容器)进行堆排序
class Solution { public int findKthLargest(int[] nums, int k) { //创建一个大小是k的小堆 PriorityBlockingQueue<Integer> queue=new PriorityBlockingQueue<>(k, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1-o2; } }); for(int i=0;i<nums.length;i++){ if(queue.size()<k){ queue.add(nums[i]); }else{ int top=queue.peek(); if(nums[i]>top){ queue.poll(); queue.add(nums[i]); } } } return queue.poll(); } }二)手动创建一个大堆，进行弹出堆顶元素N-1次即可
class Solution { public int poll(int[] array,int len){ int result=array[0]; int temp=array[0]; array[0]=array[len-1]; array[len-1]=temp; len--; createBigHeat(array,0,len); return result; } public void createBigHeat(int[] array,int parent,int len){ int child=2*parent+1; while(child<len){ if(child+1<len&&array[child]<array[child+1]){ child++;//让child下标指向左右孩子的最大值 } if(array[child]>array[parent]){ int temp=array[child]; array[child]=array[parent]; array[parent]=temp; parent=child; child=2*parent+1; }else{ break; } } } public int findKthLargest(int[] array, int k) { //1.首先建立一个大堆 int len=array.length; for(int i=(array.length-1-1)/2;i>=0;i--){ createBigHeat(array,i,len); } //2.建立完大堆之后,出数组中的元素 int data=0; for(int i=0;i<k;i++){ data=poll(array,len); len--; } return data; } }三)使用快速选择算法来解决此问题(O(N))
先进行选取一个基准元素key，然后按照基准元素key将数组划分成三部分
那么我们如何来进行确定第k大的元素是落在左边区域还是右边区域还是在中间的区域呢？
class Solution { //1.这个函数是交换两个位置的元素 public void swap(int[] array,int i,int j){ int temp=array[i]; array[i]=array[j]; array[j]=temp; } //2.先经历一次快排划分区间 public int[] SortAndFind(int[] array,int left,int right){ //1.先进行选取随机的一个元素 Random random=new Random(); int randomIndex=random.nextInt(right-left+1); int resultIndex=randomIndex+left; int temp=array[resultIndex];//基准元素选取完成 //2.根据基准元素使数组分三块 int index=left; int leftIndex=left-1; int rightIndex=right+1; while(index<rightIndex){ if(array[index]==temp){ index++; }else if(array[index]<temp){ leftIndex++; swap(array,leftIndex,index); index++; }else{ rightIndex--; swap(array,rightIndex,index); } } //3.返回划分三块的三个指针 return new int[]{leftIndex,rightIndex}; } public int QuickSort(int[] array,int left,int right,int k){ if(left>=right) return array[left]; int[] result=SortAndFind(array,left,right); int a=result[0]-left+1; int b=result[1]-result[0]-1; int c=right-result[1]+1; //1.先求出数组划分三块的各个元素的个数,小于temp的元素有几个,等于temp的元素有几个,大于temp的元素有几个,进行分类讨论 if(c>=k)//处于大于temp的区间 return QuickSort(array,result[1],right,k); else if(c+b>=k) return array[result[1]-1];//处于等于temp的区间 return QuickSort(array,left,result[0],k-b-c);//处于小于temp的区间 } public int findKthLargest(int[] nums, int k) { return QuickSort(nums,0,nums.length-1,k); } }
四)数组中最小的k个数
剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）
不讲武得:直接排序，找到前k个数
一)集合类容器+优先级队列
class Solution { public int[] getLeastNumbers(int[] array, int k) { int[] result=new int[k]; if(k==0) return result; PriorityBlockingQueue<Integer> queue=new PriorityBlockingQueue<>(k, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2-o1; } }); for(int i=0;i<array.length;i++){ if(queue.size()<k){ queue.add(array[i]); }else{ int data=queue.peek(); if(data>array[i]){ queue.poll(); queue.add(array[i]); } } } for(int i=0;i<k;i++){ result[i]=queue.poll(); } return result; } }二)快速选择算法(时间复杂度O(N))
1)先按照基准值将数组划分成三块，分别是小于key，等于key和大于key，假设[0，left]有a个元素，[left，right-1)有b个元素，[right，N-1)有c个元素
2)现在我们要进行查找的元素是第k小的元素
2.1)if(a>=k)那么现在只是需要在[0，left)区间找到第key小的元素即可
如果在[0,left)区间之内无法找到第k小的元素
2.2)if(a+b>=k)那么直接返回元素array[left]
2.3)else 直接去[right，n-1)区间内去进行查找第k-a-b小的元素
class Solution { //这个函数是交换两个位置的元素 public void swap(int[] array,int i,int j){ int temp=array[i]; array[i]=array[j]; array[j]=temp; } public int[] SortAndFind(int[] array,int left,int right){ Random random=new Random(); int randomIndex=random.nextInt(right-left+1); int resultIndex=randomIndex+left; int temp=array[resultIndex];//基准元素选取完成 int leftIndex=left-1; int rightIndex=right+1; int index=left; while(index<rightIndex){ if(array[index]==temp){ index++; }else if(array[index]<temp){ leftIndex++; swap(array,leftIndex,index); index++; }else{ rightIndex--; swap(array,rightIndex,index); } } return new int[]{leftIndex,rightIndex}; } public void QuickSort(int[] array,int left,int right,int k){ if(right<=left) return; int[] result=SortAndFind(array,left,right); int a=result[0]-left+1; int b=result[1]-result[0]-1; int c=right-result[1]+1; if(a>=k){ QuickSort(array,left,result[0],k); }else if(a+b>=k){ return; }else{ QuickSort(array,result[1],right,k-a-b); } } public int[] getLeastNumbers(int[] array, int k) { QuickSort(array,0,array.length-1,k); int[] ret=new int[k]; //相当于是把数组中的前key个元素放到了最前面 for(int i=0;i<k;i++){ ret[i]=array[i]; } return ret; } }
五)归并排序:宏观思想
归并排序的流程充分的体现了分而治之的思想，大体流程主要分成两部:
分:将数组一分为二分成两部分，一直分解到数组的长度是1，使整个数组的排序过程被分为左半部分排序+右半部分排序
治:将两个较短的有序数组合并成一个较长的有序数组，一直合并到最初的长度
1)先找到中间结点的值，把左区间排一下序，让右区间排一下序，然后在合并两个有序数组
2)在本层先把数组分成两块，先找到中间值，先让mid左边的数组的数有序，再让mid右边的数有序，在合并两个区间内的数组元素，而在让左边的数组有序的过程中，还是在左边的数组中找到一个基准值，不断地进行划分合并；
3)现根据中点划分区间，先把左右区间排个序
4)然后合并两个有序数组
六)数组中的逆序对
剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode）
解法1:暴力枚举两层for循环
使用归并排序的思想来解决这个问题:
1)如果我想要求出整个数组的逆序对，首先将数组按照中间点划分成两部分
2)先在左边挑出a个逆序对，再从右边挑出b个逆序对，再从左边挑一个数，再从右边挑选一个数，看看是否能够组成逆序对，左右组成逆序对的个数使c个，那么数组一共的逆序对的个数就是N=a+b+c，本质上还是一个暴力枚举
3)现在再来想一下:
首先还是将数组划成两部分:
1)先在左半部分找到a个逆序对，然后针对于左半部分的元素进行排序
2)然后在右半部分找到b个逆序对，然后针对于右半部分的元素进行排序
3)然后在左边找一个数，右边找一个数，然后再进行组合，此时是否将左半部分的元素进行排序和右半部分的元素进行排序并不重要，因为左半部分的元素一定是大于右半部分的元素的，我们只进行关心的是在前半段区间内找到一个数之后，在后半段区间内只需要找到比这个数小的元素即可，根本不需要关心后半段区间内的元素是否有序，或者是说固定右半段区间内的元素，只需要找到前段区间内有多少元素是比当前元素大的，至于前半段区间是否有序，我是不会关心的，所以当对两段区间进行排序的时候，是不会影响一左一右的挑法的
