思路:
指定一个数字,将数组比他小的放到左边,比他大的放到右边,实现归位
然后再指定一个数字递归,一直遍历完数组
最好的情况每次指定的都是中间位置的数字,划分完后两边长度相等,2T(n/2) + O(n),复杂度O(nlog(n))
可以证明,平均情况下的时间复杂度也是O(nlog(n))
最坏的情况,每次指定的都是最小的数字,n的复杂度归位,一共n次,T(n-1) + O(n),复杂度O(n^2)
方式一、对撞型指针+指定头元素
class Solution {
public int[] sortArray(int[] nums) {
trace(nums,0,nums.length - 1);
return nums;
}
public void trace(int[] nums,int start,int end) {
if(start>=end){
return;
}
int p = nums[start];
int l = start;
int r = end;
while(l<r){
while(nums[r]>=p&&l<r){
r--;
}
nums[l] = nums[r];
while(nums[l]<=p&&l<r){
l++;
}
nums[r] = nums[l];
}
nums[l] = p;
trace(nums,l + 1,end);
trace(nums,start,l-1);
}
}
方式二、对撞型指针+指定中间
这里要注意的细节很多,判断条件的时候nums[l]>p不能等于,不然左指针会跑到右边去同理右边
同时l<=r,不能是小于文章来源:https://www.toymoban.com/news/detail-691792.html
class Solution {
public int[] sortArray(int[] nums) {
trace(nums,0,nums.length - 1);
return nums;
}
public void trace(int[] nums,int start,int end) {
if(start>=end){
return;
}
int p = nums[(start+end)/2];
int l = start;
int r = end;
while(l<=r){
while(nums[r]>p&&l<=r){
r--;
}
while(nums[l]<p&&l<=r){
l++;
}
if(l<=r){
swap(nums,l,r);
l++;
r--;
}
}
trace(nums,start,r);
trace(nums,l,end);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
方式三、快慢指针+指定尾元素文章来源地址https://www.toymoban.com/news/detail-691792.html
lass Solution {
public int[] sortArray(int[] nums) {
partition(nums, 0, nums.length - 1);
return nums;
}
public void partition(int[] nums, int l, int r) {
if(l<r){
int pivot = nums[r];
int i = l - 1;
//快慢指针找到目标位置
for (int j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums, i, j);
}
}
//放置目标元素
swap(nums, i + 1, r);
int p = i+1;
//递归
partition(nums,l,p-1);
partition(nums,p+1,r);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
到了这里,关于算法通关村第10关【青铜】| 快速排序各种写法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!