C#中的MergeSort算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15835805/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
MergeSort algorithm in c#
提问by Hamed Kamrava
I wrote below code for Merge Class :
我为 Merge Class 编写了以下代码：
class Merge
{
public static void sort(IComparable[] a)
{
sort(a, 0, a.Length);
}
public static void sort(IComparable[] a, int low, int high)
{
int N = high - low;
if (N <= 1)
return;
int mid = low + N / 2;
sort(a, low, mid);
sort(a, mid, high);
IComparable[] aux = new IComparable[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid) aux[k] = a[j++];
else if (j == high) aux[k] = a[i++];
else if (a[j].CompareTo(a[i]) < 0) aux[k] = a[j++];
else aux[k] = a[i++];
}
for (int k = 0; k < N; k++)
{
a[low + k] = aux[k];
}
}
private static Boolean isSorted(IComparable[] a)
{
for (int i = 1; i < a.Length; i++)
if (a[i].CompareTo(a[i - 1]) < 0) return false;
return true;
}
}
And below code is Implementation. i thought below code should't be wrong! but it's does't compile...
下面的代码是实现。我认为下面的代码应该不会错！但它不编译...
class Program
{
static void Main(string[] args)
{
Merge ms = new Merge();
Double[] MyArray = { 80,10,52,7,36,7,67,1,8,54 };
Console.WriteLine("first array is: \n");
for (int k = 0; k < MyArray.Length; k++)
{
Console.Write(MyArray[k]);
if (k<9)
Console.Write(" , ");
}
ms.sort(MyArray); // Error is here. Does't compile !!!
Console.WriteLine("\n");
Console.WriteLine("\nsorted array is: \n ");
for (int k = 0; k < MyArray.Length; k++)
{
Console.Write(MyArray[k]);
if (k<9)
Console.Write(" , ");
}
Console.ReadLine();
}
}
It's does't compile. Error is in ms.sort(MyArray);.
What am i doing wrong?
Please lead me...
它不编译。错误在ms.sort(MyArray);. 我究竟做错了什么？请带领我...
Regards
问候
采纳答案by Lasse V. Karlsen
There are two problems with this code:
这段代码有两个问题：
- The signature doesn't match,
IComparable[]is not directly compatible withdouble[]in this case - You cannot call the
sortmethod through the instance directly
- 签名不匹配，在这种情况下
IComparable[]不直接兼容double[] - 不能
sort直接通过实例调用方法
The minimal amount of changes to fix this would be to make the method generic, and call Merge.sortinstead of ms.sort.
解决此问题的最少量更改是使方法通用，并调用Merge.sort而不是ms.sort.
Here's how I would implement sort:
这是我将如何实施sort：
public static void sort<T>(T[] a)
where T : IComparable<T>
{
sort(a, 0, a.Length);
}
public static void sort<T>(T[] a, int low, int high)
where T : IComparable<T>
{
int N = high - low;
if (N <= 1)
return;
int mid = low + N / 2;
sort(a, low, mid);
sort(a, mid, high);
T[] aux = new T[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid) aux[k] = a[j++];
else if (j == high) aux[k] = a[i++];
else if (a[j].CompareTo(a[i]) < 0) aux[k] = a[j++];
else aux[k] = a[i++];
}
for (int k = 0; k < N; k++)
{
a[low + k] = aux[k];
}
}
Note that I changed to using Tinstead of IComparable, and added a constraint saying we need a Tthat implements IComparable<T>.
请注意，我更改为 usingT而不是IComparable，并添加了一个约束，说明我们需要一个T实现IComparable<T>.
Additionally, change your call from this:
此外，从这里更改您的电话：
ms.sort(...);
to this:
对此：
Merge.sort(...);
回答by Matt Burland
Your sortmethod is static, you shouldn't call it from an instance of your class.
你的sort方法是静态的，你不应该从你的类的实例中调用它。
You should call it like this:
你应该这样称呼它：
Merge.sort(MyArray);
not:
不是：
ms.sort(MyArray);
In fact, since you Mergeclass has no instance methods, there is no point creating an instance of it and you should probably just mark the whole class as static.
事实上，由于您的Merge类没有实例方法，因此创建它的实例没有意义，您可能应该将整个类标记为静态。
回答by Enigmatic Mind
//merge sort recurcive
public void MergeSort(int[] input,int startIndex,int endIndex)
{
int mid;
if (endIndex > startIndex)
{
mid = (endIndex + startIndex) / 2;
MergeSort(input, startIndex, mid);
MergeSort(input, (mid + 1), endIndex);
Merge(input, startIndex, (mid + 1), endIndex);
}
}
public void Merge(int[] input, int left, int mid, int right)
{
//Merge procedure takes theta(n) time
int[] temp = new int[input.Length];
int i, leftEnd,lengthOfInput,tmpPos;
leftEnd = mid - 1;
tmpPos = left;
lengthOfInput = right - left + 1;
//selecting smaller element from left sorted array or right sorted array and placing them in temp array.
while ((left <= leftEnd) && (mid <= right))
{
if (input[left] <= input[mid])
{
temp[tmpPos++] = input[left++];
}
else
{
temp[tmpPos++]=input[mid++];
}
}
//placing remaining element in temp from left sorted array
while (left <= leftEnd)
{
temp[tmpPos++] = input[left++];
}
//placing remaining element in temp from right sorted array
while (mid <= right)
{
temp[tmpPos++] = input[mid++];
}
//placing temp array to input
for (i = 0; i < lengthOfInput;i++ )
{
input[right]=temp[right];
right--;
}
}
int[] input3 = { 22, 4, 6, 0, 9, 12, 156, 86,99};
MergeSort(input3, 0, input3.Length - 1);
for (int i = 0; i < input3.Length; i++)
Console.Write(input3[i]+", ");
Console.WriteLine("");
回答by Lee.O.
public static int[] mergeSort(int[] ar)
{
Func<int[], int[]> firstHalf = (array) =>
{
return array.Take((array.Length + 1) / 2).ToArray();
};
Func<int[], int[]> secondHalf = (array) =>
{
return array.Skip((array.Length + 1) / 2).ToArray();
};
Func<int[], int[], int[]> mergeSortedArrays = (ar1, ar2) =>
{
int[] mergedArray = new int[ar1.Length + ar2.Length];
int i1 = 0, i2 = 0, currentMin;
while (i1 < ar1.Length || i2 < ar2.Length)
{
if (i1 < ar1.Length && i2 < ar2.Length)
{
if (ar1[i1] < ar2[i2])
{
currentMin = ar1[i1];
i1++;
}
else
{
currentMin = ar2[i2];
i2++;
}
}
else if (i1 < ar1.Length)
{
currentMin = ar1[i1];
i1++;
}
else
{
currentMin = ar2[i2];
i2++;
}
mergedArray[i1 + i2 - 1] = currentMin;
}
return mergedArray;
};
int[] half1 = firstHalf(ar); //always /geq than half2
int[] half2 = secondHalf(ar);
if (half1.Length < 2)
return mergeSortedArrays(half1, half2);
else
return mergeSortedArrays(mergeSort(half1), mergeSort(half2));
}
回答by Arun Kumar
A simple C# code to do merge sort
一个简单的 C# 代码来做归并排序
using System;
namespace MergeSort
{
class Program
{
static void Main(string[] args)
{
int[] arInt = { 6, 4, 2, 8, 4, 8, 11, 1, 7, 4, 13, 5, 45, -1, 0, -7, 56, 10, 57 };
var sortedIntAr = GenericMergeSort<int>.Sort(arInt);
string[] arStr = { "Here", "Is", "A", "Cat", "Really", "Fast", "And", "Clever" };
var sortedStrAr = GenericMergeSort<string>.Sort(arStr);
Console.WriteLine(String.Join(',', sortedIntAr));
Console.WriteLine(String.Join(',', sortedStrAr));
Console.ReadLine();
}
}
class GenericMergeSort<T> where T : IComparable
{
public static T[] Sort(T[] ar)
{
var arLen = ar.Length;
if (arLen < 2)
return ar;
var arL = ar.AsSpan(0..(arLen / 2)).ToArray();
var arR = ar.AsSpan((arLen / 2)..arLen).ToArray();
arL = Sort(arL);
arR = Sort(arR);
return Merge(arL, arR);
}
private static T[] Merge(T[] arL, T[] arR)
{
var mergedArray = new T[arL.Length + arR.Length];
int iM = 0, iL = 0, iR = 0;
while (iL < arL.Length || iR < arR.Length)
{
mergedArray[iM++] = iL < arL.Length && (iR > arR.Length - 1 || arL[iL].CompareTo(arR[iR]) < 0)
? arL[iL++] : arR[iR++];
}
return mergedArray;
}
}
}
Here is the output
这是输出
-7,-1,0,1,2,4,4,4,5,6,7,8,8,10,11,13,45,56,57
-7,-1,0,1,2,4,4,4,5,6,7,8,8,10,11,13,45,56,57
A,And,Cat,Clever,Fast,Here,Is,Really
A,和,猫,聪明,快,在这里,是,真的
