912. 排序数组

目录

题目链接

题目

解题思路

代码

题目链接

912. 排序数组 - 力扣（LeetCode）

题目

解题思路

法一：使用内置方法(过是能过,但是不符合题目要求)（超时）

法二：使用简单的快速排序(每次以left索引为目标值进行判断),时间复杂度高（超时）

法三：随机索引的快速排序（勉强过,相同元素会重复交换）

法四：双路快排

法五：三路快排

代码

法一：内置方法

class Solution {
    public int[] sortArray(int[] nums) {
        Arrays.sort(nums);
        return nums;
    }
}

法二：快速排序(固定索引)

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums,int left,int right){
        if(left>=right){
            return ;
        }
        int partiIndex=partition(nums,left,right);
        quickSort(nums,left,partiIndex-1);
        quickSort(nums,partiIndex+1,right);
    }
    public int partition(int[] nums,int left,int right){
        int privot=nums[left];
        int j=left;
        for(int i=left+1;i<=right;i++){
            if(nums[i]<=privot){
                j++;
                swap(nums,i,j);
            }
        }
        swap(nums,left,j);
        return j;
    }
    public void swap(int[] nums,int i ,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    } 
}

法三：随机索引

import java.util.Random;
class Solution {
    private final static Random random=new Random(System.currentTimeMillis());
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums,int left,int right){
        if(left>=right){
            return ;
        }
        int partiIndex=partition(nums,left,right);
        quickSort(nums,left,partiIndex-1);
        quickSort(nums,partiIndex+1,right);
    }
    public int partition(int[] nums,int left,int right){
        int idx=left+ random.nextInt(right-left+1);
        swap(nums,idx,left);
        int privot=nums[left];
        int j=left;
        for(int i=left+1;i<=right;i++){
            if(nums[i]<privot){
                j++;
                swap(nums,i,j);
            }
        }
        swap(nums,left,j);
        return j;
    }
    public void swap(int[] nums,int i ,int j){
        if(nums[i]==nums[j]) return ;
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    } 
}

法四：双路快排

import java.util.Random;
class Solution {
    private final static Random random=new Random(System.currentTimeMillis());
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums,int left,int right){
        if(left>=right){
            return ;
        }
        int partiIndex=partition(nums,left,right);
        quickSort(nums,left,partiIndex-1);
        quickSort(nums,partiIndex+1,right);
    }
    public int partition(int[] nums,int left,int right){
        int idx=left+ random.nextInt(right-left+1);
        swap(nums,idx,left);
        int val=nums[left];
        int le=left+1;
        int ge=right;
        while(true){
            while(le<=ge &&nums[le]<val){
                le++;
            }
            while(le<=ge && nums[ge]>val){
                ge--;
            }
            if(le>=ge){
                break;
            }
            swap(nums,le,ge);
            le++;
            ge--;
        }
        swap(nums,left,ge);
        return ge;
    }
    public void swap(int[] nums,int i ,int j){
        if(nums[i]==nums[j]) return ;
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    } 
}

法五：三路快排

import java.util.Random;
class Solution {
    private final static Random random=new Random(System.currentTimeMillis());
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums,int left,int right){
        if(left>=right){
            return ;
        }
        int idx=left+ random.nextInt(right-left+1);
        swap(nums,idx,left);
        int val=nums[left];
        int lt=left+1;
        int gt=right;
        int i=lt;
        while(i<=gt){
            if(nums[i]==val){
                i++;
            }else if(nums[i]<val){ 
                swap(nums,lt,i);
                lt++;
                i++;
            }else{
                swap(nums,gt,i);
                gt--;
            }
        }
        swap(nums,left,lt-1);
        quickSort(nums,left,lt-2);
        quickSort(nums,gt+1,right);
    }
 

 
    public void swap(int[] nums,int i ,int j){
        if(nums[i]==nums[j]) return ;
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    } 
}