在C++中實現合併排序

Question

我研究了合併排序的理論，但對如何在C++中實現它沒有任何概念。我的問題是，合併排序在遞歸中創建數組。但是在實現時，我們如何在運行時創建數組？或者什麼是這個一般的方法？

謝謝。

Answer 1

基於這裏的代碼：http://cplusplus.happycodings.com/algorithms/code17.html

// Merge Sort 

#include <iostream> 
using namespace std; 

int a[50]; 
void merge(int,int,int); 
void merge_sort(int low,int high) 
{ 
int mid; 
if(low<high) 
{ 
    mid = low + (high-low)/2; //This avoids overflow when low, high are too large 
    merge_sort(low,mid); 
    merge_sort(mid+1,high); 
    merge(low,mid,high); 
} 
} 
void merge(int low,int mid,int high) 
{ 
int h,i,j,b[50],k; 
h=low; 
i=low; 
j=mid+1; 

while((h<=mid)&&(j<=high)) 
{ 
    if(a[h]<=a[j]) 
    { 
    b[i]=a[h]; 
    h++; 
    } 
    else 
    { 
    b[i]=a[j]; 
    j++; 
    } 
    i++; 
} 
if(h>mid) 
{ 
    for(k=j;k<=high;k++) 
    { 
    b[i]=a[k]; 
    i++; 
    } 
} 
else 
{ 
    for(k=h;k<=mid;k++) 
    { 
    b[i]=a[k]; 
    i++; 
    } 
} 
for(k=low;k<=high;k++) a[k]=b[k]; 
} 
int main() 
{ 
int num,i; 

cout<<"******************************************************************* 
*************"<<endl; 
cout<<"        MERGE SORT PROGRAM 
"<<endl; 

cout<<"******************************************************************* 
*************"<<endl; 
cout<<endl<<endl; 
cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN 
PRESS 
ENTER]:"<<endl; 
cin>>num; 
cout<<endl; 
cout<<"Now, Please Enter the ("<< num <<") numbers (ELEMENTS) [THEN 
PRESS ENTER]:"<<endl; 
for(i=1;i<=num;i++) 
{ 
    cin>>a[i] ; 
} 
merge_sort(1,num); 
cout<<endl; 
cout<<"So, the sorted list (using MERGE SORT) will be :"<<endl; 
cout<<endl<<endl; 

for(i=1;i<=num;i++) 
cout<<a[i]<<" "; 

cout<<endl<<endl<<endl<<endl; 
return 1; 

} 

Answer 2

要回答這個問題：在運行時創建動態大小的數組使用std::vector<T>完成。理想情況下，您可以使用其中一種方式獲得輸入。如果不是，則很容易將其轉換。例如，您可以創建兩個數組是這樣的：

template <typename T> 
void merge_sort(std::vector<T>& array) { 
    if (1 < array.size()) { 
     std::vector<T> array1(array.begin(), array.begin() + array.size()/2); 
     merge_sort(array1); 
     std::vector<T> array2(array.begin() + array.size()/2, array.end()); 
     merge_sort(array2); 
     merge(array, array1, array2); 
    } 
} 

然而，分配動態數組是比較慢的，一般應儘量避免。對於合併排序，您可以對原始數組的子序列進行排序並就地合併它們。看來，std::inplace_merge()要求雙向迭代器。

Answer 3

我已經重新安排了選定的答案，用於數組的指針和用於數量計數的用戶輸入沒有預先定義。

#include <iostream> 

using namespace std; 

void merge(int*, int*, int, int, int); 

void mergesort(int *a, int*b, int start, int end) { 
    int halfpoint; 
    if (start < end) { 
    halfpoint = (start + end)/2; 
    mergesort(a, b, start, halfpoint); 
    mergesort(a, b, halfpoint + 1, end); 
    merge(a, b, start, halfpoint, end); 
    } 
} 

void merge(int *a, int *b, int start, int halfpoint, int end) { 
    int h, i, j, k; 
    h = start; 
    i = start; 
    j = halfpoint + 1; 

    while ((h <= halfpoint) && (j <= end)) { 
    if (a[h] <= a[j]) { 
     b[i] = a[h]; 
     h++; 
    } else { 
     b[i] = a[j]; 
     j++; 
    } 
    i++; 
    } 
    if (h > halfpoint) { 
    for (k = j; k <= end; k++) { 
     b[i] = a[k]; 
     i++; 
    } 
    } else { 
    for (k = h; k <= halfpoint; k++) { 
     b[i] = a[k]; 
     i++; 
    } 
    } 

    // Write the final sorted array to our original one 
    for (k = start; k <= end; k++) { 
    a[k] = b[k]; 
    } 
} 

