{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# \u7b97\u6cd5\u56fe\u89e3 \u2014 \u67e5\u627e\u4e0e\u6392\u5e8f\u7bc7\n",
    "\n",
    "\u672c\u7b14\u8bb0\u672c\u662f [grokking_algorithms.html](grokking_algorithms.html) \u4e2d\n",
    "**\u67e5\u627e**\u4e0e**\u6392\u5e8f**\u4e24\u8282\u7684\u52a8\u624b\u5b9e\u8df5\u7248\u3002\n",
    "\n",
    "\u6bcf\u4e2a\u4ee3\u7801\u5355\u5143\u683c\u524d\u9762\u90fd\u6709 **\ud83d\udc0d \u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027** \u8bf4\u660e\uff0c\n",
    "\u4ee3\u7801\u6bcf\u4e00\u884c\u90fd\u5e26\u6ce8\u91ca\u3002\n",
    "\n",
    "**\u672c\u7b14\u8bb0\u672c\u6db5\u76d6\uff1a**\n",
    "1. \u4e8c\u5206\u67e5\u627e\n",
    "2. \u9009\u62e9\u6392\u5e8f\n",
    "3. \u5f52\u5e76\u6392\u5e8f\n",
    "4. \u5feb\u901f\u6392\u5e8f\n",
    "5. \u4e09\u79cd\u6392\u5e8f\u7b97\u6cd5\u7684\u540c\u53f0\u8ba1\u65f6\u5bf9\u6bd4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. \u4e8c\u5206\u67e5\u627e\n",
    "\n",
    "\u770b\u6392\u597d\u5e8f\u5217\u8868\u7684\u4e2d\u95f4\u5143\u7d20\u3002\u76ee\u6807\u66f4\u5c0f\uff1f\u6254\u6389\u53f3\u534a\u3002\u76ee\u6807\u66f4\u5927\uff1f\u6254\u6389\u5de6\u534a\u3002\n",
    "\u5426\u5219\u5c31\u627e\u5230\u4e86\u3002\u6bcf\u4e00\u6b65\u90fd\u628a\u641c\u7d22\u8303\u56f4\u780d\u6389\u4e00\u534a \u2014\u2014 \u5341\u4ebf\u4e2a\u5143\u7d20\u53ea\u9700\u8981\n",
    "\u7ea6 30 \u6b21\u731c\u6d4b\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `while \u6761\u4ef6:` \u53ea\u8981\u6761\u4ef6\u4e3a\u771f\u5c31\u53cd\u590d\u6267\u884c\u3002`//` \u662f**\u6574\u6570\u9664\u6cd5**\uff08\u5411\u4e0b\u53d6\u6574\uff09\uff1a`7 // 2 == 3`\uff0c\u4e0d\u662f 3.5\u3002`return None` \u663e\u5f0f\u8fd4\u56de\u300c\u65e0\u503c\u300d\u6807\u8bb0\u3002`lo, hi = 0, len(arr) - 1` \u7528\u9017\u53f7\u4e00\u6b21\u6027\u7ed9\u4e24\u4e2a\u53d8\u91cf\u8d4b\u503c\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(arr, target):\n",
    "    lo, hi = 0, len(arr) - 1              # \u641c\u7d22\u8303\u56f4 [lo, hi]\uff0c\u5305\u542b\u4e24\u7aef\n",
    "    while lo <= hi:                       # \u53ea\u8981\u8303\u56f4\u975e\u7a7a\u5c31\u7ee7\u7eed\n",
    "        mid = (lo + hi) // 2              # \u6574\u6570\u4e2d\u70b9\n",
    "        if arr[mid] == target:\n",
    "            return mid                    # \u627e\u5230\u4e86\uff01\u8fd4\u56de\u4e0b\u6807\n",
    "        if arr[mid] < target:\n",
    "            lo = mid + 1                  # \u76ee\u6807\u5728\u4e0a\u534a\u6bb5\n",
    "        else:\n",
    "            hi = mid - 1                  # \u76ee\u6807\u5728\u4e0b\u534a\u6bb5\n",
    "    return None                           # \u8303\u56f4\u7a7a\u4e86 \u2014\u2014 \u4e0d\u5728\u5217\u8868\u4e2d\n",
    "\n",
    "nums = [1, 3, 5, 7, 9, 11, 13, 15]\n",
    "print(\"Find 7:\",  binary_search(nums, 7))\n",
    "print(\"Find 15:\", binary_search(nums, 15))\n",
    "print(\"Find 10:\", binary_search(nums, 10))   # \u4e0d\u5728\u5217\u8868\u91cc \u2192 None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### \u770b\u5b83\u4e00\u6b65\u6b65\u6536\u655b\n",
    "\n",
    "\u52a0\u4e00\u884c print\uff0c\u4f60\u5c31\u80fd\u770b\u5230\u641c\u7d22\u8303\u56f4\u5982\u4f55\u9010\u6b65\u7f29\u5c0f\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u548c\u4e0a\u9762\u540c\u4e00\u4e2a\u7b97\u6cd5\uff0c\u53ea\u662f\u591a\u4e86 `step` \u8ba1\u6570\u5668\u548c\u5faa\u73af\u5185\u7684\u6253\u5370\u3002`f\"...{step:>3}...\"` \u628a step \u53f3\u5bf9\u9f50\u5360 3 \u683c\u3002\u5b57\u7b26\u4e32\u91cc\u7684 `\\n` \u662f\u6362\u884c\u7b26\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search_verbose(arr, target):\n",
    "    lo, hi = 0, len(arr) - 1\n",
    "    step = 0                              # \u5df2\u7ecf\u731c\u8fc7\u51e0\u6b21\n",
    "    while lo <= hi:\n",
    "        step += 1                         # \u53c8\u731c\u4e00\u6b21\n",
    "        mid = (lo + hi) // 2\n",
    "        print(f\"step {step}: lo={lo:>3} hi={hi:>3} mid={mid:>3} arr[mid]={arr[mid]}\")\n",
    "        if arr[mid] == target:\n",
    "            return mid\n",
    "        if arr[mid] < target:\n",
    "            lo = mid + 1\n",
    "        else:\n",
    "            hi = mid - 1\n",
    "    return None\n",
    "\n",
    "big_list = list(range(0, 1000, 7))        # 0, 7, 14, 21, ..., 994 \u2014\u2014 \u5df2\u6392\u597d\u5e8f\n",
    "idx = binary_search_verbose(big_list, 763)\n",
    "print(f\"\\nFound at index {idx}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### \u7ebf\u6027 vs \u4e8c\u5206 \u2014\u2014 \u5dee\u8ddd\u5230\u5e95\u6709\u591a\u5927\uff1f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `break` \u63d0\u524d\u8df3\u51fa\u5faa\u73af\u3002`1e6` \u662f\u79d1\u5b66\u8ba1\u6570\u6cd5\uff0c\u7b49\u4e8e `1,000,000`\u3002\u6211\u4eec\u628a\u7ecf\u8fc7\u7684\u79d2\u6570\u4e58 `1e6` \u8f6c\u6210\u5fae\u79d2\u3002`max(x, 0.1)` \u907f\u514d\u5728\u6d4b\u91cf\u7ed3\u679c\u63a5\u8fd1 0 \u65f6\u51fa\u73b0\u300c\u9664\u4ee5\u96f6\u300d\u7684\u95ee\u9898\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "n = 1_000_000\n",
    "sorted_data = list(range(n))              # \u4e00\u767e\u4e07\u4e2a\u6709\u5e8f\u6574\u6570\n",
    "target = n - 1                            # \u6700\u574f\u60c5\u51b5\uff1a\u6700\u540e\u4e00\u4e2a\u5143\u7d20\n",
    "\n",
    "t0 = time.perf_counter()\n",
    "for i, x in enumerate(sorted_data):       # \u7ebf\u6027\u626b\u63cf\n",
    "    if x == target:\n",
    "        break                             # \u4e00\u627e\u5230\u5c31\u505c\n",
    "linear = (time.perf_counter() - t0) * 1e6 # \u5fae\u79d2\n",
    "\n",
    "t0 = time.perf_counter()\n",
    "binary_search(sorted_data, target)\n",
    "binary = (time.perf_counter() - t0) * 1e6\n",
    "\n",
    "print(f\"linear search:  {linear:>8.1f} \u00b5s\")\n",
    "print(f\"binary search:  {binary:>8.1f} \u00b5s\")\n",
    "print(f\"binary is ~{linear / max(binary, 0.1):.0f}\u00d7 faster\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. \u9009\u62e9\u6392\u5e8f\n",
    "\n",
    "\u904d\u5386\u5217\u8868\uff0c\u627e\u5230\u6700\u5c0f\u503c\uff0c\u8ddf\u6700\u524d\u9762\u4ea4\u6362\u3002\u5bb9\u6613\u7406\u89e3\uff0c\u6c38\u8fdc\u662f O(n\u00b2)\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `range(start, stop)` \u751f\u6210 `start, start+1, ..., stop-1`\uff08\u4e0d\u542b stop\uff09\u3002`arr[i], arr[j] = arr[j], arr[i]` \u662f Python \u7684\u4e00\u884c\u5143\u7ec4\u5f0f\u4ea4\u6362\u3002`len(arr)` \u8fd4\u56de\u4efb\u4f55\u5e8f\u5217\u7684\u957f\u5ea6\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n - 1):                # i \u662f\u4e0b\u4e00\u4e2a\u8981\u586b\u7684\u4f4d\u7f6e\n",
    "        min_idx = i                       # \u5148\u5047\u8bbe\u5f53\u524d\u4f4d\u7f6e\u5c31\u662f\u6700\u5c0f\n",
    "        for j in range(i + 1, n):         # \u626b\u63cf\u540e\u9762\u672a\u6392\u5e8f\u7684\u90e8\u5206\n",
    "            if arr[j] < arr[min_idx]:\n",
    "                min_idx = j               # \u627e\u5230\u4e86\u66f4\u5c0f\u7684\n",
    "        arr[i], arr[min_idx] = arr[min_idx], arr[i]   # \u4ea4\u6362\u5230\u4f4d\n",
    "    return arr\n",
    "\n",
    "print(selection_sort([5, 2, 8, 1, 4]))\n",
    "print(selection_sort([64, 25, 12, 22, 11]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**\u770b\u5b83\u8d8a\u6765\u8d8a\u6162\u3002**\u5bf9\u8d8a\u6765\u8d8a\u5927\u7684\u968f\u673a\u5217\u8868\u8ba1\u65f6\u3002\u671f\u671b\uff1a\u5927\u5c0f\u6bcf\u7ffb\u4e00\u500d\uff0c\n",
    "\u8017\u65f6\u5927\u81f4\u53d8\u4e3a*\u56db\u500d*\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `random.random()` \u8fd4\u56de [0.0, 1.0) \u4e4b\u95f4\u7684\u6d6e\u70b9\u6570\u3002\u628a\u7ecf\u8fc7\u7684\u79d2\u6570\u4e58 1000 \u5c31\u5f97\u5230\u6beb\u79d2\uff08ms\uff09\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random, time\n",
    "\n",
    "random.seed(0)                            # \u8ba9\u7ed3\u679c\u53ef\u590d\u73b0\n",
    "print(f\"{'size':>8}  {'time':>10}\")\n",
    "for n in [500, 1000, 2000, 4000, 8000]:   # \u6bcf\u6b21\u7ffb\u500d\n",
    "    data = [random.random() for _ in range(n)]    # \u968f\u673a\u6d6e\u70b9\u6570\u5217\u8868\n",
    "    t0 = time.perf_counter()\n",
    "    selection_sort(data)\n",
    "    elapsed = time.perf_counter() - t0\n",
    "    print(f\"{n:>8}  {elapsed*1000:>8.1f} ms\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. \u5f52\u5e76\u6392\u5e8f\n",
    "\n",
    "\u628a\u5217\u8868\u5bf9\u534a\u5207\uff0c\u9012\u5f52\u6392\u597d\u6bcf\u4e00\u534a\uff0c\u7136\u540e\u5408\u5e76\u3002\u6c38\u8fdc O(n log n)\uff0c\n",
    "\u800c\u4e14**\u7a33\u5b9a**\uff08\u76f8\u7b49\u5143\u7d20\u4fdd\u6301\u539f\u987a\u5e8f\uff09\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u5207\u7247\uff1a`arr[:mid]` \u662f\u4e0b\u6807 `mid` \u4e4b\u524d\u7684\u90e8\u5206\uff1b`arr[mid:]` \u662f\u4ece `mid` \u5f00\u59cb\u5230\u672b\u5c3e\u7684\u90e8\u5206\u3002\u90fd\u4f1a\u751f\u6210\u65b0\u5217\u8868\u3002`i = j = 0` \u628a 0 \u540c\u65f6\u8d4b\u7ed9\u4e24\u4e2a\u53d8\u91cf\u3002`result.extend(seq)` \u628a seq \u91cc\u7684\u6bcf\u4e2a\u5143\u7d20\u9010\u4e2a\u8ffd\u52a0\u5230 result \u4e0a\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort(arr):\n",
    "    if len(arr) <= 1:\n",
    "        return arr                        # \u57fa\u7840\u60c5\u51b5\uff1a\u5df2\u7ecf\u6709\u5e8f\n",
    "    mid = len(arr) // 2\n",
    "    left  = merge_sort(arr[:mid])         # \u9012\u5f52\u6392\u597d\u5de6\u534a\n",
    "    right = merge_sort(arr[mid:])         # \u9012\u5f52\u6392\u597d\u53f3\u534a\n",
    "    return merge(left, right)             # \u5408\u5e76\u4e24\u4e2a\u6709\u5e8f\u6bb5\n",
    "\n",
    "def merge(left, right):\n",
    "    result = []\n",
    "    i = j = 0                             # i \u5728 left \u4e0a\uff0cj \u5728 right \u4e0a\n",
    "    while i < len(left) and j < len(right):\n",
    "        if left[i] <= right[j]:           # <= \u4fdd\u8bc1\u7a33\u5b9a\n",
    "            result.append(left[i]); i += 1\n",
    "        else:\n",
    "            result.append(right[j]); j += 1\n",
    "    result.extend(left[i:])               # \u628a\u5269\u4e0b\u7684\u5168\u5012\u8fdb\u6765\n",
    "    result.extend(right[j:])\n",
    "    return result\n",
    "\n",
    "print(merge_sort([38, 27, 43, 3, 9, 82, 10]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### \u9a8c\u8bc1\u7a33\u5b9a\u6027\n",
    "\n",
    "\u5bf9 `(\u6210\u7ee9, \u540d\u5b57)` \u5143\u7ec4\u53ea\u6309\u6210\u7ee9\u6392\u5e8f\u3002\u7a33\u5b9a\u6392\u5e8f\u4f1a\u8ba9\u540c\u5206\u5b66\u751f\u4fdd\u6301\n",
    "\u539f\u5148\u7684\u5b57\u6bcd\u987a\u5e8f\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u50cf `(\"B\", \"alice\")` \u8fd9\u6837\u7684\u5143\u7ec4\u9ed8\u8ba4\u6309\u5143\u7d20\u9010\u4e2a\u6bd4\u8f83\u3002\u5728 `merge` \u4e2d\u6bd4\u8f83\u5143\u7ec4\u65f6\uff0cPython \u5148\u6bd4\u7b2c\u4e00\u4e2a\u5143\u7d20 \u2014\u2014 \u8fd9\u5c31\u662f\u4e3a\u4ec0\u4e48\u6309\u5143\u7ec4\u6392\u5e8f\u4e3b\u8981\u6309\u6210\u7ee9\u6392\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "students = [(\"B\", \"alice\"), (\"A\", \"bob\"), (\"B\", \"charlie\"),\n",
    "            (\"A\", \"dave\"), (\"B\", \"eve\")]\n",
    "\n",
    "# \u6309\u5143\u7ec4\u6392 \u2014\u2014 \u4e3b\u8981\u6309\u6210\u7ee9\uff08\u7b2c\u4e00\u4e2a\u5143\u7d20\uff09\u3002\n",
    "sorted_students = merge_sort(students)\n",
    "for s in sorted_students:\n",
    "    print(s)\n",
    "\n",
    "# A \u7ec4\u4fdd\u6301 bob \u5728 dave \u4e4b\u524d\n",
    "# B \u7ec4\u4fdd\u6301 alice\u3001charlie\u3001eve \u7684\u539f\u987a\u5e8f \u2014\u2014 \u56e0\u4e3a\u662f**\u7a33\u5b9a**\u6392\u5e8f\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. \u5feb\u901f\u6392\u5e8f\n",
    "\n",
    "\u9009\u4e00\u4e2a\u57fa\u51c6\u503c\uff08pivot\uff09\u3002\u628a\u5176\u4f59\u5143\u7d20\u5206\u6210\"\u6bd4\u57fa\u51c6\u5c0f\u7684\"\u548c\"\u6bd4\u57fa\u51c6\u5927\u7684\"\n",
    "\u4e24\u5806\u3002\u5bf9\u4e24\u8fb9\u9012\u5f52\u3002\u5e73\u5747 O(n log n)\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u5e26\u6761\u4ef6\u7684\u5217\u8868\u63a8\u5bfc\u5f0f\uff1a`[x for x in seq if \u6d4b\u8bd5(x)]` \u751f\u6210\u6240\u6709\u6ee1\u8db3\u6761\u4ef6\u7684 x \u7ec4\u6210\u7684\u65b0\u5217\u8868\u3002`arr[1:]` \u662f\u9664\u4e86\u7b2c\u4e00\u4e2a\u5143\u7d20\u4e4b\u5916\u7684\u6240\u6709\u5143\u7d20\u3002\u5217\u8868\u7528 `+` \u62fc\u63a5\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort(arr):\n",
    "    if len(arr) < 2:\n",
    "        return arr                                    # 0 \u6216 1 \u4e2a\u5143\u7d20\u5df2\u7ecf\u6709\u5e8f\n",
    "    pivot = arr[0]                                    # \u9009\u7b2c\u4e00\u4e2a\u5143\u7d20\u4f5c\u4e3a\u57fa\u51c6\n",
    "    less    = [x for x in arr[1:] if x <= pivot]      # \u4e0d\u5927\u4e8e pivot \u7684\u5143\u7d20\n",
    "    greater = [x for x in arr[1:] if x >  pivot]      # \u5927\u4e8e pivot \u7684\u5143\u7d20\n",
    "    return quicksort(less) + [pivot] + quicksort(greater)   # \u4e24\u8fb9\u5404\u81ea\u6392\u597d\uff0cpivot \u5939\u4e2d\u95f4\n",
    "\n",
    "print(quicksort([3, 6, 1, 8, 2, 4]))\n",
    "print(quicksort([64, 25, 12, 22, 11, 90, 4, 18, 33, 7]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### \u770b\u5206\u533a\u8fc7\u7a0b\n",
    "\n",
    "\u52a0\u4e0a print \u8bed\u53e5\uff0c\u89c2\u5bdf\u5feb\u901f\u6392\u5e8f\u5728\u6bcf\u4e00\u5c42\u9012\u5f52\u4e2d\u5982\u4f55\u628a\u5217\u8868\u5207\u5f00\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** `depth=0` \u662f\u9ed8\u8ba4\u53c2\u6570\u503c\u3002`\"  \" * depth` \u628a\u4e24\u4e2a\u7a7a\u683c\u91cd\u590d `depth` \u6b21 \u2014\u2014\u7528\u6765\u6309\u9012\u5f52\u5c42\u7ea7\u7f29\u8fdb\u6253\u5370\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort_verbose(arr, depth=0):\n",
    "    indent = \"  \" * depth                             # \u6bcf\u4e00\u5c42\u9012\u5f52\u591a\u7f29\u8fdb 2 \u683c\n",
    "    if len(arr) < 2:\n",
    "        if arr:\n",
    "            print(f\"{indent}base: {arr}\")\n",
    "        return arr\n",
    "    pivot = arr[0]\n",
    "    less    = [x for x in arr[1:] if x <= pivot]\n",
    "    greater = [x for x in arr[1:] if x >  pivot]\n",
    "    print(f\"{indent}pivot={pivot}  less={less}  greater={greater}\")\n",
    "    return quicksort_verbose(less, depth + 1) + [pivot] + quicksort_verbose(greater, depth + 1)\n",
    "\n",
    "print(quicksort_verbose([3, 6, 1, 8, 2, 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. \u540c\u53f0\u5bf9\u51b3 \u2014\u2014 \u4e09\u79cd\u6392\u5e8f\u7b97\u6cd5\u5bf9\u540c\u4e00\u6570\u636e\n",
    "\n",
    "\u7ed9\u4e09\u79cd\u6392\u5e8f\u52a0\u4e0a Python \u5185\u7f6e `sorted()`\uff08Timsort\uff09\u5bf9\u540c\u4e00\u4efd\u968f\u673a\u5217\u8868\n",
    "\u8ba1\u65f6\u3002\u770b\u770b\u9009\u62e9\u6392\u5e8f\u5982\u4f55\u968f\u7740\u5217\u8868\u53d8\u5927\u88ab\u8d8a\u7529\u8d8a\u8fdc\u3002"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> \ud83d\udc0d **\u672c\u5355\u5143\u683c\u7528\u5230\u7684 Python \u7279\u6027\uff1a** \u6211\u4eec\u628a\u51fd\u6570\u5f53\u4f5c\u666e\u901a\u503c\u4f20\u9012\uff1a`time_sort(selection_sort, data)` \u628a\u51fd\u6570\u672c\u8eab\u4f5c\u4e3a\u53c2\u6570\u4f20\u7ed9\u8f85\u52a9\u51fd\u6570\u3002\u8f85\u52a9\u51fd\u6570\u5185\u90e8\u7528 `fn(...)` \u8c03\u7528\u4f20\u8fdb\u6765\u7684\u51fd\u6570\u3002`list(data)` \u590d\u5236\u4e00\u4efd\uff0c\u8ba9\u6bcf\u4e2a\u6392\u5e8f\u90fd\u62ff\u5230\u5168\u65b0\u5217\u8868\u3002"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random, time\n",
    "\n",
    "def time_sort(fn, data):\n",
    "    t0 = time.perf_counter()\n",
    "    fn(list(data))                        # \u7528\u4f20\u8fdb\u6765\u7684\u51fd\u6570\u5904\u7406\u4e00\u4efd\u65b0\u62f7\u8d1d\n",
    "    return (time.perf_counter() - t0) * 1000   # \u6beb\u79d2\n",
    "\n",
    "random.seed(0)\n",
    "print(f\"{'size':>6}  {'selection':>10}  {'merge':>8}  {'quick':>8}  {'sorted()':>10}\")\n",
    "for n in [500, 1000, 2000, 4000]:\n",
    "    data = [random.random() for _ in range(n)]\n",
    "    sel = time_sort(selection_sort, data)\n",
    "    mrg = time_sort(merge_sort,     data)\n",
    "    qck = time_sort(quicksort,      data)\n",
    "    blt = time_sort(sorted,         data)            # Python \u5185\u7f6e Timsort\n",
    "    print(f\"{n:>6}  {sel:>8.1f} ms  {mrg:>6.1f} ms  {qck:>6.1f} ms  {blt:>8.2f} ms\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**\u7ed3\u8bba\uff1a**Python \u5185\u7f6e `sorted()` \u5927\u83b7\u5168\u80dc \u2014\u2014 \u5b83\u7528 C \u5b9e\u73b0\uff0c\n",
    "\u800c\u4e14\u4f1a\u5229\u7528\u771f\u5b9e\u6570\u636e\u4e2d\u7684\u89c4\u5f8b\u3002\u751f\u4ea7\u4ee3\u7801\u91cc\u6c38\u8fdc\u4e0d\u8981\u81ea\u5df1\u5199\u6392\u5e8f\u3002"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.x"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}