PAT1101 快速排序

暴力模拟超时

存在问题：

超时
格式错误

 1 /*
 2  快速排序Quit Sort
 3  pivot  枢轴
 4  */
 5 #include <iostream>
 6 #include <cstring>
 7 #include <string>
 8 #include <algorithm>
 9 
10 using namespace std;
11 
12 int n;
13 int a[100000+5];
14 int ans[100000+5];
15 bool b[100000+5];
16 
17 int main(){
18     freopen("test.txt", "r", stdin);
19     cin >> n;
20     for(int i=0; i<n; i++){
21         cin >> a[i];
22     }
23     int cnt = 0;
24     for(int i=0; i<n; i++){
25         bool flag = false;
26         
27         for(int j=0; j<i; j++){
28             if(a[i]<a[j]){
29                 b[i] = 0;
30                 flag = true;
31                 break;
32             }
33         }
34         
35         if(flag){
36             continue;  // 后面的操作不用进行
37         }
38         
39         for(int j=i+1; j<n; j++){
40             if(a[i]>a[j]){
41                 b[i] = 0;
42                 flag = true;
43                 break;
44             }
45         }
46         
47         if(flag == false){
48             b[i] = 1;
49             cnt++;
50         }
51     }
52     
53     cout << cnt << endl;
54     int index = 0;
55     for(int i=0; i<n; i++){
56         if(b[i] == 1){
57             ans[index] =  a[i];
58             index++;
59         }
60     }
61     // increasing order
62     sort(ans , ans+cnt);
63     for(int i=0; i<cnt; i++){
64         if(i!=0)
65             cout << " ";
66         cout << ans[i];
67     }
68     
69     return 0;
70 }

格式错误参看博客https://blog.csdn.net/luowei5513/article/details/52461083

输出格式为0，则要输出一个空行

之前一直以为是输出的序列不是升序，但是想想，不是升序应该报答案错误。23333，还强行加个sort

羞耻的代码修改，过了三个样例

 1 /*
 2  快速排序Quit Sort
 3  pivot  枢轴
 4  */
 5 #include <iostream>
 6 #include <cstring>
 7 #include <string>
 8 #include <algorithm>
 9 
10 using namespace std;
11 
12 int n;
13 int a[100000+5];
14 int ans[100000+5];
15 bool b[100000+5];
16 
17 int main(){
18     // freopen("test.txt", "r", stdin);
19     cin >> n;
20     for(int i=0; i<n; i++){
21         cin >> a[i];
22     }
23     int cnt = 0;
24     for(int i=0; i<n; i++){
25         bool flag = false;
26         
27         for(int j=0; j<i; j++){
28             if(a[i]<a[j]){
29                 b[i] = 0;
30                 flag = true;
31                 break;
32             }
33         }
34         
35         if(flag){
36             continue;  // 后面的操作不用进行
37         }
38         
39         for(int j=i+1; j<n; j++){
40             if(a[i]>a[j]){
41                 b[i] = 0;
42                 flag = true;
43                 break;
44             }
45         }
46         
47         if(flag == false){
48             b[i] = 1;
49             cnt++;
50         }
51     }
52     
53     if(cnt == 0){
54         cout << 0 << endl;
55         cout << endl;
56     }else{
57         cout << cnt << endl;
58         int index = 0;
59         for(int i=0; i<n; i++){
60             if(b[i] == 1){
61                 ans[index] =  a[i];
62                 index++;
63             }
64         }
65         // increasing order
66         sort(ans , ans+cnt);
67         for(int i=0; i<cnt; i++){
68             if(i!=0)
69                 cout << " ";
70             cout << ans[i];
71         }
72     }
73     
74     return 0;
75 }

View Code

快速排序

快速排序采用分治的思想，时间复杂度为：0(N*logN)

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 class QuickSort{
 6 public:
 7     int *quickSort(int *A, int n){
 8         // 快速排序
 9         QSort(A, 0, n-1);
10         return A;
11     }
12     
13     void QSort(int *A, int low, int high){
14         // 对数组A[low,...,high]
15         if(low < high){
16             int n;
17             n = Partition(A, low, high);
18             QSort(A, low, n-1);
19             QSort(A, n+1, high);
20         }
21     }
22     
23     int Partition(int *A, int low, int high){
24         // 交换数组A[low,...,high]的记录，支点记录到位，并返回其所在位置此时在他之前（后）的记录均不大（小）于它
25         int key = A[low];
26         while (low < high) {
27             while (low<high && A[high]>=key) {
28                 high--;
29             }
30             A[low] = A[high];
31             while (low<high && A[low]<=key) {
32                 low++;
33             }
34             A[high] = A[low];
35         }
36         A[low] = key;
37         return low;
38     }
39 };
40 
41 int main(){
42     int arr[] = {54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28};
43     QuickSort a;
44     a.quickSort(arr, 13);
45     for(int i=0; i<13; i++)
46         cout << arr[i] << " ";
47     cout << endl;
48     return 0;
49 }

View Code

PAT1101 题解

但是最后好像发现这道题不是考察快速排序，汗！

c++ sort 排序的时间复杂度为O(NlogN)

我需要找到一个数它的左边数都小于它，右边都大于它

维护两个数组，时间复杂度是O(N)

 1 /*
 2  快速排序Quit Sort
 3  pivot  枢轴
 4  */
 5 #include <iostream>
 6 #include <cstring>
 7 #include <string>
 8 #include <algorithm>
 9 
10 using namespace std;
11 
12 const int maxn = 100000+5;
13 int n;
14 int a[maxn], b[maxn];
15 int ans[maxn];
16 int left_max[maxn], right_min[maxn];
17 
18 int main(){
19     // freopen("test.txt", "r", stdin);
20     cin >> n;
21     for(int i=1; i<=n; i++){
22         cin >> a[i];
23         b[i] = a[i];
24     }
25     left_max[0] = a[1];
26     for(int i=1; i<=n; i++){
27         left_max[i] = max(left_max[i-1], a[i]);
28     }
29     right_min[n+1] = a[n];
30     for(int i=n; i>0; i--){
31         right_min[i] = min(right_min[i+1], a[i]);
32     }
33 //    for(int i=1; i<=n; i++){
34 //        cout << left_max[i] << " ";
35 //    }
36 //    cout << endl;
37 //    for(int i=1; i<=n; i++){
38 //        cout << right_min[i] << " ";
39 //    }
40 //    cout << endl;
41     
42     int index=0;
43     for(int i=1; i<=n; i++){
44         if(a[i]>=left_max[i] && a[i]<=right_min[i]){
45             ans[index++] = a[i];
46         }
47     }
48     
49     if(index == 0){
50         cout << index << endl;
51         cout << endl;
52     }else{
53         cout << index << endl;
54         for(int i=0; i<index; i++){
55             if(i != 0)
56                 cout << " ";
57             cout << ans[i];
58         }
59     }
60     return 0;
61 }

View Code