題目

代碼

第二次改進
一個超時，一個錯誤

#include<iostream> #include<vector> #include<algorithm> using namespace std;struct Arr {long int value;bool flag = true; };int mySort(Arr a1, Arr a2) {return(a1.value < a2.value); }int main() {Arr a[100001];int total;cin >> total;//輸入int i;long int val;for (i = 0; i < total; i++){scanf("%ld",&val);a[i].value = val;}//遍歷改flagint j;int count = total;for (i = 0; i < total; i++){if (a[i].flag == true){for (j = i; j < total; j++){if (a[j].flag == true){if (a[i].value > a[j].value){if (a[i].flag == true){a[i].flag = false;count--;}if (a[j].flag == true){a[j].flag = false;count--;}}}}}}//直接在原來的數組排序sort(a, a + total - 1, mySort);cout << count << endl;for (i = 0; i < total; i++){if (a[i].flag == true){cout << a[i].value;count--;if (count != 0){cout << ' ';}}}cout << endl;//system("pause");return 0; }

暴力查找，超時

#include<iostream> #include<vector> #include<algorithm> using namespace std;int main() {long int a[100000];int total;cin >> total;//輸入int i;for (i = 0; i < total; i++){cin >> a[i];}//查找主元int before, after;vector<long int>center;for (i = 0; i < total; i++)//判斷第i個元素是否主元{//左邊小for (before = 0; before < i; before++){if (a[before] > a[i]){break;}}//右邊大for (after = i; after < total; after++){if (a[after] < a[i]){break;}}//如果能走完兩個循環，說明是主元if (before == i && after == total){center.push_back(a[i]);}}//排序輸出sort(center.begin(), center.end());int size = center.size();cout << size << endl;for (i = 0; i < size; i++){cout << center[i];if (i != size - 1)cout << ' ';}cout << endl;system("pause");return 0; }

第一次改進

#include<iostream> #include<vector> #include<algorithm> using namespace std;struct Arr {long int value;bool flag = true; };int mySort(Arr a1, Arr a2) {return(a1.value < a2.value); }int main() {Arr a[100000];int total;cin >> total;//輸入int i;long int val;for (i = 0; i < total; i++){cin >> val;a[i].value = val;}//遍歷改flagint j;for (i = 0; i < total; i++){if (a[i].flag == true){for (j = i; j < total; j++){if (a[j].flag == true){if (a[i].value > a[j].value){a[i].flag = false;a[j].flag = false;}}}}}//直接在原來的數組排序sort(a, a + total, mySort);//輸出int count = 0;for (i = 0; i < total; i++){if (a[i].flag == true){count++;}}cout << count << endl;for (i = 0; i < total; i++){if (a[i].flag == true){cout << a[i].value;count--;if (count != 0){cout << ' ';}}}cout << endl;//system("pause");return 0; }

總結

以上是生活随笔為你收集整理的PAT1045 快速排序 （25 分）【4/6通过】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。