アルゴリズム学習-チェーンテーブルの集計ソート_O(1)空間_O(Nlogn)時間_C++
集計ソート
集計ソートについては前述したが,配列の数列の場合の集計ソート方法を与えたが,ソートの時間的複雑度はO(Nlogn)であった.見たいならリンクは以下の通りです:並べ替え、早く並べ替え、泡が立つ並べ替え
しかし,この集計ソートにはO(n)の余分な空間が必要であるという欠点がある.
では、この欠点はどのような状況で解決されるのでしょうか.数列がチェーンテーブル形式で格納されているときです!追加の申請O(n)レベルのスペースは必要ありません.
では、なぜ集計ソートを使うのでしょうか.まだ速い列があるのではないでしょうか.いずれも速度の速いソートです.実はチェーンテーブルには向いていません!スナップショットの場合、検索レバーはO(1)レベルですが、チェーンテーブルではheadノードしか得られませんので、取得レバーにはO(n)レベルが必要です.では複雑度は(nnlogn)レベルに上昇します.
コード実装
したがって、チェーンテーブルの場合、集計ソート、複雑度Nlognを使用する必要があり、追加のスペースを申請する必要はありません.
集計ソートについては前述したが,配列の数列の場合の集計ソート方法を与えたが,ソートの時間的複雑度はO(Nlogn)であった.見たいならリンクは以下の通りです:並べ替え、早く並べ替え、泡が立つ並べ替え
しかし,この集計ソートにはO(n)の余分な空間が必要であるという欠点がある.
では、この欠点はどのような状況で解決されるのでしょうか.数列がチェーンテーブル形式で格納されているときです!追加の申請O(n)レベルのスペースは必要ありません.
では、なぜ集計ソートを使うのでしょうか.まだ速い列があるのではないでしょうか.いずれも速度の速いソートです.実はチェーンテーブルには向いていません!スナップショットの場合、検索レバーはO(1)レベルですが、チェーンテーブルではheadノードしか得られませんので、取得レバーにはO(n)レベルが必要です.では複雑度は(nnlogn)レベルに上昇します.
コード実装
したがって、チェーンテーブルの場合、集計ソート、複雑度Nlognを使用する必要があり、追加のスペースを申請する必要はありません.
//
// main.cpp
// MergeList
//
// Created by Alps on 14/12/6.
// Copyright (c) 2014 chen. All rights reserved.
//
#include <iostream>
using namespace std;
struct ListNode{
int val;
ListNode* next;
ListNode(int x):val(x),next(NULL){}
};
class Solution{
public:
ListNode *sortList(ListNode* head){
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* mid = getMid(head);
ListNode* right = NULL;
if (mid != NULL) {
right = mid->next;
mid->next = NULL;
}
head = sortList(head);
right = sortList(right);
head = MergeList(head, right);
return head;
}
ListNode* getMid(ListNode* node){
if (node == NULL || node->next == NULL) {
return node;
}
ListNode* l1 = node;
ListNode* l2 = node->next;
while (l2 && l2->next) {
l1 = l1->next;
l2 = l2->next->next;
}
return l1;
}
ListNode* MergeList(ListNode* left, ListNode* right){
if (left == NULL) {
return right;
}
if (right == NULL) {
return left;
}
ListNode* temp = NULL;
if (left->val >= right->val) {
temp = right->next;
right->next = left;
left = right;
right = temp;
}
left->next = MergeList(left->next, right);
return left;
}
};
int main(int argc, const char * argv[]) {
Solution sl;
ListNode *head = new ListNode(4);
head->next = new ListNode(2);
head->next->next = new ListNode(1);
head->next->next->next = new ListNode(3);
sl.sortList(head);
return 0;
}