C++实现归并排序

implementing merge sort in C++

提问by Maduranga E

I have studied the theory of the merge sort but don't have any idea of how to implement it in C++. My question is, merge sort creates arrays in recursion. But when implementing, how do we create arrays in runtime? or what is the general approach for this?

我研究了归并排序的理论，但不知道如何在 C++ 中实现它。我的问题是，合并排序以递归方式创建数组。但是在实现的时候，我们如何在运行时创建数组呢？或者对此的一般方法是什么？

Thanks.

谢谢。

采纳答案by klm123

Based on the code here: http://cplusplus.happycodings.com/algorithms/code17.html

基于这里的代码：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;

}

回答by Dietmar Kühl

To answer the question: Creating dynamically sized arrays at run-time is done using std::vector<T>. Ideally, you'd get your input using one of these. If not, it is easy to convert them. For example, you could create two arrays like this:

回答这个问题：在运行时创建动态大小的数组是使用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);
    }
}

However, allocating dynamic arrays is relatively slow and generally should be avoided when possible. For merge sort you can just sort subsequences of the original array and in-place merge them. It seems, std::inplace_merge()asks for bidirectional iterators.

但是，分配动态数组相对较慢，通常应尽可能避免。对于合并排序，您可以对原始数组的子序列进行排序并就地合并它们。看来，std::inplace_merge()要求双向迭代器。

回答by Sazzad Hissain Khan

I have completed @DietmarKühl s way of merge sort. Hope it helps all.

我已经完成了@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);
    }
}

回答by emrahgunduz

I've rearranged the selected answer, used pointers for arrays and user input for number count is not pre-defined.

我重新排列了选定的答案，用于数组的指针和用于数字计数的用户输入不是预定义的。

#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;
}

回答by Jo?o Abrantes

#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;
}

回答by Mac

The problem with merge sort is the merge, if you don't actually need to implement the merge, then it is pretty simple (for a vector of ints):

合并排序的问题在于合并，如果您实际上不需要实现合并，那么它非常简单（对于整数向量）：

#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);
    }
}

回答by KKP

Here's a way to implement it, using just arrays.

这是实现它的一种方法，仅使用数组。

#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;    
}

回答by Barry Steyn

I know this question has already been answered, but I decided to add my two cents. Here is code for a merge sort that only uses additional space in the merge operation (and that additional space is temporary space which will be destroyed when the stack is popped). In fact, you will see in this code that there is not usage of heap operations (no declaring newanywhere).

我知道这个问题已经得到了回答，但我决定加上我的两分钱。这是合并排序的代码，它只在合并操作中使用额外的空间（额外的空间是临时空间，当堆栈弹出时将被销毁）。事实上，你会在这段代码中看到没有使用堆操作（没有在new任何地方声明）。

Hope this helps.

希望这可以帮助。

    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;
    } 

回答by theCaveman

This would be easy to understand:

这很容易理解：

#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;
}

回答by Peyman Mahdavi

This is my version (simple and easy):
uses memory only twicethe size of original array.
[ a is the left array ] [ b is the right array ] [ c used to merge a and b ] [ p is counter for c ]

这是我的版本（简单易行）：
使用的内存仅为原始数组大小的两倍。
[a是左数组][b是右数组][c用于合并a和b][p是c的计数器]

void MergeSort(int list[], int size)
{
    int blockSize = 1, p;
    int *a, *b;
    int *c = new int[size];
    do
    {
        for (int k = 0; k < size; k += (blockSize * 2))
        {
            a = &list[k];
            b = &list[k + blockSize];
            p = 0;
            for (int i = 0, j = 0; i < blockSize || j < blockSize;)
            {
                if ((j < blockSize) && ((k + j + blockSize) >= size))
                {
                    ++j;
                }
                else if ((i < blockSize) && ((k + i) >= size))
                {
                    ++i;
                }
                else if (i >= blockSize)
                {
                    c[p++] = b[j++];
                }
                else if (j >= blockSize)
                {
                    c[p++] = a[i++];
                }
                else if (a[i] >= b[j])
                {
                    c[p++] = b[j++];
                }
                else if (a[i] < b[j])
                {
                    c[p++] = a[i++];
                }
            }
            for (int i = 0; i < p; i++)
            {
                a[i] = c[i];
            }
        }
        blockSize *= 2;
    } while (blockSize < size);
}