算法图解/chap04-快速排序.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第4章 快速排序\n",
    "\n",
    "本章的重点是使用学到的新技能来解决问题。我们将探索分而治之（divide and conquer，D&C）——一种著名的递归式问题解决方法。\n",
    "\n",
    "本书将深入算法的核心。只能解决一种问题的算法毕竟用处有限，而D&C提供了解决问题的思路，是另一个可供你使用的工具。面对新问题时，你不再束手无策，而是自问：“使用分而治\n",
    "之能解决吗？”\n",
    "\n",
    "在本章末尾，你将学习第一个重要的D&C算法——快速排序。快速排序是一种排序算法，速度比第2章介绍的选择排序快得多，实属优雅代码的典范。\n",
    "\n",
    "## 4.1 分而治之\n",
    "\n",
    "如何将一块地均匀地分成方块，并确保分出的方块是最大的呢？使用D&C策略！D&C算法是递归的。使用D&C解决问题的过程包括两个步骤。\n",
    "\n",
    "- (1) 找出基线条件，这种条件必须尽可能简单。\n",
    "- (2) 不断将问题分解（或者说缩小规模），直到符合基线条件。\n",
    "\n",
    "假设你是农场主，有一小块土地。1680m x 640m\n",
    "\n",
    "首先，找出基线条件。最容易处理的情况是，一条边的长度是另一条边的整数倍。\n",
    "\n",
    "现在需要找出递归条件，这正是D&C的用武之地。根据D&C的定义，每次递归调用都必须缩小问题的规模。如何缩小前述问题的规模呢？我们首先找出这块地可容纳的最大方块。\n",
    "\n",
    "你可以从这块地中划出两个640 m×640 m的方块，同时余下一小块地。现在是顿悟时刻：何不对余下的那一小块地使用相同的算法呢？\n",
    "\n",
    "最初要划分的土地尺寸为1680 m×640 m，而现在要划分的土地更小，为640 m×400 m。适用于这小块地的最大方块，也是适用于整块地的最大方块。换言之，你将均匀划分1680 m×640 m\n",
    "土地的问题，简化成了均匀划分640 m×400 m土地的问题！\n",
    "```\n",
    "1680x640\n",
    "400x640\n",
    "400x240\n",
    "160x240\n",
    "160x80\n",
    "```\n",
    "\n",
    "因此，对于最初的那片土地，适用的最大方块为80 m× 80 m。\n",
    "\n",
    "这里重申一下D&C的工作原理：\n",
    "- (1) 找出简单的基线条件；\n",
    "- (2) 确定如何缩小问题的规模，使其符合基线条件。\n",
    "D&C并非可用于解决问题的算法，而是一种解决问题的思路。我们再来看一个例子。\n",
    "\n",
    "给定一个数字数组，计算数字之和：\n",
    "\n",
    "循环方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "def sum_array(arr):\n",
    "    total = 0\n",
    "    for x in arr:\n",
    "        total += x\n",
    "    return total\n",
    "\n",
    "print(sum_array([1, 2, 3, 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "但如何使用递归函数来完成这种任务呢？\n",
    "\n",
    "- 第一步：找出基线条件。最简单的数组什么样呢？请想想这个问题，再接着往下读。如果数组不包含任何元素或只包含一个元素，计算总和将非常容易。因此这就是基线条件。\n",
    "- 第二步：每次递归调用都必须离空数组更近一步。 sum([2,4,6) = 2 + sum([4,6])\n",
    "\n",
    "![et4Ac8.png](https://s2.ax1x.com/2019/07/31/et4Ac8.png)\n",
    "\n",
    "这个函数的运行过程如下:\n",
    "\n",
    "[![et48jU.png](https://s2.ax1x.com/2019/07/31/et48jU.png)](https://imgchr.com/i/et48jU)\n",
    "\n",
    "**编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_array(arr):\n",
    "    if len(arr) == 0:\n",
    "        return 0\n",
    "    if len(arr) == 1:\n",
    "        return arr[0]\n",
    "    else:\n",
    "        return arr[0] + sum_array(arr[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_array([2,4,6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.2 快速排序 Quick Sort\n",
    "\n",
    "快速排序是一种常用的排序算法，比选择排序快得多。例如，C语言标准库中的函数 qsort实现的就是快速排序。快速排序也使用了D&C。\n",
    "\n",
    "基线条件为数组为空或只包含一个元素。在这种情况下，只需原样返回数组——根本就不用排序。\n",
    "\n",
    "```\n",
    "def quicksort(array):\n",
    "    if len(array) < 2:\n",
    "        return array\n",
    "```\n",
    "\n",
    "快速排序，步骤如下。\n",
    "\n",
    "- (1) 选择基准值。\n",
    "- (2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。\n",
    "- (3) 对这两个子数组进行快速排序。\n",
    "\n",
    "对于快速排序，可使用类似的推理。在基线条件中，我证明这种算法对空数组或包含一个元素的数组管用。在归纳条件中，我证明如果快速排序对包含一个元素的数组管用，对包含两个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用，以此类推。因此，我可以说，快速排序对任何长度的数组都管用。这里不再深入讨论归纳证明，但它很有趣，并与D&C协同发挥作用。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 10]\n"
     ]
    }
   ],
   "source": [
    "def quicksort(array):\n",
    "    if len(array) < 2:\n",
    "        return array   # 基线条件：为空或只包含一个元素的数组是“有序”的\n",
    "    else:\n",
    "        pivot = array[0] # 递归条件\n",
    "        less = [i for i in array[1:] if i <= pivot] #由所有小于基准值的元素组成的子数组\n",
    "        greater = [i for i in array[1:] if i > pivot] #由所有大于基准值的元素组成的子数组\n",
    "        return quicksort(less) + [pivot] + quicksort(greater)\n",
    "\n",
    "print(quicksort([10, 5, 2, 3]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "还有一种名为合并排序（merge sort）（或称归并排序）的排序算法，其运行时间为O(n log n)，比选择排序快得多！快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n 2 )。与选择排序一样慢！但这是最糟情况。在平均情况下，快速排序的运行时间为O(n log n)。\n",
    "\n",
    "平均情况和最糟情况：\n",
    "\n",
    "在这个示例中，层数为O(log n)（用技术术语说，调用栈的高度为O(log n)），而每层需要的时间为O(n)。因此整个算法需要的时间为O(n) * O(log n) = O(n log n)。这就是最佳情况。\n",
    "\n",
    "在最糟情况下，有O(n)层，因此该算法的运行时间为O(n) * O(n) = O(n 2 )。\n",
    "\n",
    "这里要告诉你的是，最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(n log n)。快速排序是最快的排序算法之一，也是D&C典范。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 归并排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (system-wide)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}