前言：
眼前兄弟们对“n元数组所构成的空间的基”大约比较讲究，咱们都想要分析一些“n元数组所构成的空间的基”的相关知识。那么小编也在网上网罗了一些关于“n元数组所构成的空间的基””的相关知识，希望兄弟们能喜欢，朋友们快快来学习一下吧！优化：增加pivot的随机性可以让算法更加稳定
解法：快排基础上微改代码
先手写快排代码
//快排核心 private int quickSort(int[] nums, int start, int end){ //这里没有写递归终止条件，这题不是要递归排序 int i = start; int j = end; int pivot = nums[start]; //选择第一个为锚点元素 while(i < j){ while(i < j && nums[j] >= pivot){ j--; } while(i < j && nums[i] <= pivot){ i++; } //交换元素 // swap(nums, i, j) ; //用这个没有全部通过，bug int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } //交换锚点元素至临界位置 // swap(nums, start, j);用这个没有全部通过，bug nums[start] = nums[j]; nums[j] = pivot; return i; //继承递归； // quickSort(nums, start, i-1); // quickSort(nums, i+1, end); }}快排思想两个指针，left,指向第一个，right,指最后一个。向中间靠拢，右边找比锚点元素小的值，左边找比锚点元素大的值。找到了，让这个两个值交换位置，直到left == right , 这个时候把锚点元素和left的值交换。这样锚点元素左边 都是比他小的， 右边都是比他大的
上面的返回值是int 就是我们要找的第k 大吗，不是。返回的只是随机的一个位置。这个时候利用二分查找。
int resIndex = quickSort(nums, start, end);
if(resIndex == kTarget){
return nums[resIndex];
}else if(resIndex > kTarget){
end = resIndex - 1;
}else if(resIndex < kTarget){
start = resIndex + 1;
}
全部代码：
时间复杂度：O(N)，N 是数组的长度
空间复杂度：O(1)，没有借助额外的空间。
class Solution { public int findKthLargest(int[] nums, int k) { // int start = 0, end = nums.length - 1; int kTarget = nums.length - k; while(true){ int resIndex = quickSort(nums, start, end); if(resIndex == kTarget){ return nums[resIndex]; }else if(resIndex > kTarget){ end = resIndex - 1; }else if(resIndex < kTarget){ start = resIndex + 1; } } } //快排核心 private int quickSort(int[] nums, int start, int end){ //这里没有写递归终止条件，这题不是要递归排序 int i = start; int j = end; int pivot = nums[start]; //选择第一个为锚点元素 while(i < j){ while(i < j && nums[j] >= pivot){ j--; } while(i < j && nums[i] <= pivot){ i++; } //交换元素 // swap(nums, i, j) ; //用这个没有全部通过，bug int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } //交换锚点元素至临界位置 // swap(nums, start, j);用这个没有全部通过，bug nums[start] = nums[j]; nums[j] = pivot; return i; //继承递归； // quickSort(nums, start, i-1); // quickSort(nums, i+1, end); } private void swap(int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = nums[i]; }}但是这样写，面试官会让你优化的！
优化：增加pivot的随机性可以让算法更加稳定
Random.nextInt(n)方法，是生成一个随机的int值，该值介于[0,n)的区间
Random random = new Random();
// 在区间随机选择一个元素作为
if (start > end) {
int randomIndex = 1 + random.nextInt(end); //包含0 不包含end, 为了不是0， 加一个1；
swap(nums, start, randomIndex);
}
完整代码：
import java.util.Random;class Solution { public int findKthLargest(int[] nums, int k) { // int start = 0, end = nums.length - 1; int kTarget = nums.length - k; while(true){ int resIndex = quickSort(nums, start, end); if(resIndex == kTarget){ return nums[resIndex]; }else if(resIndex > kTarget){ end = resIndex - 1; }else if(resIndex < kTarget){ start = resIndex + 1; } } } //快排核心 private int quickSort(int[] nums, int start, int end){ //这里没有写递归终止条件，这题不是要递归排序 int i = start; int j = end; Random random = new Random(); // 在区间随机选择一个元素作为 if (start > end) { int randomIndex = 1 + random.nextInt(end); //包含0 不包含end, 为了不是0， 加一个1； swap(nums, start, randomIndex); } int pivot = nums[start]; //选择第一个为锚点元素 while(i < j){ while(i < j && nums[j] >= pivot){ j--; } while(i < j && nums[i] <= pivot){ i++; } //交换元素 // swap(nums, i, j) ; //用这个没有全部通过，bug int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } //交换锚点元素至临界位置 // swap(nums, start, j);用这个没有全部通过，bug nums[start] = nums[j]; nums[j] = pivot; return i; //继承递归； // quickSort(nums, start, i-1); // quickSort(nums, i+1, end); } private void swap(int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = nums[i]; }}加油啊：：：：：PPPP
标签： #n元数组所构成的空间的基
