17

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

谢谢。

4

10 回答 10

28

要回答这个问题：在运行时创建动态大小的数组是使用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()要求双向迭代器。

于 2012-08-19T23:39:06.087 回答
16

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

}
于 2012-08-19T23:12:20.123 回答
9

我已经完成了@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);
    }
}
于 2014-09-17T06:17:25.633 回答
7

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

#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;
}
于 2013-03-12T14:58:24.147 回答
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;
}
于 2013-10-29T22:27:22.767 回答
5

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

#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);
    }
}
于 2017-03-17T06:38:52.053 回答
2

我知道这个问题已经得到解答，但我决定加两分钱。这是合并排序的代码，它只在合并操作中使用额外的空间（并且额外的空间是临时空间，在弹出堆栈时将被销毁）。事实上，您会在这段代码中看到没有使用堆操作（没有在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;
    }
于 2013-03-16T16:43:35.023 回答
2

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

#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;    
}
于 2014-05-02T22:42:35.650 回答
0

这很容易理解：

#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;
}
于 2015-04-09T21:55:54.603 回答
0

这是我的版本（简单易行）：
使用的内存仅为原始数组大小的 两倍。
[ 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);
}
于 2019-12-11T16:33:08.500 回答