[912] Sort an Array (TBD)

拿來練習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;

}

「20260208 更新」

原來我不會寫quick sort !!!

對付leetcode 要: 3-way partition + random pivot

詳洽chatGpt (眼神死）

#include <stdlib.h>

#include <time.h>

void swap(int *a, int *b) {

    int t = *a;

    *a = *b;

    *b = t;

}

void quickSort(int* nums, int left, int right) {

    if (left >= right) return;

    // Random pivot

    int pivotIndex = left + rand() % (right - left + 1);

    int pivot = nums[pivotIndex];

    int lt = left;     // nums[left .. lt-1] < pivot

    int gt = right;    // nums[gt+1 .. right] > pivot

    int i  = left;

    while (i <= gt) {

        if (nums[i] < pivot) {

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

            i++;

            lt++;

        } else if (nums[i] > pivot) {

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

            gt--;

        } else {

            i++;

        }

    }

    quickSort(nums, left, lt - 1);

    quickSort(nums, gt + 1, right);

}

// LeetCode 介面

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

    *returnSize = numsSize;

    srand(1);  // LeetCode 不需要真的 random

    quickSort(nums, 0, numsSize - 1);

    return nums;

}