[912] Sort an Array

拿來練習merge sort 但看起來迴圈太多？！ XD

先存一個超時的版本：

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

void swap(int *a, int *b)

{

int tmp;

tmp = *a;

*a=*b;

*b=tmp;

}

void merge(int* nums, int start,int mid, int end){

// printf(" merge %d %d %d\n", start,mid, end);

int i= start;

int j=mid+1;

int *ret = malloc (sizeof(int)* (end+1));

while (i<=mid){

if (nums[i]>nums[j])

{

swap(&nums[i],&nums[j]);

for(int z=j; z<end;z++)

{

if (nums[z] >nums[z+1])

swap(&nums[z],&nums[z+1]);

else

break;

}

}

i++;

}

#if 0

while(0)//(j<end)

{

if (nums[j]>nums[j+1])

swap(&nums[j],&nums[j+1]);

j++;

}

#endif

}

void mergeSort(int* nums, int start, int end){

// printf(" mergeSort %d %d\n", start, end);

if(start < end)

{

int mid = start + (end-start) /2;

mergeSort(nums,start, mid);

mergeSort(nums,mid+1, end);

merge(nums,start, mid,end);

}

}

int* sortArray(int* nums, int numsSize, int* returnSize){

mergeSort(nums,0,numsSize-1);

*returnSize=numsSize;

return nums;

}

然後改了一個版本，原先想用兩個array分別copy，但沒有很集中精神一直無法正確memcpy，為了方便就改成用一個新的array直接存left+right array，然後用兩個pointer 去比這個new Array，

依值的大小分別填回nums，讓它完成sorting。

沒想到最後卡住的地方是，我忘記新的array 的index 是從0 開始，所以它的start，mid，end 都要重算，這個改完以後就ok了 QQ 然後還從超過時間變成80% 這樣= =+

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

void swap(int *a, int *b)

{

int tmp;

tmp = *a;

*a=*b;

*b=tmp;

}

void merge(int* nums, int start,int mid, int end){

if (end-start==1)

{

if (nums[start]> nums[end])

swap(&nums[start], &nums[end]);

return;

}

int *tmpA = malloc (sizeof(int)*(end-start+1));

memcpy(tmpA, nums+start, sizeof(int)*(end-start+1));

int left=0;

int right=mid-start+1;

int newMid=mid-start;

int newEnd=end-start;

while (left<=newMid && right <=newEnd)

{

if (tmpA[left]<tmpA[right])

nums[start++]=tmpA[left++];

else if (tmpA[left] > tmpA[right])

nums[start++]=tmpA[right++];

else

{

nums[start++]=tmpA[left++];

nums[start++]=tmpA[right++];

}

}

while (left<=newMid)

nums[start++]=tmpA[left++];

while (right<=newEnd)

nums[start++]=tmpA[right++];

}

void mergeSort(int* nums, int start, int end){

if(start < end)

{

int mid = start + (end-start) /2;

mergeSort(nums,start, mid);

mergeSort(nums,mid+1, end);

merge(nums,start, mid,end);

}

}

int* sortArray(int* nums, int numsSize, int* returnSize){

mergeSort(nums,0,numsSize-1);

*returnSize=numsSize;

return nums;

}