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;} 
}