- #pragma once
- #include <vector>
- #include<stdlib.h>
- #include<iostream>
- using namespace std;
- template<typename T>
- class MergeSort
- {
- public:
- MergeSort(){}
- void mergeSortList(vector<T> & dataList)
- {
- mergeSort(dataList, 0, dataList.size() - 1);
- printf("\\n\\n");
- }//end function
- void mergeSort(vector<T> & dataList, int p, int r)
- {
- if (p < r)
- {
- int q = (p + r) / 2;
- mergeSort(dataList, p, q);
- mergeSort(dataList, q + 1, r);
- merge(dataList, p, q, r);
- }//end if
- }//end function
- void merge(vector<T> & dataList, int p, int q, int r)
- {
- int n1 = q - p + 1;
- int n2 = r - q;
- int i, j;
- vector<T> leftList(n1);
- vector<T> rightList(n2);
- for (i = 0; i < n1; i++)
- leftList.at(i) = dataList.at(p + i);
- for (j = 0; j < n2; j++)
- rightList.at(j) = dataList.at(q + 1 + j);
- i = 0;
- j = 0;
- //Need to loop till r because r IS THE INDEX!!!
- for (int k = p; k <= r; k++)
- {
- if (i == n1)
- {
- dataList.at(k) = rightList.at(j);
- cout << " Copying rest: " << rightList.at(j);
- j = j + 1;
- }//copy the remaining from the left list.
- else if (j == n2)
- {
- dataList.at(k) = leftList.at(i);
- cout << " Copying rest: " << leftList.at(i);
- i = i + 1;
- }//copy the remaining from the right list.
- else
- {
- if (leftList.at(i) <= rightList.at(j))
- {
- dataList.at(k) = leftList.at(i);
- cout << "\\nNumber left: " << leftList.at(i);
- i = i + 1;
- }//end if: copy value from left array to final array.
- else
- {
- dataList.at(k) = rightList.at(j);
- cout << "\\nNumber right: " << rightList.at(j);
- j = j + 1;
- }//end if: copy value from right array to final array.
- }//end else
- }//end loop
- }//end function
- ~MergeSort(){}//end cons
- };//end class
- //该片段来自于http://www.codesnippet.cn/detail/1507201614860.html
来源: http://www.codesnippet.cn/detail/1507201614860.html