int main(int argc, char** argv) { 
    int num; 
    cout << "How many numbers do you want to sort: "; 
    cin >> num; 
    int a[num]; 
    int b[num]; 
    for (int i = 0; i < num; i++) { 
    cout << (i + 1) << ": "; 
    cin >> a[i]; 
    } 

    // Start merge sort 
    mergesort(a, b, 0, num - 1); 

    // Print the sorted array 
    cout << endl; 
    for (int i = 0; i < num; i++) { 
    cout << a[i] << " "; 
    } 
    cout << endl; 

    return 0; 
} 

Answer 4

我知道這個問題已經回答了，但我決定加我兩分錢。這裏是合併排序的代碼，它只在合併操作中使用額外的空間（並且額外的空間是當堆棧彈出時將被銷燬的臨時空間）。實際上，您將在此代碼中看到沒有使用堆操作（任何地方都沒有聲明new）。

希望這會有所幫助。

void merge(int *arr, int size1, int size2) { 
     int temp[size1+size2]; 
     int ptr1=0, ptr2=0; 
     int *arr1 = arr, *arr2 = arr+size1; 

     while (ptr1+ptr2 < size1+size2) { 
      if (ptr1 < size1 && arr1[ptr1] <= arr2[ptr2] || ptr1 < size1 && ptr2 >= size2) 
       temp[ptr1+ptr2] = arr1[ptr1++]; 

      if (ptr2 < size2 && arr2[ptr2] < arr1[ptr1] || ptr2 < size2 && ptr1 >= size1) 
       temp[ptr1+ptr2] = arr2[ptr2++]; 
     } 

     for (int i=0; i < size1+size2; i++) 
      arr[i] = temp[i]; 
    } 

    void mergeSort(int *arr, int size) { 
     if (size == 1) 
      return; 

     int size1 = size/2, size2 = size-size1; 
     mergeSort(arr, size1); 
     mergeSort(arr+size1, size2); 
     merge(arr, size1, size2); 
    } 

    int main(int argc, char** argv) { 
     int num; 
     cout << "How many numbers do you want to sort: "; 
     cin >> num; 
     int a[num]; 
     for (int i = 0; i < num; i++) { 
      cout << (i + 1) << ": "; 
      cin >> a[i]; 
     } 

     // Start merge sort 
     mergeSort(a, num); 

     // Print the sorted array 
     cout << endl; 
     for (int i = 0; i < num; i++) { 
      cout << a[i] << " "; 
     } 
     cout << endl; 

     return 0; 
    } 

Answer 5

#include <iostream> 
using namespace std; 

template <class T> 
void merge_sort(T array[],int beg, int end){ 
    if (beg==end){ 
     return; 
    } 
    int mid = (beg+end)/2; 
    merge_sort(array,beg,mid); 
    merge_sort(array,mid+1,end); 
    int i=beg,j=mid+1; 
    int l=end-beg+1; 
    T *temp = new T [l]; 
    for (int k=0;k<l;k++){ 
     if (j>end || (i<=mid && array[i]<array[j])){ 
      temp[k]=array[i]; 
      i++; 
     } 
     else{ 
      temp[k]=array[j]; 
      j++; 
     } 
    } 
    for (int k=0,i=beg;k<l;k++,i++){ 
     array[i]=temp[k]; 
    } 
    delete temp; 
} 

int main() { 
    float array[] = {1000.5,1.2,3.4,2,9,4,3,2.3,0,-5}; 
    int l = sizeof(array)/sizeof(array[0]); 
    merge_sort(array,0,l-1); 
    cout << "Result:\n"; 
    for (int k=0;k<l;k++){ 
     cout << array[k] << endl; 
    } 
    return 0; 
} 

Answer 6

下面就來實現它，只使用陣列的方式。

#include <iostream> 
using namespace std; 

//The merge function 
void merge(int a[], int startIndex, int endIndex) 
{ 

int size = (endIndex - startIndex) + 1; 
int *b = new int [size](); 

int i = startIndex; 
int mid = (startIndex + endIndex)/2; 
int k = 0; 
int j = mid + 1; 

while (k < size) 
{ 
    if((i<=mid) && (a[i] < a[j])) 
    { 
     b[k++] = a[i++]; 
    } 
    else 
    { 
     b[k++] = a[j++]; 
    } 

} 

for(k=0; k < size; k++) 
{ 
    a[startIndex+k] = b[k]; 
} 

delete []b; 

} 

