C++バブルソート、高速ソート、集計ソートを実現
18605 ワード
1.泡立ちソート
2.クイックソート
3.集計ソート
4.試験用例
#include <ioatream>
#include <vector>
#include <algorithm>
void bubbleSort(std::vector<int> &vec)
{
for (size_t i = 0;i+1 < vec.size();++i) {
for (size_t j = 0;j + i + 1 < vec.size();++j) {
if(vec[j]> vec[j + 1])
std::swap(vec[j], vec[j + 1]);
}
}
}
2.クイックソート
void quickSort(std::vector<int> &vec, int left, int right)
{
if (left >= right)
return;
int value = vec[left];
int l = left, r = right, mid = left;
while (l < r) {
if (mid == l) {
if (vec[r] < value) {
vec[mid] = vec[r];
++l;
mid = r;
}
else
--r;
}
else {
if (vec[l] > value) {
vec[mid] = vec[l];
--r;
mid = l;
}
else
++l;
}
}
vec[mid] = value;
quickSort(vec, left, mid - 1);
quickSort(vec, mid + 1, right);
}
3.集計ソート
void guibingmerge(std::vector<int>& ans, int left, int mid, int right)
{
int cntLeft = left;
int cntRight = mid+1;
int cntMerge = left;
std::vector<int> vec(ans);
while (cntLeft<mid + 1 && cntRight<=right) {
ans[cntMerge++] = (vec[cntLeft] < vec[cntRight]) ? vec[cntLeft++] : vec[cntRight++];
}
while (cntLeft < mid + 1 && cntRight == right+1)
ans[cntMerge++] = vec[cntLeft++];
while (cntRight <= right&&cntLeft == mid + 1)
ans[cntMerge++] = vec[cntRight++];
}
void guibingsort(std::vector<int> &vec, int left, int right)
{
if (left >= right)
return;
int mid = (left + right) / 2;
guibingsort(vec, left, mid);
guibingsort(vec, mid + 1, right);
guibingmerge(vec, left, mid, right);
}
4.試験用例
int main()
{
std::vector<int> vec{ 9, 7, 5, 3, 1, 2, 4, 6, 8, 10, 2, 5, 7, 1 };
for (auto v : vec)
std::cout << v << " ";
std :: cout << std::endl;
//bubbleSort(vec);
//quickSort(vec, 0, vec.size() - 1);
guibingsort(vec, 0, vec.size() - 1);
for (auto v : vec)
std::cout << v << " ";
std::cout << std::endl;
return 0;
}