クイックバブル選択挿入集計ソートアルゴリズム
31577 ワード
きゅうそくれつ
泡が立つ
選択
挿入
まとめる
#include
using namespace std;
void quick_sort(vector<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], q[j]);
} else {
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
}
}
int main() {
int n, t;
cin >> n;
vector<int>q;
for(int i = 0; i < n; i ++) {
cin >> t;
q.push_back(t);
}
quick_sort(q, 0, q.size() - 1);
for(int x : q) cout << x << ' ';
cout << endl;
return 0;
}
泡が立つ
#include
using namespace std;
void bubble_sort(vector<int>&q) {
for(int i = q.size() - 1; i > 0; i --) {
bool isSwap = false;
for(int j = 1; j <= i; j ++) {
if(q[j - 1] > q[j]) {
isSwap = true;
swap(q[j - 1], q[j]);
}
if(!isSwap) break;
}
}
}
int main() {
int n, t;
cin >> n;
vector<int>q;
for(int i = 0; i < n; i ++) {
cin >> t;
q.push_back(t);
}
bubble_sort(q);
for(int x : q) cout << x << ' ';
cout << endl;
return 0;
}
選択
#include
using namespace std;
void select_sort(vector<int>&q) {
for(int i = 0; i < q.size(); i ++) {
for(int j = i + 1; j < q.size(); j ++) {
if(q[i] > q[j]) {
swap(q[i], q[j]);
}
}
}
}
int main() {
int n, t;
cin >> n;
vector<int>q;
for(int i = 0; i < n; i ++) {
cin >> t;
q.push_back(t);
}
select_sort(q);
for(int x : q) cout << x << ' ';
cout << endl;
return 0;
}
挿入
#include
using namespace std;
void insert_sort(vector<int>&q) {
for(int i = 1; i < q.size(); i ++) {
int t = q[i], j;
for(j = i - 1; j >= 0; j --) {
if(q[j] > t) {
q[j + 1] = q[j];
} else {
break;
}
}
q[j + 1] = t;
}
}
int main() {
int n, t;
cin >> n;
vector<int>q;
for(int i = 0; i < n; i ++) {
cin >> t;
q.push_back(t);
}
insert_sort(q);
for(int x : q) cout << x << ' ';
cout << endl;
return 0;
}
まとめる
#include
using namespace std;
void merge_sort(vector<int>&q, int l, int r) {
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
static vector<int>w;
w.clear();
int i = l, j = mid + 1;
while(i <= mid && j <= r) {
if(q[i] < q[j]) {
w.push_back(q[i ++]);
} else {
w.push_back(q[j ++]);
}
}
while(i <= mid) w.push_back(q[i ++]);
while(j <= r) w.push_back(q[j ++]);
for(int i = 0, j = l; i < w.size(); i ++) q[j ++] = w[i];
}
int main() {
int n, t;
cin >> n;
vector<int>q;
for(int i = 0; i < n; i ++) {
cin >> t;
q.push_back(t);
}
merge_sort(q, 0, q.size() - 1);
for(int x : q) cout << x << ' ';
cout << endl;
return 0;
}