{"id":616,"date":"2013-09-12T19:46:25","date_gmt":"2013-09-12T11:46:25","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=616"},"modified":"2013-09-12T19:46:25","modified_gmt":"2013-09-12T11:46:25","slug":"%e6%9f%90%e5%b9%b4%e7%a0%94%e7%a9%b6%e7%94%9f%e5%a4%8d%e8%af%95%e6%9c%ba%e8%af%95%e9%a2%98","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=616","title":{"rendered":"\u67d0\u5e74\u7814\u7a76\u751f\u590d\u8bd5\u673a\u8bd5\u9898"},"content":{"rendered":"

\u8bfb\u5165\u4e00\u6279\u4ee5\u8d1f\u6570\u4e3a\u7ed3\u675f\u7684\u6b63\u6574\u6570\uff0c\u6570\u636e\u4e3a5\uff0c7\uff0c2\uff0c4\uff0c9\uff0c\uff0d1\uff0c\u5efa\u7acb\u4e00\u4e2a\u5e26\u5934\u7ed3\u70b9\u7684\u94fe\u8868\uff0c\u94fe\u8868\u7684\u6bcf\u4e2a\u7ed3\u70b9\u4e2d\u5305\u542b\u6709\u4e24\u4e2a\u6307\u9488\uff1a\u4e00\u4e2a\u7528\u4e8e\u94fe\u63a5\u8f93\u5165\u7684\u5148\u540e\u987a\u5e8f\uff0c\u53e6\u4e00\u4e2a\u7528\u4e8e\u94fe\u63a5\u8f93\u5165\u6574\u6570\u4ece\u5c0f\u5230\u5927\u7684\u987a\u5e8f\u3002\u5e76\u5206\u522b\u6309\u4e24\u4e2a\u6307\u9488\u65b9\u5411\u8fdb\u884c\u904d\u5386\u8f93\u51fa\u3002
\n====================
\n\u8fd9\u4e2a\u8003\u7684\u57fa\u7840\u77e5\u8bc6\uff0c\u4e00\u4e2a\u662f\u94fe\u8868\u7684\u4e1c\u897f\uff0c\u6307\u9488\u554a\u4ec0\u4e48\u7684
\n\u53e6\u5916\u5c31\u662f\u5355\u5411\u94fe\u8868\u600e\u4e48\u6392\u5e8f
\n\u6211\u80fd\u60f3\u5230\u7684\u65b9\u6cd5\u561b~\u5176\u5b9e\u6392\u5e8f\u8fd9\u4e2a\u4e1c\u897f\uff0c\u7ed9\u5b9a\u5f53\u524d\u7684\u6570\u503cvalue
\n\u5982\u679c\u5b58\u5728x,\u4f7f\u5f97 val <=x < MINVALUE\uff0c\u90a3\u4e48x\u5c31\u662f\u5f53\u524d\u8282\u70b9\u7684\u540e\u7ee7\u4e86
\n\u540e\u9762\u8fd9\u4e2aMINVALUE\uff0c\u5c31\u662f\u9009\u5b9a\u4e86\u8fd9\u4e2ax\u4e4b\u540e\uff0c\u628aMINVALUE\u8bbe\u5b9a\u4e3ax\uff0c\u7136\u540e\u7ee7\u7eed\u904d\u5386\u8f93\u5165\u6b21\u5e8f\uff0c\u770b\u770b\u8fd8\u6709\u6ca1\u6709\u6bd4x\u66f4\u9002\u5408\u7684\u8282\u70b9\u4e86
\n\u6709\u70b9\u65e0\u9650\u903c\u8fd1\u7684\u5473\u9053…\u8981\u6ce8\u610f\u7684\u662f\u6307\u9488\u64cd\u4f5c\u7684\u65f6\u5019\u522b\u628a\u81ea\u5df1\u8ddf\u81ea\u5df1\u6765\u6bd4\uff0c\u4e0d\u7136\u8f93\u5165\u65f6\u5982\u679c\u6709\u76f8\u540c\u6570\u5c31\u4f1a\u73a9\u5b8c\u4e86~
\n\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n^2)\uff0c\u4e0d\u8fc7\u561b…\u8fd9\u4e2a\u8282\u9aa8\u773c\u80fd\u60f3\u51fa\u65b9\u6cd5\u5c31\u884c
\n 
\n\u5410\u69fd\u4e00\u53e5\uff0cVC6\u771f\u4ed6\u5988\u7684\u592a\u96be\u7528\u4e86\uff01\uff01\uff01
\n=====================
\n
\n#include
\nusing namespace std;
\nstruct Node
\n{
\n\tint val;
\n\tNode *ptrOrder;
\n\tNode *ptrSort;
\n\tNode()
\n\t{
\n\t\tptrOrder = NULL;
\n\t\tptrSort = NULL;
\n\t\tval = -1;
\n\t}
\n};
\nint main()
\n{
\n\t\/\/const int MAX_SIZE = 100;
\n\t\/\/int inputArray[MAX_SIZE];
\n\t\/\/Initialize link head
\n\tNode root;
\n\tint input;
\n\tint arySize = 0;
\n\tNode *currNode = &root;
\n\t\/\/Node *prevNode = NULL;
\n\twhile(cin >> input)
\n\t{
\n\t\tif(input < 0 || arySize >= MAX_SIZE)
\n\t\t\tbreak;
\n\t\tNode *newNode = new Node;
\n\t\tnewNode->val = input;
\n\t\tcurrNode -> ptrOrder = newNode;
\n\t\tcurrNode = newNode;
\n\t}
\n\t\/\/Sort
\n\tcurrNode = &root;
\n\twhile(currNode != NULL)
\n\t{
\n\t\tNode *nextNode = root.ptrOrder;
\n\t\tint min_val_max = 65535;
\n\t\tint currValue = currNode->val;
\n\t\twhile(nextNode != NULL)
\n\t\t{
\n\t\t\tif(nextNode == currNode)
\n\t\t\t{
\n\t\t\t\tnextNode = nextNode->ptrOrder;
\n\t\t\t\tcontinue;
\n\t\t\t}
\n\t\t\tint nextValue = nextNode->val;
\n\t\t\tif(nextValue >= currValue && nextValue < min_val_max)\n\t\t\t{\n\t\t\t\tmin_val_max = nextValue;\n\t\t\t\tcurrNode->ptrSort = nextNode;
\n\t\t\t}
\n\t\t\tnextNode = nextNode->ptrOrder;
\n\t\t}
\n\t\tcurrNode = currNode->ptrOrder;
\n\t}
\n\t\/\/Output
\n\tcurrNode = root.ptrOrder;
\n\twhile(currNode != NULL)
\n\t{
\n\t\tcout << currNode->val << \" \";\n\t\tcurrNode = currNode -> ptrOrder;
\n\t}
\n\tcout << endl;\n\tcurrNode = root.ptrSort;\n\twhile(currNode != NULL)\n\t{\n\t\tcout << currNode->val << \" \";\n\t\tcurrNode = currNode -> ptrSort;
\n\t}
\n\tcout << endl;\n\t\/\/Clear memory if you have enough time :)\n\tcin.get();\n\treturn 0;\n}\n<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"

