网站建设网站建设公司,深圳市设计网站,长春开发小程序开发,网站建设单位不给数据库原理
对于一个数组x#xff0c;快速排序流程如下#xff1a;
确定分界点a#xff0c;可以取x[l]、x[r]、x[l r / 2]、随机#xff08;四种都可以#xff09;调整区间#xff0c;使得#xff1a;区间被分成 a 和 a的两部分#xff0c;左边 a#xff…原理
对于一个数组x快速排序流程如下
确定分界点a可以取x[l]、x[r]、x[l r / 2]、随机四种都可以调整区间使得区间被分成 a 和 a的两部分左边 a右边 a注意a不一定在原来的位置了递归处理左右两边
重点在于第二步调整区间上。 做法是在区间[l, r]中指定两个指针i、j。
当i指向的数 a的时候i往右移动当j指向的数 a的时候j往左移动
当i和j停下来的时候说明x[i] ax[j] a则x[i] x[j]。那根据我们的想要实现的目的要保证左边 a右边 a也就是x[i] x[j]。因此需要将x[i]与x[j]交换。
复杂度
代码
import java.util.*;
import java.io.*;class Main {public static void quick(int[] x, int l, int r) {if (l r) return ;int a x[l r 1], i l - 1, j r 1;while (i j) {/**内层的循环不能加 i j原因如果加了i j那么两个do while之后i j。此时如果x[j] a而后续的递归就会出问题因为要保证[l, j]的数都 a所以原则就是最后外层循环退出的时候要保证i j不能i j*/do i ; while (x[i] a);do j -- ; while (x[j] a);if (i j) {int t x[i];x[i] x[j];x[j] t;}}quick(x, l, j);quick(x, j 1, r);}public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[] x new int[n];for(int i 0; i n; i ) x[i] sc.nextInt();quick(x, 0, n - 1);for(int i 0; i n; i ) System.out.print(x[i] );}
}
