일반적인 정렬 알고리즘 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;
}

좋은 웹페이지 즐겨찾기