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) 的算法。
|
|