做网站需要自备服务器吗,一个人免费观看视频播放,深圳网站建设服务电话,html5汽车网站模板目录 题目1-思路-快排1-1 快排的核心思想快速排序算法步骤优美的调整区间 1-2 ⭐快排的实现 2- 实现⭐912. 排序数组——题解思路 3- ACM 实现 题目
原题连接#xff1a;912. 排序数组 1-思路-快排
1-1 快排的核心思想
选择一个基准 基准左侧的元素都小于该元素基准右侧的元… 目录 题目1-思路-快排1-1 快排的核心思想快速排序算法步骤优美的调整区间 1-2 ⭐快排的实现 2- 实现⭐912. 排序数组——题解思路 3- ACM 实现 题目
原题连接912. 排序数组 1-思路-快排
1-1 快排的核心思想
选择一个基准 基准左侧的元素都小于该元素基准右侧的元素都大于该元素 快速排序算法步骤
① 确定分界点 方式有三种第一种取左边界点 q[ l ]第二种取中间点q[ lr ]第三种取右边界点q[ r ]随机 ② 调整区间★难点 使得左半边区间内的数都小于等于 x 右半边区间内的数都大于等于 x ③ 递归 递归处理左右两段
优美的调整区间
用两个指针分别指向数组的左边和右边两个指针同时往中间走。如果指针 i 指向的数组的元素值小于 x 则指针 i 向右移动一位以此类推一直往下移动直到指针 i 所指向的某个元素的值 大于等于 x此时指针 i 停下不动。同理此时移动指针 j 若指针 j 指向的元素的值大于等于 x 则指针 j 便向左移动直到移动到 j 所指向的值小于等于 x 。 当两个指针都停下来的时候swap 交换两个指针指向的数之后两个指针继续往中间走以此类推直到两个指针相遇为止。
1-2 ⭐快排的实现 public void quickSort(int[] nums,int left,int right){if(rightleft) return;// 定义 int i left-1;int j right1;int x nums[(ij)/2];while(ij){do{i;}while(nums[i]x);do{j--;}while(nums[j]x);if(ij){int tmp nums[i];nums[i] nums[j];nums[j] tmp;}}quickSort(nums,left,j);quickSort(nums,j1,right);}2- 实现
⭐912. 排序数组——题解思路 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(rightleft) return;// 定义 int i left-1;int j right1;int x nums[(ij)/2];while(ij){do{i;}while(nums[i]x);do{j--;}while(nums[j]x);if(ij){int tmp nums[i];nums[i] nums[j];nums[j] tmp;}}quickSort(nums,left,j);quickSort(nums,j1,right);}
}3- ACM 实现
public class quickSort {public static void quickSort(int[] nums,int left,int right){if(rightleft) return;// 定义int i left-1;int j right1;int x nums[(ij)/2];while(ij){do{i;}while(nums[i]x);do{j--;}while(nums[j]x);if(ij){int tmp nums[i];nums[i] nums[j];nums[j] tmp;}}quickSort(nums,left,j);quickSort(nums,j1,right);}public static void main(String[] args) {Scanner sc new Scanner(System.in);System.out.println(输入数组长度);int n sc.nextInt();int[] nums new int[n];for(int i 0 ;i n;i){nums[i] sc.nextInt();}quickSort(nums,0,nums.length-1);System.out.println(排序结果为);for (int i:nums){System.out.print(i );}}
}
