「データ構造とアルゴリズム分析(c説明)」——集計ソート

集計ソートは、比較に基づく内部/外部ソートアルゴリズムに属する分割法の良い例である.一般的な集計アルゴリズムは、O(n * log(n))の時間とO(n)の空間的複雑さを有する.オンサイト集計アルゴリズムは、集計ソートをより効率的にするために、追加のスペースオーバーヘッドを低減するのに役立ちます.
時間の複雑さの導出も非常に典型的である.
T(N)=2T(N2)+N
T(N)N=T(N/2)N/2+1
T(N)N=11+logN
T(N)=O(NlogN)
集計ソートが外部ソートに簡単に適用できるのは、集計ソートの集計プロセスが順次スキャンされ、順次格納されたファイルの処理に使用でき、多重集計はマルチスレッドや並列計算で加速することができ、大きなファイルの処理が便利になるからです.ランダムにファイルにアクセスするには、そんなに速くありません.
ソート配列

void merge(int a[], int temp[], int left, int right, int rightEnd) {
    int leftEnd = right - 1;
    int numElement = rightEnd - left + 1;
    int i = left;
    while (left <= leftEnd && right <= rightEnd) {
        if (a[left] < a[right])
            temp[i++] = a[left++];
        else
            temp[i++] = a[right++];
    }

    while (left <= leftEnd)
        temp[i++] = a[left++];

    while (right <= rightEnd)
        temp[i++] = a[right++];

    for (i = 0; i < numElement; i++, rightEnd--)
        a[rightEnd] = temp[rightEnd];
}

void mergeSort(int a[], int temp[], int leftBegin, int rightEnd) {
    int mid;
    if (leftBegin < rightEnd) {
        mid = (leftBegin + rightEnd)/2;
        mergeSort(a, temp, leftBegin, mid);
        mergeSort(a, temp, mid + 1, rightEnd);
        merge(a, temp, leftBegin, mid + 1, rightEnd);
    }
}


int main () {
    int a[10] = {9, 2, 8, 3, 4, 1, 5, 18, 11, 14};
    int  temp[10];
    mergeSort(a, temp, 0, 9);
    for (int i = 0; i < 10 ; i++)
        printf("%d#", a[i]);
    printf("
");
}

2つの順序付きチェーンテーブルをマージ
leetcode 21問題は、2つの秩序化チェーンテーブルの統合を実現するために集計ソートを適用することである.
次のコードはテストに合格できます.

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL)
            return l2;
        if (l2 == NULL)
            return l1;
        ListNode *head = new ListNode(0);
        ListNode *pos = head;
        int temp;

        while(l1 && l2) {
            if (l1->val < l2->val) {
                temp = l1->val;
                l1 = l1->next;
            }
            else {
                temp = l2->val;
                l2 = l2->next;
            }
            pos->next = new ListNode(temp);
            pos = pos->next;
        }

        while(l1 != NULL) {
            pos->next = new ListNode(l1->val);
            pos = pos->next;
            l1 = l1->next;
        }

        while(l2 != NULL) {
            pos->next = new ListNode(l2->val);
            pos = pos->next;
            l2 = l2->next;
        }
        return head->next;
    }