计数排序
计数排序适合排序关键字很有限的情况,如这里只有3个.
class Solution {
public void sortColors(int[] nums) {
int[] count={0,0,0};// 存放0,1,2三个元素的频率
for (int num : nums) {
assert num >= 0 && num <=2;
// nums[] = {0,1,2} 自身元素nums[x]与自身频率count[x]是一一对应的
count[num]++;
}
// nums[]元素值{0,1,2}与count[]下标值是一一对应的
for(int j=0;j<count.length;j++){
int presum=sum(count,j);
// 解决了下标递增的问题,这样即使频率有多个也不怕了
for(int i=presum;i<count[j]+presum;i++)
nums[i] = j;
}
}
public static int sum(int[] count,int index){
int sum =0;
// count中下标为[0,index)的和是nums[i]中i的下标开始值
for(int i=0;i< index ;i++)
sum += count[i];
return sum;
}
}三路快排
能应用的核心还是在于元素种类很有限,可以逐种情况判断:把遍历到的每个元素放到对应的区间0或1或2
class Solution {
public void sortColors(int[] nums) {
int zero = -1;
//[0...zero]放0,初始化为-1是因为我不知道最开始nums[0,0]是几,-1致其其中没有任何元素
int two = nums.length;
//[two...nums.length-1] == 2
//[zero..i] == 1
for(int i=0;i<two;){
if(nums[i] == 0){
swap(nums,++zero,i++);
}else if(nums[i] == 1){
i++;
}else{// nums[i] == 2
assert nums[i] == 2;
// 这里i不应该++,因为换过来了一个新的nums[-two]
swap(nums,i,--two);
}
}
}
public static void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}Merge Sorted Array
继承自三路快排的区间划分思路: [0…one…m+n|0…two] 中间[one…m+n]部分是空的,与上题不同的是这个部分区间用作了复制(不是有着明确种类划分)
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
if(n== 0){
return;
}
int one = m-1;//[0,one]
int two = n-1;//[0,two]
// 对nums1,刚开始[m,m+n]是额外给的空间
// 如果没有这额外空间,我是得额外开辟吧!
int three=m+n-1;
// 和链表的merge()很像
for(;one>=0 && two>=0;three--){
if(nums2[two]>nums1[one]){
nums1[three]=nums2[two--];
}else{
nums1[three] = nums1[one--];
}
}
// 不需要处理可能还有的剩下的[0,one] 元素，因为这些元素本来就是排序好in-place的
if(two>=0)
while(two>=0)
nums1[three--]=nums2[two--];
}
}继承自快排的快速选择
kth-largest-element-in-an-array
class Solution {
public int findKthLargest(int[] nums, int k) {
int lo=0;
int hi=nums.length-1;//[0,hi]
// 找第k大的精髓是不看数组元素的具体值，只要找到目标第k大元素的索引即可
// 简单推理一下：
// 1. 升序排序后，第1大的元素在末尾 `len(nums) - 1`。
// 2. 升序排序后，第2大的元素就在 `len(nums) - 2` 的位置，以此类推。
// 3. 泛化上述规律，升序排序后，第 `k` 大的元素在 `len(nums) - k` 的位置。
int targetIndex = nums.length - k;
return selectAscendingKthLargest(nums,l,r,targetIndex);
}
public int selectAscendingKthLargest(int[] nums, int l, int r, int targetIndex) {
int pivotIndex = ascendingPartition(nums, l, r);
if (pivotIndex == targetIndex) {
return nums[pivotIndex];
} else if (pivotIndex < targetIndex) {
//如果现在的轴值索引大于目标索引，只需要看轴值左边区间
return selectAscendingKthLargest(nums,++pivotIndex,r,targetIndex);
} else {
return selectAscendingKthLargest(nums,l,--pivotIndex,targetIndex);
}
}
/**
* 返回升序分区后的轴值下标
* 其实一个单指针就可以解决，不一定要用双指针i、j<b>
* 但是单指针的优化手段比较少，遇到数组已经部分排序的场景比双指针低
* @return pivot: 所有小于轴值的元素应该位于其左侧，而所有大于或等于轴值的元素应位于其右侧
*/
public static int ascendingPartition(int[] nums,int lo,int hi){
if(lo>=hi) return lo;// 为了防止传进来的已经指针相遇
int pivot = handleAndGetFirstIndexAsPivot(nums,lo,hi);
int i = lo; // i初始化为lo,因为已经留出第一位作为轴值所在的下标位置，所以不需要比较。如果i初始化为 lo-1,轴值参与比较的同时，轴值的下标位置就会丢失，从而不能在最后将轴值放到它应该在的位置上
int j = hi+1;
while(true){
//i代表的是小于等于pivot的元素，如果当nums[i] 不满足小于等于轴值时，结束向右移动，等待把这个不满足条件的nums[i] 换到右边
while(i <= hi && nums[++i] < pivot);
//j代表的是大于等于pivot的元素，当nums[j] 不满足大于等于轴值时，结束向左移动，等待把这个不满足条件的nums[j] 换到左边
while(j >= lo && pivot <= nums[--j]);
// 如果左边遍历指针和右边的已经相遇或交叉，表示以下条件已经满足：
// - 所有位于 `leftSearchIndex` 左侧的元素都已被检查，并且小于轴值
// - 所有位于 `rightSearchIndex` 右侧的元素（包括轴值本身，如果轴值在最右端的话）都已被检查，并且大于或等于轴值
// 因此，在双指针相遇或交错的时候终止循环
if(i>=j ) break;
swap(nums,i,j);
}
swap(nums,lo,j);
return j;
}
/**
* 可以通过随机选择轴值来降低平均时间复杂度
*/
public int handleAndGetFirstIndexAsPivot(int[] nums, int l, int r) {
int randomIndex = l + new Random().nextInt(r - l + 1);
swap(nums, l, randomIndex);
return nums[l];
}
public static void swap(int[] nums,int j,int i){
int temp=nums[j];
nums[j]=nums[i];
nums[i]=temp;
}
}