1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import java.io.*;
import java.util.*;
public class  阿一_1快排{
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter coup = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer t=new StreamTokenizer(cin);
    public static void main(String[] args) throws IOException {
        t.nextToken();
        int n = (int)t.nval;
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            t.nextToken();
            array[i] = (int)t.nval;
        }

        quickSort(array, 0, n - 1);

        System.out.println("排序后的数组：");
        for (int i = 0; i < n; i++) {
            coup.print(array[i] + " ");
            coup.flush();
        }
    }
public static void quickSort(int q[],int l,int r){
    if(l>=r) return;
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j) swap(q,i,j);
    }
    quickSort(q,l,j-1);
    quickSort(q,j+1,r);
}
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
}
// public static void quickSort(int[] array, int low, int high) {
//         if (low < high) {
//             int pivotIndex = partition(array, low, high);
//             quickSort(array, low, pivotIndex - 1);
//             quickSort(array, pivotIndex + 1, high);
//         }
//     }

//     public static int partition(int[] array, int low, int high) {
//         int pivot = array[high]; 
//         int i = low - 1; 
//         for (int j = low; j < high; j++) {
//             if (array[j] < pivot) {
//                 i++;
//                 swap(array, i, j);
//             }
//         }
//         swap(array, i + 1, high); 
//     }
// }

// import java.io.BufferedReader;
// import java.io.InputStreamReader;
// import java.io.StreamTokenizer;
// import java.util.Arrays;
// import java.util.Scanner;

// public class Main {
//  static int []a = new int[5000005];
//  static int x;
//  public static void main(String[] args) throws Exception{

//      int n;
//      StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
//      st.nextToken();
//      n=(int)st.nval;
//      // st.nextToken();
//      // x=(int)st.nval;
//      for(int i = 0;i<n;i++) {
//          st.nextToken();
//          a[i]=(int)st.nval;
//      }
//      quickSort(a,0,n-1);
//      for(int i=0;i<n;i++){
//             System.out.print(a[i] + " ");
//         }
//  }

//  public static void quickSort(int q[],int l,int r) {
//      if(l>=r)
//          return;
//      int pivot = q[l];
//      int i=l,j=r;
//      while(i<j) {
//          while(i<j && q[j]>=pivot) {
//              j--;
//          }
//          while(i<j && q[i]<=pivot) {
//              i++;
//          }
//          if(i<j) {
//              int temp=q[i];
//              q[i]=q[j];
//              q[j]=temp;
//          }
//      }
//      q[l]=q[i];
//      q[i]=pivot;
//      //if(i==x) return;
//      //if(i>x)
//      quickSort(q,l,i-1);
//      //else if(i<x)
//      quickSort(q,i+1,r);
//  }
// }