本文主要是介绍快排不同实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
区别主要在于如何将大于和小于等于pt_value的元素分组
测试样例case
https://leetcode.cn/problems/sort-an-array/
1. 正常交换搬移
超时
class Solution {private void swap(int[] nums, int l, int r) {int t = nums[l];nums[l] = nums[r];nums[r]= t;}private void quickSort(int[] nums, int l, int r) {if (r <= l) {return;}int ptVal = nums[l];int lc = l;int rc = r;while (lc < rc) {while (nums[lc] <= ptVal && lc < r) {lc++;}while(nums[rc] > ptVal && l < rc) {rc--;}if (rc > lc) {swap(nums, lc, rc);}}swap(nums, rc, l);quickSort(nums, l, rc - 1);quickSort(nums, rc+1, r);}public int[] sortArray(int[] nums) {if (nums.length < 1) {return nums;}quickSort(nums, 0, nums.length - 1);return nums;}
}
2. 随机pt
执行用时分布
2020ms 击败8.93%使用 Java 的用户
class Solution {private void swap(int[] nums, int l, int r) {int t = nums[l];nums[l] = nums[r];nums[r]= t;}private void quickSort(int[] nums, int l, int r) {if (r <= l) {return;}int rand = new Random().nextInt(r - l + 1);swap(nums, l, l+rand);int ptVal = nums[l];int lc = l;int rc = r;while (lc < rc) {while (nums[lc] <= ptVal && lc < r) {lc++;}while(nums[rc] > ptVal && l < rc) {rc--;}if (rc > lc) {swap(nums, lc, rc);}}swap(nums, rc, l);quickSort(nums, l, rc - 1);quickSort(nums, rc+1, r);}public int[] sortArray(int[] nums) {if (nums.length < 1) {return nums;}quickSort(nums, 0, nums.length - 1);return nums;}
}
3. 三指针
执行用时分布
1015
ms
击败
32.07%
使用 Java 的用户
class Solution {private void swap(int[] nums, int l, int r) {int t = nums[l];nums[l] = nums[r];nums[r]= t;}private void quickSort(int[] nums, int l, int r) {if (r <= l) {return;}// 小于区间右边界int i = l;// 大于区间左边界int rl = r + 1;// 指针int cursor = l + 1;int selVal = nums[l];while (cursor < rl) {if (nums[cursor] > selVal) {rl -= 1;swap(nums, rl, cursor);} else if (nums[cursor] < selVal){swap(nums, i+1, cursor);cursor += 1; i += 1;} else {cursor+=1;}}swap(nums, i, l);quickSort(nums, l, i-1);quickSort(nums, rl, r);}public int[] sortArray(int[] nums) {if (nums.length < 1) {return nums;}quickSort(nums, 0, nums.length - 1);return nums;}
}
这篇关于快排不同实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!