C学习--归并排序

算法思路

• 有限数组可以二分，直到所有数组都为1.
• 两条有序数组合并为一条新的数组

分治是一种解决问题的处理思想，递归是一种规程技巧

Show Me Code

下面是归并排序的代码。

void mergeSort(uint8_t* arr, int lenth) {
    mergeSortC(arr, 0, lenth-1);
}

void mergeSortC(uint8_t* arr, int p, int r) {
    if (p >= r) {
        return;
    }
    int q = (p + r) / 2;
    //Recursive Call
    mergeSortC(arr, p, q);
    mergeSortC(arr, q+1, r);
    //Init a tmp array story the compare value
    uint8_t tmpArr[r-p+1];
    int i = p;
    int j = q+1;
    for (int t = 0; t <= (r-p); t ++) {
        if (j > r) {
            tmpArr[t] = arr[i];
            i ++;
            continue;
        }
        if (i > q) {
            tmpArr[t] = arr[j];
            j ++;
            continue;
        }
        //Compare Array One by one
        if (arr[i] > arr[j]) {
            tmpArr[t] = arr[j];
            j++;
        }else {
            tmpArr[t] = arr[i];
            i++;
        }
    }
    // Copy tmpArray into Arr[p~r]
    int count = (int)sizeof(tmpArr);
    for (int i = 0; i < count; i ++) {
        arr[p+i] = tmpArr[i];
    }
}