iis默认网站 建设中,杭州建设信用网官网,网页布局设计摘要,陕西网站建设技术方案Problem: 785. 快速排序 文章目录 思路解题方法复杂度Code方法一#xff08;调用系统类库#xff09;方法二#xff08;随机快速排序经典版#xff09;方法三 #xff08;利用荷兰国旗问题改写快排#xff09; 思路 这个问题要求实现快速排序算法#xff0c;对给定的整数… Problem: 785. 快速排序 文章目录 思路解题方法复杂度Code方法一调用系统类库方法二随机快速排序经典版方法三 利用荷兰国旗问题改写快排 思路 这个问题要求实现快速排序算法对给定的整数数组进行从小到大的排序。 快速排序算法的工作原理是从数组中选择一个“枢轴”元素然后将其他元素分区为两个子数组一个包含小于枢轴的元素另一个包含大于枢轴的元素。然后通过对两个子数组递归调用快速排序算法进行排序。 快速排序的时间复杂度在最好和平均情况下为O(n log n)在最坏情况下为O(n^2)但对于大多数输入最坏情况并不常见。空间复杂度为O(log n)到O(n)取决于快速排序的版本并假设不计算存储输入所需的空间。 解题方法 方法一调用系统类库这种方法是最简单的直接调用Java的Arrays.sort()方法对数组进行排序。 方法二随机快速排序经典版这种方法是快速排序的经典实现通过随机选择一个元素作为枢轴然后将数组分为两部分一部分是小于枢轴的元素另一部分是大于枢轴的元素然后对这两部分分别进行快速排序。 方法三利用荷兰国旗问题改写快排这种方法是快速排序的一个变种通过将数组分为三部分一部分是小于枢轴的元素一部分是等于枢轴的元素一部分是大于枢轴的元素然后对小于枢轴和大于枢轴的两部分分别进行快速排序。 复杂度
时间复杂度: 时间复杂度在最好和平均情况下是 O ( n l o g n ) O(n log n) O(nlogn)在最坏情况下是 O ( n 2 ) O(n^2) O(n2)。 空间复杂度: 空间复杂度是 O ( l o g n ) O(log n) O(logn)。 Code
方法一调用系统类库
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int n;static int MAXN 100001;static int[] arr new int[MAXN];public static void main(String[] args) throws IOException {n nextInt();for(int i 0; i n; i) {arr[i] nextInt();}Arrays.sort(arr, 0, n);StringBuffer sb new StringBuffer();for(int i 0; i n; i) {sb.append(arr[i]);sb.append( );}out.println(sb);out.flush(); }static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}方法二随机快速排序经典版 未通过所有样例这种方法不推荐 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int n;static int MAXN 100001;static int[] arr new int[MAXN];public static void main(String[] args) throws IOException {n nextInt();for (int i 0; i n; i) {arr[i] nextInt();}quickSort(0, n - 1);StringBuffer sb new StringBuffer();for (int i 0; i n; i) {sb.append(arr[i]);sb.append( );}out.println(sb);out.flush();}public static void quickSort(int l, int r) {if (l r) {return;}int x arr[l (int) (Math.random() * (r - l 1))];int mid partition(l, r, x);quickSort(l, mid - 1);quickSort(mid 1, r);}private static int partition(int l, int r, int x) {int a l, xi 0; // 记录等于x的位置for (int i l; i r; i) {if (arr[i] x) {swap(a, i);if (arr[a] x) {xi a;}a;}}swap(xi, a - 1);return a - 1;}private static void swap(int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
方法三 利用荷兰国旗问题改写快排
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int n;static int MAXN 100001;static int[] arr new int[MAXN];public static void main(String[] args) throws IOException {n nextInt();for (int i 0; i n; i) {arr[i] nextInt();}quickSort(0, n - 1);StringBuffer sb new StringBuffer();for (int i 0; i n; i) {sb.append(arr[i]);sb.append( );}out.println(sb);out.flush();}public static int first, last;public static void quickSort(int l, int r) {if(l r) {return;}int x arr[l (int) (Math.random() * (r - l 1))];partition(l, r, x);quickSort(l, first - 1);quickSort(last 1, r);}private static void partition(int l, int r, int x) {if(l r) {return;}first l;last r;int i l;while(i last) {if(arr[i] x) {i;} else if(arr[i] x) {swap(i, first);} else {swap(i, last--);}}}private static void swap(int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