//The recursive merge sort function 
void merge_sort(int iArray[], int startIndex, int endIndex) 
{ 
int midIndex; 

//Check for base case 
if (startIndex >= endIndex) 
{ 
    return; 
} 

//First, divide in half 
midIndex = (startIndex + endIndex)/2; 

//First recursive call 
merge_sort(iArray, startIndex, midIndex); 

//Second recursive call 
merge_sort(iArray, midIndex+1, endIndex); 

merge(iArray, startIndex, endIndex); 

} 



//The main function 
int main(int argc, char *argv[]) 
{ 
int iArray[10] = {2,5,6,4,7,2,8,3,9,10}; 

merge_sort(iArray, 0, 9); 

//Print the sorted array 
for(int i=0; i < 10; i++) 
{ 
    cout << iArray[i] << endl; 
} 

return 0;  
} 

Answer 7

我已完成@DietmarKühl的合併排序方式。希望它能幫助所有人。

template <typename T> 
void merge(vector<T>& array, vector<T>& array1, vector<T>& array2) { 
    array.clear(); 

    int i, j, k; 
    for(i = 0, j = 0, k = 0; i < array1.size() && j < array2.size(); k++){ 
     if(array1.at(i) <= array2.at(j)){ 
      array.push_back(array1.at(i)); 
      i++; 
     }else if(array1.at(i) > array2.at(j)){ 
      array.push_back(array2.at(j)); 
      j++; 
     } 
     k++; 
    } 

    while(i < array1.size()){ 
     array.push_back(array1.at(i)); 
     i++; 
    } 

    while(j < array2.size()){ 
     array.push_back(array2.at(j)); 
     j++; 
    } 
} 

template <typename T> 
void merge_sort(std::vector<T>& array) { 
    if (1 < array.size()) { 
     std::vector<T> array1(array.begin(), array.begin() + array.size()/2); 
     merge_sort(array1); 
     std::vector<T> array2(array.begin() + array.size()/2, array.end()); 
     merge_sort(array2); 
     merge(array, array1, array2); 
    } 
} 

Answer 8

這將是很容易理解：

#include <iostream> 

using namespace std; 

void Merge(int *a, int *L, int *R, int p, int q) 
{ 
    int i, j=0, k=0; 
    for(i=0; i<p+q; i++) 
    { 
     if(j==p)      //When array L is empty 
     { 
      *(a+i) = *(R+k); 
      k++; 
     } 
     else if(k==q)     //When array R is empty 
     { 
      *(a+i) = *(L+j); 
      j++; 
     } 
     else if(*(L+j) < *(R+k)) //When element in L is smaller than element in R 
     { 
      *(a+i) = *(L+j); 
      j++; 
     } 
     else //When element in R is smaller or equal to element in L 
     { 
      *(a+i) = *(R+k); 
      k++; 
     } 
    } 
} 

void MergeSort(int *a, int len) 
{ 
    int i, j; 
    if(len > 1) 
    { 
     int p = len/2 + len%2;  //length of first array 
     int q = len/2;    //length of second array 
     int L[p];     //first array 
     int R[q];     //second array 
     for(i=0; i<p; i++) 
     { 
      L[i] = *(a+i);  //inserting elements in first array 
     } 
     for(i=0; i<q; i++) 
     { 
      R[i] = *(a+p+i); //inserting elements in second array 
     } 
     MergeSort(&L[0], p); 
     MergeSort(&R[0], q); 
     Merge(a, &L[0], &R[0], p, q); //Merge arrays L and R into A 
    } 
    else 
    { 
     return;  //if array only have one element just return 
    } 
} 

int main() 
{ 
    int i, n; 
    int a[100000]; 
    cout<<"Enter numbers to sort. When you are done, enter -1\n"; 
    i=0; 
    while(true) 
    { 
     cin>>n; 
     if(n==-1) 
     { 
      break; 
     } 
     else 
     { 
      a[i] = n; 
      i++; 
     } 
    } 
    int len = i; 
    MergeSort(&a[0], len); 
    for(i=0; i<len; i++) 
    { 
     cout<<a[i]<<" "; 
    } 

    return 0; 
} 

Answer 9

與歸併排序的問題是合併，如果你實際上並不需要實現合併，那麼它是非常簡單的（對於整數的矢量）：

#include <algorithm> 
#include <vector> 
using namespace std; 

typedef vector<int>::iterator iter; 

void mergesort(iter b, iter e) { 
    if (e -b > 1) { 
     iter m = b + (e -b)/2; 
     mergesort(b, m); 
     mergesort(m, e); 
     inplace_merge(b, m, e); 
    } 
}