{"id":3344,"date":"2022-07-30T22:01:39","date_gmt":"2022-07-30T19:01:39","guid":{"rendered":"https:\/\/demensdeum.com\/blog\/?p=3344"},"modified":"2024-12-16T22:32:18","modified_gmt":"2024-12-16T19:32:18","slug":"quicksort","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/zh\/2022\/07\/30\/quicksort\/","title":{"rendered":"\u5feb\u901f\u6392\u5e8f"},"content":{"rendered":"

\u5feb\u901f\u6392\u5e8f\u662f\u4e00\u79cd\u5206\u800c\u6cbb\u4e4b\u7684\u6392\u5e8f\u7b97\u6cd5\u3002\u9012\u5f52\u5730\uff0c\u6211\u4eec\u9010\u4e2a\u89e3\u6790\u6570\u5b57\u6570\u7ec4\uff0c\u5c06\u6240\u9009\u53c2\u8003\u5143\u7d20\u4e2d\u7684\u6570\u5b57\u6309\u7167\u8f83\u5c0f\u548c\u8f83\u5927\u7684\u987a\u5e8f\u653e\u7f6e\uff0c\u5e76\u5c06\u53c2\u8003\u5143\u7d20\u672c\u8eab\u63d2\u5165\u5230\u5b83\u4eec\u4e4b\u95f4\u7684\u622a\u6b62\u4f4d\u7f6e\u3002\u7ecf\u8fc7\u51e0\u6b21\u9012\u5f52\u8fed\u4ee3\u540e\uff0c\u60a8\u5c06\u5f97\u5230\u4e00\u4e2a\u6392\u5e8f\u5217\u8868\u3002\u65f6\u95f4\u590d\u6742\u5ea6 O(n2<\/sup>)\u3002<\/p>\n

\u65b9\u6848\uff1a<\/p>\n

    \n
  1. \u6211\u4eec\u9996\u5148\u4ece\u5916\u90e8\u83b7\u53d6\u5143\u7d20\u5217\u8868\uff0c\u5373\u6392\u5e8f\u8fb9\u754c\u3002\u7b2c\u4e00\u6b65\uff0c\u6392\u5e8f\u8fb9\u754c\u5c06\u4ece\u5934\u5230\u5c3e\u3002<\/li>\n
  2. \u68c0\u67e5\u8d77\u59cb\u8fb9\u754c\u548c\u7ed3\u675f\u8fb9\u754c\u662f\u5426\u76f8\u4ea4\uff1b\u5982\u679c\u53d1\u751f\u8fd9\u79cd\u60c5\u51b5\uff0c\u5219\u8be5\u7ed3\u675f\u4e86<\/li>\n
  3. \u4ece\u5217\u8868\u4e2d\u9009\u62e9\u67d0\u4e2a\u5143\u7d20\u5e76\u5c06\u5176\u547d\u540d\u4e3a\u6570\u636e\u900f\u89c6<\/li>\n
  4. \u5c06\u5176\u5411\u53f3\u79fb\u52a8\u5230\u6700\u540e\u4e00\u4e2a\u7d22\u5f15\u5904\u7684\u672b\u5c3e\uff0c\u8fd9\u6837\u5c31\u4e0d\u4f1a\u59a8\u788d<\/li>\n
  5. \u521b\u5efa\u4e00\u4e2a*\u8f83\u5c0f\u6570\u5b57*\u4ecd\u7b49\u4e8e\u96f6\u7684\u8ba1\u6570\u5668<\/li>\n
  6. \u4ece\u5de6\u5230\u53f3\u5faa\u73af\u904d\u5386\u5217\u8868\uff0c\u76f4\u5230\u5f15\u7528\u5143\u7d20\u6240\u5728\u7684\u6700\u540e\u4e00\u4e2a\u7d22\u5f15\uff08\u5305\u62ec\u8be5\u7d22\u5f15\uff09<\/li>\n
  7. \u6211\u4eec\u5c06\u6bcf\u4e2a\u5143\u7d20\u4e0e\u53c2\u8003\u5143\u7d20\u8fdb\u884c\u6bd4\u8f83<\/li>\n
  8. \u5982\u679c\u5c0f\u4e8e\u53c2\u8003\u503c\uff0c\u5219\u6839\u636e\u8f83\u5c0f\u6570\u5b57\u7684\u8ba1\u6570\u5668\u7684\u7d22\u5f15\u8fdb\u884c\u4ea4\u6362\u3002\u589e\u52a0\u8f83\u5c0f\u6570\u5b57\u7684\u8ba1\u6570\u5668\u3002<\/li>\n
  9. \u5f53\u5faa\u73af\u5230\u8fbe\u652f\u6301\u5143\u7d20\u65f6\uff0c\u6211\u4eec\u505c\u6b62\u5e76\u6839\u636e\u8f83\u5c0f\u6570\u5b57\u7684\u8ba1\u6570\u5668\u5c06\u652f\u6301\u5143\u7d20\u4e0e\u5143\u7d20\u4ea4\u6362\u3002<\/li>\n
  10. \u6211\u4eec\u5206\u522b\u9488\u5bf9\u5217\u8868\u5de6\u4fa7\u8f83\u5c0f\u7684\u90e8\u5206\u548c\u5217\u8868\u53f3\u4fa7\u8f83\u5927\u7684\u90e8\u5206\u5206\u522b\u8fd0\u884c\u8be5\u7b97\u6cd5\u3002<\/li>\n
  11. \u56e0\u6b64\uff0c\u7531\u4e8e\u68c0\u67e5\u70b9 2\uff0c\u6240\u6709\u9012\u5f52\u8fed\u4ee3\u90fd\u5c06\u5f00\u59cb\u505c\u6b62<\/li>\n
  12. \u83b7\u53d6\u6392\u5e8f\u5217\u8868<\/li>\n<\/ol>\n

    \u5feb\u901f\u6392\u5e8f\u662f\u7531\u83ab\u65af\u79d1\u56fd\u7acb\u5927\u5b66\u7684\u79d1\u5b66\u5bb6 Charles Anthony Richard Hoare \u53d1\u660e\u7684\uff0c\u4ed6\u5728\u5b66\u4e60\u4fc4\u8bed\u540e\uff0c\u5728 Kolmogorov \u5b66\u9662\u5b66\u4e60\u4e86\u8ba1\u7b97\u673a\u7ffb\u8bd1\u4ee5\u53ca\u6982\u7387\u8bba\u3002 1960\u5e74\uff0c\u56e0\u653f\u6cbb\u5371\u673a\u79bb\u5f00\u82cf\u8054\u3002<\/p>\n

    Rust \u4e2d\u7684\u793a\u4f8b\u5b9e\u73b0\uff1a<\/p>\n

    \n
    \n
    \nuse rand::Rng;\n\nfn swap(numbers: &mut [i64], from: usize, to: usize) {\n    let temp = numbers[from];\n    numbers[from] = numbers[to];\n    numbers[to] = temp;\n}\n\nfn quicksort(numbers: &mut [i64], left: usize, right: usize) {\n    if left >= right {\n        return\n    }\n    let length = right - left;\n    if length <= 1 {\n        return\n    }\n    let pivot_index = left + (length \/ 2);\n    let pivot = numbers[pivot_index];\n\n    let last_index = right - 1;\n    swap(numbers, pivot_index, last_index);\n\n    let mut less_insert_index = left;\n\n    for i in left..last_index {\n        if numbers[i] < pivot {\n            swap(numbers, i, less_insert_index);\n            less_insert_index += 1;\n        }\n    }\n    swap(numbers, last_index, less_insert_index);\n    quicksort(numbers, left, less_insert_index);\n    quicksort(numbers, less_insert_index + 1, right);\n}\n\nfn main() {\n    let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];\n    let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];\n\n    let mut rng = rand::thread_rng();\n    for i in 0..numbers.len() {\n        numbers[i] = rng.gen_range(-10..10);\n        reference_numbers[i] = numbers[i];\n    }\n\n    reference_numbers.sort();\n\n  println!(\"Numbers           {:?}\", numbers);\n  let length = numbers.len();\n  quicksort(&mut numbers, 0, length);\n  println!(\"Numbers           {:?}\", numbers);\n  println!(\"Reference numbers {:?}\", reference_numbers);\n\n  if numbers != reference_numbers {\n    println!(\"Validation failed\");\n    std::process::exit(1);\n  }\n  else {\n    println!(\"Validation success!\");\n    std::process::exit(0);\n  }\n}\n<\/code><\/pre>\n<\/div>\n<\/div>\n
    \u5982\u679c\u4e0d\u6e05\u695a\uff0c\u6211\u5efa\u8bae\u89c2\u770b\u5723\u5730\u4e9a\u54e5\u5927\u5b66 Rob Edwards \u7684\u89c6\u9891  https:\/\/www.youtube.com\/watch?v=ZHVk2blR45Q<\/a> \u6700\u7b80\u5355\u3001\u4e00\u6b65\u6b65\u5c55\u793a\u4e86\u7b97\u6cd5\u7684\u672c\u8d28\u548c\u5b9e\u73b0\u3002<\/p>\n
    \u94fe\u63a5<\/h3>\n
    https:\/\/gitlab.com\/demensdeum \/algorithms\/-\/tree\/master\/sortAlgorithms\/quickSort<\/a><\/p>\n
    \u6765\u6e90<\/h3>\n
    https:\/\/www.youtube.com\/watch?v =4s-aG6yGGLU<\/a>
    https:\/\/www.youtube.com\/watch?v=ywWBy6J5gz8<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=Hoixgm4-P4M<\/a>
    \n    https:\/\/ru.wikipedia.org\/wiki\/\u0411\u044b\u0441\u0442\u0440\u0430\u044f_\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=Hoixgm4-P4M<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=XE4VP_8Y0BU<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=MZaf_9IZCrc<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=ZHVk2blR45Q<\/a>
    \n    http:\/\/rosettacode.org\/wiki\/Sorting_algorithms\/Quicksort<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=4s-aG6yGGLU<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=dQw4w9WgXcQ<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=maibrCbZWKw<\/a>
    \n    https:\/\/www.geeksforgeeks.org\/quick-sort\/<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=uXBnyYuwPe8<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    \u5feb\u901f\u6392\u5e8f\u662f\u4e00\u79cd\u5206\u800c\u6cbb\u4e4b\u7684\u6392\u5e8f\u7b97\u6cd5\u3002\u9012\u5f52\u5730\uff0c\u6211\u4eec\u9010\u4e2a\u89e3\u6790\u6570\u5b57\u6570\u7ec4\uff0c\u5c06\u6240\u9009\u53c2\u8003\u5143\u7d20\u4e2d\u7684\u6570\u5b57\u6309\u7167\u8f83\u5c0f\u548c\u8f83\u5927\u7684\u987a\u5e8f\u653e\u7f6e\uff0c\u5e76\u5c06\u53c2\u8003\u5143\u7d20\u672c\u8eab\u63d2\u5165\u5230\u5b83\u4eec\u4e4b\u95f4\u7684\u622a\u6b62\u4f4d\u7f6e\u3002\u7ecf\u8fc7\u51e0\u6b21\u9012\u5f52\u8fed\u4ee3\u540e\uff0c\u60a8\u5c06\u5f97\u5230\u4e00\u4e2a\u6392\u5e8f\u5217\u8868\u3002\u65f6\u95f4\u590d\u6742\u5ea6 O(n2)\u3002 \u65b9\u6848\uff1a \u6211\u4eec\u9996\u5148\u4ece\u5916\u90e8\u83b7\u53d6\u5143\u7d20\u5217\u8868\uff0c\u5373\u6392\u5e8f\u8fb9\u754c\u3002\u7b2c\u4e00\u6b65\uff0c\u6392\u5e8f\u8fb9\u754c\u5c06\u4ece\u5934\u5230\u5c3e\u3002 \u68c0\u67e5\u8d77\u59cb\u8fb9\u754c\u548c\u7ed3\u675f\u8fb9\u754c\u662f\u5426\u76f8\u4ea4\uff1b\u5982\u679c\u53d1\u751f\u8fd9\u79cd\u60c5\u51b5\uff0c\u5219\u8be5\u7ed3\u675f\u4e86 \u4ece\u5217\u8868\u4e2d\u9009\u62e9\u67d0\u4e2a\u5143\u7d20\u5e76\u5c06\u5176\u547d\u540d\u4e3a\u6570\u636e\u900f\u89c6 \u5c06\u5176\u5411\u53f3\u79fb\u52a8\u5230\u6700\u540e\u4e00\u4e2a\u7d22\u5f15\u5904\u7684\u672b\u5c3e\uff0c\u8fd9\u6837\u5c31\u4e0d\u4f1a\u59a8\u788d \u521b\u5efa\u4e00\u4e2a*\u8f83\u5c0f\u6570\u5b57*\u4ecd\u7b49\u4e8e\u96f6\u7684\u8ba1\u6570\u5668 \u4ece\u5de6\u5230\u53f3\u5faa\u73af\u904d\u5386\u5217\u8868\uff0c\u76f4\u5230\u5f15\u7528\u5143\u7d20\u6240\u5728\u7684\u6700\u540e\u4e00\u4e2a\u7d22\u5f15\uff08\u5305\u62ec\u8be5\u7d22\u5f15\uff09 \u6211\u4eec\u5c06\u6bcf\u4e2a\u5143\u7d20\u4e0e\u53c2\u8003\u5143\u7d20\u8fdb\u884c\u6bd4\u8f83 \u5982\u679c\u5c0f\u4e8e\u53c2\u8003\u503c\uff0c\u5219\u6839\u636e\u8f83\u5c0f\u6570\u5b57\u7684\u8ba1\u6570\u5668\u7684\u7d22\u5f15\u8fdb\u884c\u4ea4\u6362\u3002\u589e\u52a0\u8f83\u5c0f\u6570\u5b57\u7684\u8ba1\u6570\u5668\u3002 \u5f53\u5faa\u73af\u5230\u8fbe\u652f\u6301\u5143\u7d20\u65f6\uff0c\u6211\u4eec\u505c\u6b62\u5e76\u6839\u636e\u8f83\u5c0f\u6570\u5b57\u7684\u8ba1\u6570\u5668\u5c06\u652f\u6301\u5143\u7d20\u4e0e\u5143\u7d20\u4ea4\u6362\u3002 \u6211\u4eec\u5206\u522b\u9488\u5bf9\u5217\u8868\u5de6\u4fa7\u8f83\u5c0f\u7684\u90e8\u5206\u548c\u5217\u8868\u53f3\u4fa7\u8f83\u5927\u7684\u90e8\u5206\u5206\u522b\u8fd0\u884c\u8be5\u7b97\u6cd5\u3002 \u56e0\u6b64\uff0c\u7531\u4e8e\u68c0\u67e5\u70b9 2\uff0c\u6240\u6709\u9012\u5f52\u8fed\u4ee3\u90fd\u5c06\u5f00\u59cb\u505c\u6b62 \u83b7\u53d6\u6392\u5e8f\u5217\u8868 \u5feb\u901f\u6392\u5e8f\u662f\u7531\u83ab\u65af\u79d1\u56fd\u7acb\u5927\u5b66\u7684\u79d1\u5b66\u5bb6 Charles Anthony Richard Hoare \u53d1\u660e\u7684\uff0c\u4ed6\u5728\u5b66\u4e60\u4fc4\u8bed\u540e\uff0c\u5728 Kolmogorov \u5b66\u9662\u5b66\u4e60\u4e86\u8ba1\u7b97\u673a\u7ffb\u8bd1\u4ee5\u53ca\u6982\u7387\u8bba\u3002 1960\u5e74\uff0c\u56e0\u653f\u6cbb\u5371\u673a\u79bb\u5f00\u82cf\u8054\u3002 Rust \u4e2d\u7684\u793a\u4f8b\u5b9e\u73b0\uff1a use rand::Rng; fn swap(numbers: &mut [i64], from: usize, to: usize) { let temp = numbers[from]; numbers[from] = numbers[to]; numbers[to] = temp; } fn quicksort(numbers: &mut [i64], left: usize,Continue reading “\u5feb\u901f\u6392\u5e8f”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,199,190],"class_list":["post-3344","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-quicksort","tag-sorting","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"zh","enabled_languages":["en","ru","zh","de","fr","ja","pt"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/posts\/3344","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/comments?post=3344"}],"version-history":[{"count":20,"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/posts\/3344\/revisions"}],"predecessor-version":[{"id":3880,"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/posts\/3344\/revisions\/3880"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/media?parent=3344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/categories?post=3344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/zh\/wp-json\/wp\/v2\/tags?post=3344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}