排序——归并排序与基数排序

归并排序

归并排序遵循了分治模式，直观上就是分解：分解带排序的元素的序列成各具n/2个元素的两个子序列；解决：使用归并排序递归的排序两个子序列；合并：合并两个已排序的子序列以产生已排序的答案。

首先看看如何合并已排序的两个数组，为了避免在每一个基本步骤都必须检查数组是否已经到了最末端，在两个数组的最末端都放置了哨兵——将两个数组的最末端的元素设置为最大，这样就可以避免对数组的检查：

int* MergeSort(int* arr, int p, int q, int r) {
       //the sort interval is arr[p, q] to arr[q + 1, r]
       int n1 = q - p + 1;
       int n2 = r - q;
       int* left = (int*)malloc(sizeof(1) * (n1+1));
       int* right = (int*)malloc(sizeof(1) * (n2+1));
       for (int i = p; i <= q; i++)
           left[i-p] = arr[i];
       for (int i = q + 1; i <= r; i++)
           right[i - q - 1] = arr[i];
       left[n1] = INT_MAX;
       right[n2] = INT_MAX;
       int i = 0;
       int j = 0;
       for (int k = p; k <= r; k++) {
           if (left[i] <= right[j]) {
               arr[k] = left[i];
               i += 1;
           }
           else if (left[i] > right[j]) {
               arr[k] = right[j];
               j += 1;
           }
       }
       free(left);
       free(right);
       return arr;
   }

下面使用循环不变式方法来证明这个算法的正确性：
初始化：在循环的第一次迭代之前，有k=p,数组arr[p, k - 1]为空，i， j 均为0，说明left[i]和right[j]都是各自所在数组里最小的元素，且这两个元素均没有被复制到arr数组里面；
保持：为了更好的理解循环不变式，首先假设left[i] <= right[j]，这时left[i]是最小的没有被复制到数组里的最小的元素，将left[i]复制到数组里面之后数组arr[p…k]包含了k-p-1个最小的元素，然后p 和 i，均加1，为下一次迭代重新建立了循环不变式。
终止：循环终止的条件是k=r+1。这个时候数组包含了两个数组的所有元素，且是有序的。
综上所述，证明了上述算法的正确性！

接下来考虑递归算法：

int* Merge(int* arr, int p, int r) {
       if (p < r) {
           int q = (p + r) / 2;
           Merge(arr, p, q);
           Merge(arr, q + 1, r);
           MergeSort(arr, p, q, r);
       }
       return arr;
   }

递归算法将一个数组分成两半，分别对这两半进行排序之后，再将这两个排好序的数组组合成为一个数组。

接下来分析归并算法的时间复杂度：
每一次都将一个节点划分成为两个，直到所有的节点都被划分成为最小的单位为止，划分的时候会产生log n + 1层，而对于每一层的划分，总的代价都是cn(遍历大数组，产生每一个小数组)，所以递归的总的代价就是cn(log n + 1) ，时间复杂度为 n(log n).

以下是本次在LeetCode上面所做的题目： Sort a linked list in O(n log n) time using constant space complexity.
根据上面的分析，程序如下所示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* sortList(struct ListNode* head) {
     int* MergeSort(int* arr, int p, int q, int r) {
        //the sort interval is arr[p, q] to arr[q + 1, r]
        int n1 = q - p + 1;
        int n2 = r - q;
        int* left = (int*)malloc(sizeof(1) * (n1+1));
        int* right = (int*)malloc(sizeof(1) * (n2+1));
        for (int i = p; i <= q; i++)
            left[i-p] = arr[i];
        for (int i = q + 1; i <= r; i++)
            right[i - q - 1] = arr[i];
        left[n1] = INT_MAX;
        right[n2] = INT_MAX;
        int i = 0;
        int j = 0;
        for (int k = p; k <= r; k++) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i += 1;
            }
            else if (left[i] > right[j]) {
                arr[k] = right[j];
                j += 1;
            }
        }
        free(left);
        free(right);
        return arr;
    }

    int* Merge(int* arr, int p, int r) {
        if (p < r) {
            int q = (p + r) / 2;
            Merge(arr, p, q);
            Merge(arr, q + 1, r);
            MergeSort(arr, p, q, r);
        }
        return arr;
    }
    
    int size = 0;
    struct ListNode* temp = head;
    while (temp != NULL) {
        size ++;
        temp = temp -> next;
    }
    if (size > 1) {
        int* arr1 = (int*)malloc(sizeof(1) * size);
        size = 0;
        temp = head;
        while (temp != NULL) {
            arr1[size] = temp -> val;
            size ++;
            temp = temp -> next;
        }
        
        Merge(arr1, 0, size - 1);
        temp = head;
        size = 0;
        while (temp != NULL) {
            temp -> val = arr1[size];
            size ++;
            temp = temp -> next;
        }
        free(arr1);
    }
    
    return head;
}