p*****2
发帖数: 21240 | 1 我写了一个，有什么问题吗？
static void Merge(int[] arr, int start, int mid, int end)
{
int[] tmp = new int[arr.Length];
Array.Copy(arr, start, tmp, start, end - start + 1);
int left = start;
int right = mid + 1;
int current = start;
while (left <= mid)
{
if (right>end || tmp[left] <= tmp[right])
arr[current++] = tmp[left++];
else
arr[current++] = tmp[right++];
}
} | l*****a
发帖数: 14598 | 2 第一个问题是为什么要传mid
函数里自己算不好吗？
【在 p*****2 的大作中提到】
: 我写了一个，有什么问题吗？
: static void Merge(int[] arr, int start, int mid, int end)
: {
: int[] tmp = new int[arr.Length];
: Array.Copy(arr, start, tmp, start, end - start + 1);
: int left = start;
: int right = mid + 1;
: int current = start;
: while (left <= mid)
: {
| q****x
发帖数: 7404 | 3 没看懂。
【在 p*****2 的大作中提到】
: 我写了一个，有什么问题吗？
: static void Merge(int[] arr, int start, int mid, int end)
: {
: int[] tmp = new int[arr.Length];
: Array.Copy(arr, start, tmp, start, end - start + 1);
: int left = start;
: int right = mid + 1;
: int current = start;
: while (left <= mid)
: {
| p*****2
发帖数: 21240 | 4 这是全部的代码
static void MergeSort(int[] arr)
{
if (arr == null || arr.Length == 1)
return;
Sort(arr, 0, arr.Length - 1);
}
static void Sort(int[] arr, int start, int end)
{
if (start >= end)
return;
int mid = (start + end) / 2;
Sort(arr, start, mid);
Sort(arr, mid + 1, end);
Merge(arr, start,end);
}
static void Merge(int[] arr, int start,int end)
{
int[] tmp = new int[arr.Length];
Array.Copy(arr, start, tmp, start, end - start + 1);
int mid = (start + end) / 2;
int left = start;
int right = mid + 1;
int current = start;
while (left <= mid)
{
if (right>end || tmp[left] <= tmp[right])
arr[current++] = tmp[left++];
else
arr[current++] = tmp[right++];
}
} | p*****2
发帖数: 21240 | 5 mid 的确可以自己算。我试试。
【在 l*****a 的大作中提到】
: 第一个问题是为什么要传mid
: 函数里自己算不好吗？
| p*****2
发帖数: 21240 | 6
可以。看来interview exposed和careercup上的sample code还是有很多可以改进的地
方呀。
【在 l*****a 的大作中提到】
: 第一个问题是为什么要传mid
: 函数里自己算不好吗？
| q****x
发帖数: 7404 | 7 我不看他们的代码，只看思路。
【在 p*****2 的大作中提到】
:
: 可以。看来interview exposed和careercup上的sample code还是有很多可以改进的地
: 方呀。
| p*****2
发帖数: 21240 | 8
你是大牛当然不一样了。啥时候也出本书吧，保证比那两本卖得好。
【在 q****x 的大作中提到】
: 我不看他们的代码，只看思路。
| l*****a
发帖数: 14598 | 9 arr.length<=1 是不是更好？
merge这个函数还是用5个参数好点，比较直接（这里跟那个mid不一样）
merge( int[],int start1,int end1,int start2,int end2)
【在 p*****2 的大作中提到】
: 这是全部的代码
: static void MergeSort(int[] arr)
: {
: if (arr == null || arr.Length == 1)
: return;
: Sort(arr, 0, arr.Length - 1);
: }
: static void Sort(int[] arr, int start, int end)
: {
: if (start >= end)
| p*****2
发帖数: 21240 | 10 嗯。是应该<=1。merge标准是5个参数吗？书上是4个。
【在 l*****a 的大作中提到】
: arr.length<=1 是不是更好？
: merge这个函数还是用5个参数好点，比较直接（这里跟那个mid不一样）
: merge( int[],int start1,int end1,int start2,int end2)
| | | r****t
发帖数: 10904 | | l*****a
发帖数: 14598 | 12 不递归咋玩？
【在 r****t 的大作中提到】
: 不该递归吧
| r****t
发帖数: 10904 | | i**********e
发帖数: 1145 | 14 merge sort 是要递归的。
那个代码有个隐含条件，数组的大小必须是 2 的平方。
那个应该不叫merge sort吧，看上去像是 O(n^2) 的算法。
【在 r****t 的大作中提到】
: http://www.algorithmist.com/index.php/Merge_sort.c
| r****t
发帖数: 10904 | 15 这网页我随手 google 的，sort 部分写的不好。
工业界实用的 merge sort 应该没有递归实现的，复杂度同样是 O(nlogn)
【在 i**********e 的大作中提到】
: merge sort 是要递归的。
: 那个代码有个隐含条件，数组的大小必须是 2 的平方。
: 那个应该不叫merge sort吧，看上去像是 O(n^2) 的算法。
|
|
