广州公司建设网站,征信中心个人信用查询,网站如何生成静态页面,wordpress字典插件大家好我是苏麟,今天带来快速排序 . 快速排序
单边快速排序(lomuto 洛穆托分区方案)
单边循环 (lomuto分区) 要点 :
选择最右侧元素作为基准点j 找比基准点小的#xff0c;i 找比基准点大的#xff0c;一旦找到#xff0c;二者进行交换。
交换时机: 找到小的#xff0c…大家好我是苏麟,今天带来快速排序 . 快速排序
单边快速排序(lomuto 洛穆托分区方案)
单边循环 (lomuto分区) 要点 :
选择最右侧元素作为基准点j 找比基准点小的i 找比基准点大的一旦找到二者进行交换。
交换时机: 找到小的且与i不相等oi找到 基准点元素后不应自增
最后基准点与i 交换i 即为基准点最终索引
B站解析 : 基础算法-210-排序算法-单边快排_哔哩哔哩_bilibili 代码 :
class Solution {public int[] sortArray(int[] nums) {int length nums.length;sort(nums,0,length - 1);return nums;}public void sort(int[] nums,int left,int right){if(left right){return;}int i qicke(nums,left,right);sort(nums,left,i - 1);sort(nums,i 1,right);}public int qicke(int[] nums,int left,int right){int i left;int j left;int p nums[right];while(j right){if(nums[j] p){if(i ! j){swap(nums,i,j);}i;}j;}swap(nums,i,right);return i; }public void swap(int[]nums,int i,int j){int temp nums[i];nums[i]nums[j];nums[j]temp;}
}
双边快速排序
双边循环要点 :
选择最左侧元素作为基准点 找比基准点小的i 找比基准点大的一旦找到二者进行交换
i从左向右j从右向左
最后基准点与i 交换i 即为基准点最终索引
B站解析 : 基础算法-211-排序算法-双边快排_哔哩哔哩_bilibili 解析 :
class Solution {public int[] sortArray(int[] nums) {int length nums.length;sort(nums,0,length - 1);return nums;}public void sort(int[] nums,int left,int right){if(left right){return;}int i qicke(nums,left,right);sort(nums,left,i - 1);sort(nums,i 1,right);}public int qicke(int[] nums,int left,int right){int i left;int j right;int p nums[left];while(i j){while(i j nums[j] p){j--;}while(i j nums[i] p){i;}swap(nums,i,j);}swap(nums,i,left);return i; }public void swap(int[]nums,int i,int j){int temp nums[i];nums[i]nums[j];nums[j]temp;}
} 小题一道
这道题是一个数组排序题目 , 没有指定什么排序 , 但是为了更好的学习快速排序 ,请大家用快速排序做这道题 , 但是有一个Bug 有的块排会超时间限制 , 请大家自己思考用什么样的快排 .
题目 :
LeetCode : 912 排序数组
912. 排序数组 分析 :
根据上面写出快排
解析 :
class Solution {public int[] sortArray(int[] nums) {int length nums.length;quickSort(nums,0,length - 1);return nums;}public void quickSort(int[] array,int start,int end){if (start end) {return; } int left start, right end; int pivot array[(start end) / 2];while (left right) {while (left right array[left] pivot){left;}while (left right array[right] pivot){ right--; }if (left right){ int temp array[left]; array[left] array[right]; array[right] temp; left;right--; }} quickSort(array, start, right); quickSort(array, left, end);}
}
这期就到这里 , 下期见!
