{"id":179,"date":"2013-06-08T20:02:16","date_gmt":"2013-06-08T12:02:16","guid":{"rendered":"http:\/\/coderbee.net\/?p=179"},"modified":"2013-06-17T16:29:23","modified_gmt":"2013-06-17T08:29:23","slug":"%e6%8f%92%e5%85%a5%e6%8e%92%e5%ba%8f%e4%b8%8e%e5%86%92%e6%b3%a1%e6%8e%92%e5%ba%8f","status":"publish","type":"post","link":"https:\/\/coderbee.net\/index.php\/algorithm\/20130608\/179","title":{"rendered":"\u63d2\u5165\u6392\u5e8f\u4e0e\u5192\u6ce1\u6392\u5e8f"},"content":{"rendered":"

\u8bb0\u5f55\u63d2\u5165\u6392\u5e8f\u53ca\u5176\u6539\u8fdb\u7b97\u6cd5\u3001\u5e0c\u5c14\u6392\u5e8f\u3001\u5192\u6ce1\u6392\u5e8f\uff0c\u53ca\u63d2\u5165\u6392\u5e8f\u4e0e\u5192\u6ce1\u6392\u5e8f\u7684\u5bf9\u6bd4\u3002
\n<\/p>\n

\u63d2\u5165\u6392\u5e8f<\/h2>\n

\u4ee5\u5347\u5e8f\u4e3a\u4f8b\u3002<\/p>\n

    \n
  1. \u6ca1\u6709\u5143\u7d20\u6216\u53ea\u6709\u4e00\u4e2a\u5143\u7d20\u65f6\uff0c\u9ed8\u8ba4\u5c31\u662f\u6709\u5e8f\u7684\u3002<\/li>\n
  2. \u6392\u5e8f\u8fc7\u7a0b\u4e2d\uff0c\u6570\u7ec4\u5206\u4e3a\u4e24\u90e8\u5206\uff1a\u524d\u4e00\u90e8\u5206\u662f\u6709\u5e8f\u7684\uff0c\u540e\u4e00\u90e8\u5206\u662f\u4e71\u5e8f\u7684\u3002<\/li>\n
  3. \u4ece\u4e71\u5e8f\u90e8\u5206\u6bcf\u6b21\u9009\u53d6\u524d\u9762\u7684\u4e00\u4e2a\u5143\u7d20\uff0c\u63d2\u5165\u5230\u6709\u5e8f\u90e8\u5206\u3002\u76f4\u5230\u6240\u6709\u5143\u7d20\u90fd\u6709\u5e8f\u3002\n
      \n
    1. \u4ece\u4e71\u5e8f\u90e8\u5206\u6bcf\u6b21\u9009\u53d6\u6700\u524d\u9762\u7684\u4e00\u4e2a\u5143\u7d20v\uff0c\u5176\u4e0b\u6807\u4e3ai\u3002<\/li>\n
    2. \u5728\u6709\u5e8f\u90e8\u5206\u4ece\u53f3\u5f80\u524d\u67e5\u627e\u7b2c\u4e00\u4e2a\u5c0f\u4e8e\u7b49\u4e8ev\u7684\u5143\u7d20\uff0c\u5176\u4e0b\u6807\u4e3aj\u3002<\/li>\n
    3. \u5728\u67e5\u627e\u7684\u8fc7\u7a0b\u4e2d\uff0c\u628a\u6240\u6709\u5927\u4e8ev\u7684\u5143\u7d20\u540e\u79fb\u4e00\u4e2a\u4f4d\u7f6e\u3002<\/li>\n
    4. \u628av\u63d2\u5165\u5230\u4f4d\u7f6ej+1\u3002<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n
      \nfunc InsertSort(arr []int) {\n    for i, end := 1, len(arr); i < end; i++ {\n        j := i - 1\n        v := arr[i]\n\n        for ; j >= 0 && arr[j] > v; j-- {\n            arr[j+1] = arr[j]\n        }\n\n        arr[j+1] = v\n    }\n}\n<\/code><\/pre>\n
      \u63d2\u5165\u6392\u5e8f\u6539\u8fdb<\/h3>\n
      \u63d2\u5165\u6392\u5e8f\u4e3b\u8981\u6709\u4e24\u4e2a\u64cd\u4f5c\uff1a\u5728\u6709\u5e8f\u90e8\u5206\u67e5\u627e\u5408\u9002\u7684\u63d2\u5165\u4f4d\u7f6e\uff0c\u5728\u67e5\u627e\u8fc7\u7a0b\u4e2d\u79fb\u52a8\u5143\u7d20\u3002<\/p>\n
      \u5728\u6709\u5e8f\u6570\u7ec4\u4e2d\u67e5\u627e\u65f6\uff0c\u5982\u679c\u4f7f\u7528\u987a\u5e8f\u67e5\u627e\uff0c\u5219\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n)\uff1b\u6240\u4ee5\u53ef\u4ee5\u4f7f\u7528\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(lg(n))\u7684\u6298\u534a\u67e5\u627e\u6765\u6539\u8fdb\u3002<\/p>\n
      \u5728\u79fb\u52a8\u5143\u7d20\u65f6\uff0c\u76ee\u524d\u90fd\u662f\u4e00\u6b21\u53ea\u79fb\u52a8\u4e00\u4e2a\u4f4d\u7f6e\u3002\u5e0c\u5c14\u6392\u5e8f\u5728\u8fd9\u65b9\u9762\u8fdb\u884c\u4e86\u6539\u8fdb\u3002<\/p>\n
      \u5e26\u6298\u534a\u67e5\u627e\u7684\u63d2\u5165\u6392\u5e8f<\/h4>\n
      \u5728\u5408\u9002\u7684\u63d2\u5165\u4f4d\u7f6e\u65f6\uff0c\u4ee5\u4ece\u5de6\u5f80\u53f3\u7684\u65b9\u5411\u770b\uff0c\u662f\u8981\u627e\u7b2c\u4e00\u4e2a\u5927\u4e8e\u76ee\u6807\u5143\u7d20v\u7684\u5143\u7d20\u3002<\/p>\n
      l, r \u5206\u522b\u4e3a\u6307\u5411\u6709\u5e8f\u90e8\u5206\u7684\u7b2c\u4e00\u4e2a\u548c\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u6307\u9488\uff0c\u5f53\u4e2d\u503c\u5143\u7d20arr[mid] > v\u65f6\uff0c\u53ef\u4ee5\u8ba4\u4e3amid\u4e4b\u524d\u8fd8\u6709\u5143\u7d20\u5927\u4e8ev\uff1b\u5426\u5219\uff0c\u53ef\u4ee5\u8ba4\u4e3amid\u4e4b\u540e\u8fd8\u6709\u5143\u7d20\u5c0f\u4e8e\u7b49\u4e8ev\u3002\u5f53l\u5927\u4e8er\u65f6\uff0cl\u5373\u4e3a\u8981\u627e\u7684\u4f4d\u7f6e\u3002<\/p>\n
      \u5b9e\u73b0<\/h5>\n
      \n func InsertSortWithBinarySearch(arr []int) {\n     for i, end := 1, len(arr); i < end; i++ {\n         v := arr[i]\n         l, r := 0, i-1                                    \/\/  l, r \u5206\u522b\u4e3a\u6307\u5411\u6709\u5e8f\u90e8\u5206\u7684\u7b2c\u4e00\u4e2a\u548c\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u6307\u9488\n         for l <= r {\n             mid := l + (r-l)\/2                         \/\/ \u907f\u514d\u6ea2\u51fa\uff0c(l+r)\/2\u53ef\u80fd\u4ea7\u751f\u6ea2\u51fa\u3002\n             if arr[mid] > v {\n                 r = mid - 1                              \/\/  \u8ba4\u4e3amid\u4e4b\u524d\u8fd8\u6709\u5143\u7d20\u5927\u4e8ev\n             } else {\n                 l = mid + 1                              \/\/  \u8ba4\u4e3amid\u4e4b\u540e\u8fd8\u6709\u5143\u7d20\u5c0f\u4e8e\u7b49\u4e8ev\n             }\n         }\n         if l < i {\n             util.ArrayCopy(arr, l, arr, l+1, i-l)     \/\/  l+1\u76841\u8868\u793a\u540e\u79fb\u4e00\u4e2a\u5143\u7d20\uff0ci-l \u8868\u793a\u9700\u8981\u79fb\u52a8\u7684\u5143\u7d20\u6570\u91cf\n             arr[l] = v\n         }\n     }\n}\n<\/code><\/pre>\n
      \u6ce8\u610f\uff1a<\/strong>\u8fd9\u4e2a\u7b97\u6cd5\u5e76\u6ca1\u6709\u51cf\u5c11\u79fb\u52a8\u5143\u7d20\u7684\u6b21\u6570\uff0c\u53ea\u662f\u51cf\u5c11\u4e86\u67e5\u627e\u5143\u7d20\u7684\u6bd4\u8f83\u6b21\u6570\u3002<\/p>\n
      \u5e0c\u5c14\u6392\u5e8f<\/h4>\n
      \u5e0c\u5c14\u6392\u5e8f\u662f\u63d2\u5165\u6392\u5e8f\u7684\u4e00\u79cd\u6539\u8fdb\uff0c\u57fa\u4e8e\uff1a\u5f53\u6570\u7ec4\u57fa\u672c\u6709\u5e8f\u65f6\uff0c\u63d2\u5165\u6392\u5e8f\u8fdb\u884c\u67e5\u627e\u548c\u79fb\u52a8\u64cd\u4f5c\u90fd\u662f\u9ad8\u6548\u7684\uff0c\u5b83\u628a\u6bcf\u9694\u56fa\u5b9a\u95f4\u9694\u7684\u5143\u7d20\u5f53\u4f5c\u4e00\u4e2a\u5b50\u6570\u7ec4\u8fdb\u884c\u63d2\u5165\u6392\u5e8f\uff0c\u9010\u6b65\u7f29\u5c0f\u95f4\u9694\uff0c\u6700\u540e\u5bf9\u6574\u4e2a\u6570\u7ec4\u8fdb\u884c\u63d2\u5165\u6392\u5e8f\u3002<\/p>\n
      \u5b50\u6570\u7ec4\u95f4\u9694\u7684\u9009\u53d6\u4e0d\u80fd\u542b\u6709\u516c\u5171\u7684\u56e0\u5b50\uff0c\u5426\u5219\u4f1a\u5728\u67d0\u4e2a\u95f4\u9694\u4e0a\u91cd\u590d\u8fdb\u884c\u6392\u5e8f\uff0c\u4e00\u822c\u9009\u53d6\u8d28\u6570\u4f5c\u4e3a\u95f4\u9694\u3002\u6700\u540e\u4e00\u4e2a\u95f4\u9694\u5fc5\u987b\u662f1<\/code>\u3002<\/p>\n
      \u5e0c\u5c14\u6392\u5e8f\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f\u5f88\u590d\u6742\u7684\uff0c\u4e0d\u4ec5\u4e0e\u8f93\u5165\u6709\u5173\uff0c\u8fd8\u53d6\u51b3\u4e8e\u4e0d\u540c\u95f4\u9694\u6570\u7ec4\u7684\u9009\u62e9\u3002<\/p>\n
      \u5b9e\u73b0<\/h5>\n
      \nfunc GetSkipTable() []int {\n    return []int{19, 13, 7, 5, 3, 1}\n}\n\nfunc ShellSort(arr []int) {\n    limit := len(arr)\n    for _, jmp := range GetSkipTable() {\n        for i := jmp; i < limit; i += jmp {\n            j, v := i-jmp, arr[i]\n            for ; j >= 0 && arr[j] > v; j -= jmp {\n                arr[j+jmp] = arr[j]\n            }\n            arr[j+jmp] = v\n        }\n    }\n}\n<\/code><\/pre>\n
      \u5192\u6ce1\u6392\u5e8f<\/h2>\n
      \u4ee5\u5347\u5e8f\u4e3a\u4f8b\uff1a<\/p>\n
        \n
      1. \u6570\u7ec4\u4e5f\u5206\u4e3a\u4e24\u90e8\u5206\uff1a\u524d\u9762\u7684\u662f\u4e71\u5e8f\u7684\uff08US\uff09\uff0c\u9ed8\u8ba4\u662f\u6574\u4e2a\u6570\u7ec4\uff1b\u540e\u9762\u7684\u662f\u6709\u5e8f\u7684\uff08S\uff09\uff0c\u9ed8\u8ba4\u662f\u7a7a\u7684\u3002<\/li>\n
      2. \u904d\u5386US\uff0c\u5bf9\u4e8e\u76f8\u90bb\u7684\u4e24\u4e2a\u5143\u7d20\uff0c\u5982\u679c\u524d\u9762\u7684\u6bd4\u540e\u9762\u7684\u5927\uff0c\u5219\u4ea4\u6362\u4e24\u4e2a\u503c\u3002<\/li>\n
      3. \u8fd9\u6837\uff0c\u5728\u904d\u5386\u5b8c\u6574\u4e2aUS\u65f6\uff0cUS\u7684\u6700\u5927\u5143\u7d20\u5c06\u88ab\u4ea4\u6362\u81f3US\u5e95\u90e8\uff0c\u79f0\u4e3aS\u7684\u4e00\u90e8\u5206\uff0cUS\u7684\u6570\u91cf\u51cf\u4e00\u3002<\/li>\n
      4. \u5faa\u73af\u76f4\u81f3US\u4e3a\u7a7a\u3002<\/li>\n<\/ol>\n
        \nfunc BubbleSort(arr []int) {\n    for i, end := 0, len(arr); i < end; i++ {\n        for j, innerEnd := 1, end-i; j < innerEnd; j++ {\n            if arr[j] < arr[j-1] {\n                util.Swap(arr, j, j-1)\n            }\n        }\n    }\n}\n<\/code><\/pre>\n
        \u5192\u6ce1\u6392\u5e8f\u7684\u6539\u8fdb<\/h3>\n
        \u5728\u904d\u5386US\u65f6\uff0c\u5982\u679c\u6574\u4e2a\u904d\u5386\u8fc7\u7a0b\u6ca1\u6709\u4e86\u4ea4\u6362\u64cd\u4f5c\uff0c\u8bf4\u660e\u6574\u4e2aUS\u5df2\u7ecf\u662f\u6709\u5e8f\u7684\u4e86\uff0c\u53ef\u4ee5\u63d0\u524d\u7ed3\u675f\u3002<\/p>\n
        \nfunc BubbleSortImprove(arr []int) {\n    for i, end := 0, len(arr); i < end; i++ {\n        isSwaped := false\n        for j, innerEnd := 1, end-i; j < innerEnd; j++ {\n            if arr[j] < arr[j-1] {\n                util.Swap(arr, j, j-1)\n                isSwaped = true\n            }\n        }\n        if !isSwaped {\n            return\n        }\n    }\n}\n<\/code><\/pre>\n
        \u63d2\u5165\u6392\u5e8f\u4e0e\u5192\u6ce1\u6392\u5e8f\u7684\u5bf9\u6bd4<\/h2>\n
          \n
        1. \u4e24\u8005\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u6700\u5dee\u90fd\u662fO(n^2)\uff0c\u6700\u597d\u90fd\u662fO(n)\u3002<\/li>\n
        2. \u63d2\u5165\u6392\u5e8f\u53ef\u4ee5\u5229\u7528\u5728\u5df2\u7ecf\u6709\u5e8f\u90e8\u5206\u4e0a\u4f7f\u7528\u6298\u534a\u67e5\u627e\u6765\u52a0\u901f\u67e5\u627e\u63d2\u5165\u4f4d\u7f6e\u3002<\/li>\n
        3. \u5192\u6ce1\u6392\u5e8f\u53ef\u4ee5\u5229\u7528\u5192\u6ce1\u8fc7\u7a0b\u662f\u5426\u6709\u4ea4\u6362\u64cd\u4f5c\u6765\u5224\u65ad\u662f\u5426\u5df2\u7ecf\u6709\u5e8f\u3002<\/li>\n<\/ol>\n\n
          \u6b22\u8fce\u5173\u6ce8\u6211\u7684\u5fae\u4fe1\u516c\u4f17\u53f7: coderbee\u7b14\u8bb0<\/strong>\uff0c\u53ef\u4ee5\u66f4\u53ca\u65f6\u56de\u590d\u4f60\u7684\u8ba8\u8bba\u3002<\/p>\n
          <\/p>\n","protected":false},"excerpt":{"rendered":"
          \u8bb0\u5f55\u63d2\u5165\u6392\u5e8f\u53ca\u5176\u6539\u8fdb\u7b97\u6cd5\u3001\u5e0c\u5c14\u6392\u5e8f\u3001\u5192\u6ce1\u6392\u5e8f\uff0c\u53ca\u63d2\u5165\u6392\u5e8f\u4e0e\u5192\u6ce1\u6392\u5e8f\u7684\u5bf9\u6bd4\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[53],"tags":[55,56],"_links":{"self":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/179"}],"collection":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/comments?post=179"}],"version-history":[{"count":7,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/179\/revisions"}],"predecessor-version":[{"id":215,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/179\/revisions\/215"}],"wp:attachment":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/media?parent=179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/categories?post=179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/tags?post=179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}