\u8bfb\u5165\u4e00\u6279\u4ee5\u8d1f\u6570\u4e3a\u7ed3\u675f\u7684\u6b63\u6574\u6570\uff0c\u6570\u636e\u4e3a5\uff0c7\uff0c2\uff0c4\uff0c9\uff0c\uff0d1\uff0c\u5efa\u7acb\u4e00\u4e2a\u5e26\u5934\u7ed3\u70b9\u7684\u94fe\u8868\uff0c\u94fe\u8868\u7684\u6bcf\u4e2a\u7ed3\u70b9\u4e2d\u5305\u542b\u6709\u4e24\u4e2a\u6307\u9488\uff1a\u4e00\u4e2a\u7528\u4e8e\u94fe\u63a5\u8f93\u5165\u7684\u5148\u540e\u987a\u5e8f\uff0c\u53e6\u4e00\u4e2a\u7528\u4e8e\u94fe\u63a5\u8f93\u5165\u6574\u6570\u4ece\u5c0f\u5230\u5927\u7684\u987a\u5e8f\u3002\u5e76\u5206\u522b\u6309\u4e24\u4e2a\u6307\u9488\u65b9\u5411\u8fdb\u884c\u904d\u5386\u8f93\u51fa\u3002 ==================== \u8fd9\u4e2a\u8003\u7684\u57fa\u7840\u77e5\u8bc6\uff0c\u4e00\u4e2a\u662f\u94fe\u8868\u7684\u4e1c\u897f\uff0c\u6307\u9488\u554a\u4ec0\u4e48\u7684 \u53e6\u5916\u5c31\u662f\u5355\u5411\u94fe\u8868\u600e\u4e48\u6392\u5e8f \u6211\u80fd\u60f3\u5230\u7684\u65b9\u6cd5\u561b~\u5176\u5b9e\u6392\u5e8f\u8fd9\u4e2a\u4e1c\u897f\uff0c\u7ed9\u5b9a\u5f53\u524d\u7684\u6570\u503cvalue \u5982\u679c\u5b58\u5728x,\u4f7f\u5f97 val <=x < MINVALUE\uff0c\u90a3\u4e48x\u5c31\u662f\u5f53\u524d\u8282\u70b9\u7684\u540e\u7ee7\u4e86 \u540e\u9762\u8fd9\u4e2aMINVALUE\uff0c\u5c31\u662f\u9009\u5b9a\u4e86\u8fd9\u4e2ax\u4e4b\u540e\uff0c\u628aMINVALUE\u8bbe\u5b9a\u4e3ax\uff0c\u7136\u540e\u7ee7\u7eed\u904d\u5386\u8f93\u5165\u6b21\u5e8f\uff0c\u770b\u770b\u8fd8\u6709\u6ca1\u6709\u6bd4x\u66f4\u9002\u5408\u7684\u8282\u70b9\u4e86 \u6709\u70b9\u65e0\u9650\u903c\u8fd1\u7684\u5473\u9053…\u8981\u6ce8\u610f\u7684\u662f\u6307\u9488\u64cd\u4f5c\u7684\u65f6\u5019\u522b\u628a\u81ea\u5df1\u8ddf\u81ea\u5df1\u6765\u6bd4\uff0c\u4e0d\u7136\u8f93\u5165\u65f6\u5982\u679c\u6709\u76f8\u540c\u6570\u5c31\u4f1a\u73a9\u5b8c\u4e86~ \u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n^2)\uff0c\u4e0d\u8fc7\u561b…\u8fd9\u4e2a\u8282\u9aa8\u773c\u80fd\u60f3\u51fa\u65b9\u6cd5\u5c31\u884c   \u5410\u69fd\u4e00\u53e5\uff0cVC6\u771f\u4ed6\u5988\u7684\u592a\u96be\u7528\u4e86\uff01\uff01\uff01 ===================== #include using namespace std; struct Node { int val; Node *ptrOrder; Node *ptrSort; Node() { ptrOrder = NULL; ptrSort = NULL; val = -1; } }; int main() { \/\/const int MAX_SIZE = 100; \/\/int inputArray[MAX_SIZE]; \/\/Initialize link head […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-616","post","type-post","status-publish","format-standard","hentry","category-study"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/616","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=616"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/616\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=616"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=616"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=616"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}