일반적인 정렬 알고리즘 2 (병렬 정렬)
16119 단어 정렬 알고리즘
병합 정렬
수조를 좌우 두 부분으로 나누어 좌우 부분을 각각 순서(귀속 코드sortProcess 함수 참조)로 배열하여 보조 수조를 만들고 좌우 양쪽에 순서를 배열한 하위 수조를 크기에 따라 보조 수조에 넣고 보조 수조를 원 수조로 복사한다.코드 참조 merge 함수
#include
#include
using namespace std;
class Solution {
public:
//
/*
* 1. ,
* 2. ,
* 3.
* */
void merge(vector<int>& example, int left, int mid, int right) {
vector<int> tmp;
int p1 = left, p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
if (example[p1] < example[p2]) {
tmp.push_back(example[p1]);
p1++;
} else {
tmp.push_back(example[p2]);
p2++;
}
}
while (p1 <= mid) {
for (int i = p1; i <= mid; i++) {
tmp.push_back(example[i]);
p1++;
}
}
while (p2 <= right) {
for (int i = p2; i <= right; i++) {
tmp.push_back(example[i]);
p2++;
}
}
for (int i = 0; i < tmp.size(); i++) {
example[left+i] = tmp[i];
}
}
void sortProcess(vector<int>& example, int left, int right) {
if (left == right) {
return;
}
int mid = left + ((right - left) >> 1);
sortProcess(example, left, mid);
sortProcess(example, mid + 1, right);
merge(example, left, mid, right);
}
void mergeSort(vector<int>& example) {
if (example.empty() || example.size() == 1) {
return;
}
sortProcess(example, 0, example.size() - 1);
}
};
int main()
{
vector<int> example = {1, 12, 9, 3, 6};
cout << " : ";
for (int i = 0; i < example.size() - 1; i++) {
cout << example[i] << ", ";
}
cout << example[example.size()-1] << endl;
cout << "----------------------------" << endl;
Solution su;
su.mergeSort(example);
cout << " : ";
for (int i = 0; i < example.size() - 1; i++) {
cout << example[i] << ", ";
}
cout << example[example.size()-1] << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
WEEK. 01 2022.04.03 TIL정렬(sorting)이란 이름, 학번, 학점 등의 키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 의미함. 정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.