编辑
阿华代码，不是逆风，就是我疯
你们的点赞收藏是我前进最大的动力！！
希望本文内容能够帮助到你！！
目录
本文主要介绍了排序中的快排算法，和优化思路，按照题号做，难度层层递进，第二题是最基础的模版，第三题、第四题在此基础上进行算法优化
一：颜色分类
编辑
编辑
class Solution { public void sortColors(int[] nums) { int left = -1 , right = nums.length ; //先把框架搭出来 // 遍历数组 for(int i = 0 ; i < right ; ){ if(nums[i] == 0){ left++; swap(nums,i,left); i++; }else if(nums[i] == 1){ i++; }else{ right--; swap(nums,i,right); } } } //交换数组中的两个元素传入数组和下标 public void swap(int[] nums,int a , int b){ int tem = nums[a]; nums[a] = nums[b]; nums[b] = tem; } }
二：排序数组（分三组快排）
编辑
编辑
class Solution { public int[] sortArray(int[] nums) { int n = nums.length; for(int j = n-1 ; j > 0 ; j--){ for(int i = 0 ; i < j ;){ if(nums[i] > nums[i+1]){ swap(nums , i , i+1); i++; }else{ i++; } } } return nums; } public void swap(int nums[] , int a , int b){ int tem = nums[a]; nums[a] = nums[b]; nums[b] = tem; } }
编辑
编辑
编辑
class Solution { public int[] sortArray(int[] nums) { quickSort(nums,0,nums.length-1); return nums; } public void quickSort(int[] nums , int l , int r){ if(l >= r){ return; } // Random random = new Random(); // int index = random.nextInt(r - l + 1) + l;//随机下标 // int key = nums[index];//随机数 int key = nums[new Random().nextInt( r - l + 1) + l]; int left = l-1 , right = r+1 , i = l; while(i < right){ if(nums[i] < key){ swap(nums,i++,++left); }else if(nums[i] == key){ i++; }else{ swap(nums,i,--right); //i++;不能++换过来的数还是一个没有被排序的数 } } quickSort(nums,l,left); quickSort(nums,right,r); } public void swap(int[] nums , int a , int b){ int tem = nums[a]; nums[a] = nums[b]; nums[b] = tem; } }
三：数组中的第k个最大元素
第k个最大的元素，重复元素也算
易错点
①递归出口的判断（l == r）
②while循坏的条件(l < right)
③i的初始值是l（很重要，因为划分区间后，i是从l开始移动的）
④优化的三个条件，各个区间的元素个数，需要随机应变，判断条件要想好
⑤方法的返回值类型，int或者void，如果为int类型，递归出口和优化的三个条件中写返回就可以了
⑥最稳妥的方法就是不优化，先给整个数组进行完全快排，然后在排序好的数组中，进行结果的查找
编辑
编辑
class Solution { public int findKthLargest(int[] nums, int k) { //1:实现递归排序,传入数组，左边界，右边界，k int l = 0 , r = nums.length-1; return quickSort(nums,l,r,k); } // 把数组分成三部分 public int quickSort(int[] nums , int l , int r , int k){ //递归出口 if(l == r){ return nums[l]; } //产生随机数作为下标，作为划分三部分的基准值 Random random = new Random(); int num = random.nextInt(r - l + 1); int index = num + l; int key = nums[index]; int left = l-1 , right = r+1 , i = l; while(i < right){ if(nums[i] > key){ swap(nums , i , --right); }else if(nums[i] == key){ i++; }else{ swap(nums , i++ , ++left);//此处i++是因为 >key的值和=key的值发生了交换 } } //根据划分的三个部分在找 // 三个部分的区间为[l,left] [left+1,right-1] [right,r] int a = left-l+1; int b = right-left-1; int c = r-right+1; if(c >= k){ return quickSort(nums,right,r,k); }else if(b + c >= k){ return key; }else{ return quickSort(nums,l,left,k-b-c); } } public void swap(int[] nums , int a , int b){ int tem = nums[a]; nums[a] = nums[b]; nums[b] = tem; } }
四：前k的最小的元素
前k的最小的元素
方法一：冒泡排序
编辑
class Solution { public int[] inventoryManagement(int[] stock, int cnt) { //方法一：冒泡排序 int n = stock.length; for(int i = 0 ; i < n ; i++){ for(int j = n-1 ; j > i ; j--){ if(stock[j] < stock[j-1]){ //把小的元素往前面放 swap(stock , j , j-1); } } } int[] ret = new int[cnt]; for(int i = 0 ; i < cnt ; i++){ ret[i] = stock[i]; } return ret; } public void swap(int[] stock , int a , int b){ int tem = stock[a]; stock[a] = stock[b]; stock[b] = tem; } }
方法二：基础快排思想
编辑
class Solution { public int[] inventoryManagement(int[] nums, int cnt) { //方法二：快排分三部分思想 int l = 0 , r = nums.length-1; quickSort(nums,l,r); int[] ret = new int[cnt]; for(int i = 0 ; i < cnt ; i++){ ret[i] = nums[i]; } return ret; } public void quickSort(int[] nums , int l , int r){ int left = l - 1 , right = r + 1 , i = l ; if(l >= r){ return; } // 在[l,r]区间进行排序 // 产生随机数 int index = new Random().nextInt( r - l + 1) + l; int key = nums[index]; while(i < right){ //小于的情况实际上就是，右边界和右边界元素的交换 if(nums[i] < key){ swap(nums,++left,i++); }else if(nums[i] == key){ i++; }else{ swap(nums,--right,i);//换过去的是未排序的元素 } } quickSort(nums,l,left); quickSort(nums,right,r); } public void swap(int[] nums , int a , int b){ int tem = nums[a]; nums[a] = nums[b]; nums[b] = tem; } }
方法三：优化版本
太快了2msNB
找前k个最小元素，每次递归都可以舍弃好多元素
编辑
class Solution { public int[] inventoryManagement(int[] nums, int cnt) { //方法三：快排分三部分思想 int l = 0 , r = nums.length-1; int k = cnt; quickSort(nums,l,r,k); int[] ret = Arrays.copyOf(nums,k); return ret; } public void quickSort(int[] nums , int l , int r , int k){ int left = l - 1 , right = r + 1 , i = l ; //递归这里的区间一定要想好，非常容易出错 if(l >= r){ return; } // 在[l,r]区间进行排序 // 产生随机数 int index = new Random().nextInt( r - l + 1) + l; int key = nums[index]; //i小于right是基于这个key进行排序，循环的条件很重要 while(i < right){ //小于的情况实际上就是，右边界和右边界元素的交换 if(nums[i] < key){ swap(nums,++left,i++); }else if(nums[i] == key){ i++; }else{ swap(nums,--right,i);//换过去的是未排序的元素 } } //根据划分的三个部分在找 // 三个部分的区间为[l,left] [left+1,right-1] [right,r] int a = left-l+1; int b = right-left-1; int c = r-right+1; if(k < a){ quickSort(nums,l,left,k); }else if(k <= a + b){ return; }else if(k > a + b){ quickSort(nums,right,r,k-a-b); } } public void swap(int[] nums , int a , int b){ int tem = nums[a]; nums[a] = nums[b]; nums[b] = tem; } }
