排序算法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。\n",
    "+ 关于时间复杂度：\n",
    "    + 平方阶 (O(n2)) 排序：各类简单排序，直接插入、直接选择和冒泡排序；\n",
    "    + 线性对数阶 (O(nlog2n)) 排序：快速排序、堆排序和归并排序；\n",
    "    + O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数：希尔排序；\n",
    "    + 线性阶 (O(n)) 排序：基数排序，此外还有桶、箱排序。\n",
    "\n",
    "+ 关于稳定性：\n",
    "    + 排序后 2 个相等键值的顺序和排序之前它们的顺序相同。\n",
    "    + 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。\n",
    "    + 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。\n",
    "\n",
    "+ 名词解释：\n",
    "    + n：数据规模\n",
    "    + k：“桶”的个数\n",
    "    + In-place：占用常数内存，不占用额外内存\n",
    "    + Out-place：占用额外内存\n",
    " \n",
    "![](./imgs/排序算法.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 冒泡排序\n",
    "冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。\n",
    "## 算法步骤\n",
    "+ 比较相邻的元素。如果第一个比第二个大，就交换他们两个。\n",
    "+ 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。\n",
    "+ 针对所有的元素重复以上的步骤，除了最后一个。\n",
    "+ 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比\n",
    "\n",
    "## 动图演示\n",
    "![](./imgs/bubblesort.gif)\n",
    "\n",
    "## 代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 3, 4, 5, 5, 6, 7, 9, 10]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [1, 4, 5, 1, 10, 9, 7, 6, 3, 5]\n",
    "\n",
    "def bubble_sort(l):\n",
    "    for i in range(len(l)-1):\n",
    "        for i in range(len(l)-1):\n",
    "            if l[i] > l[i+1]:\n",
    "                l[i+1], l[i] = l[i], l[i+1]\n",
    "    return l\n",
    "\n",
    "bubble_sort(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 选择排序\n",
    "选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。\n",
    "\n",
    "## 算法步骤\n",
    "+ 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置\n",
    "+ 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。\n",
    "+ 重复第二步，直到所有元素均排序完毕。  \n",
    "\n",
    "## 动图演示\n",
    "![](./imgs/selectsort.gif)\n",
    "\n",
    "## 代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 3, 4, 5, 5, 6, 7, 9, 10]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def select_sort(l):\n",
    "    for i in range(len(l)-1):\n",
    "        min_index = i\n",
    "        for j in range(i+1, len(l)):\n",
    "            if l[j] < l[min_index]:\n",
    "                min_index = j\n",
    "        if i != min_index:\n",
    "            l[i], l[min_index] = l[min_index], l[i]\n",
    "    return l\n",
    "\n",
    "l = [1, 4, 5, 1, 10, 9, 7, 6, 3, 5]\n",
    "select_sort(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 插入排序\n",
    "插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。\n",
    "\n",
    "## 算法步骤\n",
    "+ 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。\n",
    "+ 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）\n",
    "\n",
    "## 动图演示\n",
    "![](./imgs/insertsort.gif)\n",
    "\n",
    "## 代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 3, 4, 5, 5, 6, 7, 9, 10]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def insert_sort(l):\n",
    "    for i in range(len(l)):\n",
    "        pre_index = i - 1\n",
    "        current = l[i]\n",
    "        while pre_index >= 0 and l[pre_index] > current:\n",
    "            l[pre_index+1] = l[pre_index]\n",
    "            pre_index -= 1\n",
    "        l[pre_index+1] = current\n",
    "    return l\n",
    "\n",
    "l = [1, 4, 5, 1, 10, 9, 7, 6, 3, 5]\n",
    "insert_sort(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 希尔排序\n",
    "希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。\n",
    "希尔排序是基于插入排序的以下两点性质而提出改进方法的：\n",
    "+ 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；\n",
    "+ 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。\n",
    "希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。\n",
    "\n",
    "## 算法步骤\n",
    "+ 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；\n",
    "+ 按增量序列个数 k，对序列进行 k 趟排序；\n",
    "+ 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。\n",
    "\n",
    "## 代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 3, 4, 5, 5, 6, 7, 9, 10]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def shell_sort(l):\n",
    "    n = len(l)\n",
    "    gap = int(n / 2)\n",
    "    \n",
    "    while gap > 0 :\n",
    "        for i in range(gap, n):\n",
    "            temp = l[i]\n",
    "            j = i - gap\n",
    "            while j >= 0 and l[j] > temp:\n",
    "                l[j + gap] = l[j]\n",
    "                j -= gap\n",
    "            l[j + gap] = temp\n",
    "        gap = int(gap / 2)\n",
    "        \n",
    "    return l\n",
    "\n",
    "l = [1, 4, 5, 1, 10, 9, 7, 6, 3, 5]\n",
    "shell_sort(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 归并排序\n",
    "归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。\n",
    "\n",
    "## 算法步骤\n",
    "+ 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；\n",
    "+ 设定两个指针，最初位置分别为两个已经排序序列的起始位置；\n",
    "+ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；\n",
    "+ 重复步骤 3 直到某一指针达到序列尾；\n",
    "+ 将另一序列剩下的所有元素直接复制到合并序列尾。\n",
    "\n",
    "## 动图演示\n",
    "![](./imgs/mergesort.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 3, 4, 5, 5, 6, 7, 9, 10]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def merge_sort(l):\n",
    "    if len(l) < 2:\n",
    "        return l\n",
    "    middle = int(len(l) / 2)\n",
    "    left, right = l[: middle], l[middle:]\n",
    "    return merge(merge_sort(left), merge_sort(right))\n",
    "\n",
    "def merge(left, right):\n",
    "    result = []\n",
    "    while left and right:\n",
    "        if left[0] <= right[0]:\n",
    "            result.append(left.pop(0))\n",
    "        else:\n",
    "            result.append(right.pop(0))\n",
    "    while left:\n",
    "        result.append(left.pop(0))\n",
    "    while right:\n",
    "        result.append(right.pop(0))\n",
    "    return result\n",
    "\n",
    "l = [1, 4, 5, 1, 10, 9, 7, 6, 3, 5]\n",
    "merge_sort(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 快速排序\n",
    "快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。\n",
    "\n",
    "## 算法步骤\n",
    "+ 从数列中挑出一个元素，称为 “基准”（pivot）;\n",
    "+ 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；\n",
    "+ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。\n",
    "\n",
    "## 动图演示\n",
    "![](./imgs/quicksort.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 3, 4, 5, 5, 6, 7, 9, 10]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def quick_sort(l, left=None, right=None):\n",
    "    left = left if left else 0\n",
    "    right = right if right or right == 0 else len(l) - 1\n",
    "    if left < right:\n",
    "        pindex = partition(l, left, right)\n",
    "        quick_sort(l, left, pindex-1)\n",
    "        quick_sort(l, pindex+1, right)\n",
    "    return l\n",
    "\n",
    "\n",
    "def partition(l, left, right):\n",
    "    i = left + 1\n",
    "    while i <= right:\n",
    "        if l[right] < l[left]:\n",
    "            l[i], l[right] = l[right], l[i]\n",
    "            i += 1\n",
    "        else:\n",
    "            right -= 1\n",
    "    l[right], l[left] = l[left], l[right]\n",
    "    return right\n",
    "\n",
    "l = [1, 4, 5, 1, 10, 9, 7, 6, 3, 5]\n",
    "quick_sort(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 堆排序\n",
    "堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：\n",
    "+ 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；\n",
    "+ 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。\n",
    "\n",
    "## 算法步骤\n",
    "+ 创建一个堆 H[0……n-1]；\n",
    "+ 把堆首（最大值）和堆尾互换；\n",
    "+ 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；\n",
    "+ 重复步骤 2，直到堆的尺寸为 1。\n",
    "\n",
    "## 动图演示\n",
    "![](./imgs/heapsort.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1,  1,  3,  4,  5,  5,  6,  7,  9, 10])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def buildMaxHeap(arr):\n",
    "    import math\n",
    "    for i in range(math.floor(len(arr)/2),-1,-1):\n",
    "        heapify(arr,i)\n",
    "\n",
    "def heapify(arr, i):\n",
    "    left = 2*i+1\n",
    "    right = 2*i+2\n",
    "    largest = i\n",
    "    if left < arrLen and arr[left] > arr[largest]:\n",
    "        largest = left\n",
    "    if right < arrLen and arr[right] > arr[largest]:\n",
    "        largest = right\n",
    "\n",
    "    if largest != i:\n",
    "        swap(arr, i, largest)\n",
    "        heapify(arr, largest)\n",
    "\n",
    "def swap(arr, i, j):\n",
    "    arr[i], arr[j] = arr[j], arr[i]\n",
    "\n",
    "def heapSort(arr):\n",
    "    global arrLen\n",
    "    arrLen = len(arr)\n",
    "    buildMaxHeap(arr)\n",
    "    for i in range(len(arr)-1,0,-1):\n",
    "        swap(arr,0,i)\n",
    "        arrLen -=1\n",
    "        heapify(arr, 0)\n",
    "    return arr\n",
    "\n",
    "import numpy as np\n",
    "l = np.array([1, 4, 5, 1, 10, 9, 7, 6, 3, 5])\n",
    "heapSort(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 计数排序\n",
    "计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。\n",
    "\n",
    "## 动图演示  \n",
    "![](./imgs/countingsort.gif)\n",
    "\n",
    "## 代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1,  1,  3,  4,  5,  5,  6,  7,  9, 10])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def countingSort(arr, maxValue):\n",
    "    bucketLen = maxValue+1\n",
    "    bucket = [0]*bucketLen\n",
    "    sortedIndex =0\n",
    "    arrLen = len(arr)\n",
    "    for i in range(arrLen):\n",
    "        if not bucket[arr[i]]:\n",
    "            bucket[arr[i]]=0\n",
    "        bucket[arr[i]]+=1\n",
    "    for j in range(bucketLen):\n",
    "        while bucket[j]>0:\n",
    "            arr[sortedIndex] = j\n",
    "            sortedIndex+=1\n",
    "            bucket[j]-=1\n",
    "    return arr\n",
    "\n",
    "import numpy as np\n",
    "l = np.array([1, 4, 5, 1, 10, 9, 7, 6, 3, 5])\n",
    "countingSort(l, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 桶排序\n",
    "桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：\n",
    "+ 在额外空间充足的情况下，尽量增大桶的数量\n",
    "+ 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中\n",
    "\n",
    "同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。\n",
    "+ 什么时候最快\n",
    ">当输入的数据可以均匀的分配到每一个桶中。  \n",
    "+ 什么时候最慢\n",
    ">当输入的数据被分配到了同一个桶中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 3, 4, 5, 5, 6, 7, 9, 10]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bucket_sort(s):\n",
    "    \"\"\"桶排序\"\"\"\n",
    "    min_num = min(s)\n",
    "    max_num = max(s)\n",
    "    # 桶的大小\n",
    "    bucket_range = (max_num-min_num) / len(s)\n",
    "    # 桶数组\n",
    "    count_list = [ [] for i in range(len(s) + 1)]\n",
    "    # 向桶数组填数\n",
    "    for i in s:\n",
    "        count_list[int((i-min_num)//bucket_range)].append(i)\n",
    "    s.clear()\n",
    "    # 回填，这里桶内部排序直接调用了sorted\n",
    "    for i in count_list:\n",
    "        for j in sorted(i):\n",
    "            s.append(j)\n",
    "    return s\n",
    "\n",
    "l = [1, 4, 5, 1, 10, 9, 7, 6, 3, 5]\n",
    "bucket_sort(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基数排序\n",
    "基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。\n",
    "\n",
    "这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：\n",
    "+ 基数排序：根据键值的每位数字来分配桶；\n",
    "+ 计数排序：每个桶只存储单一键值；\n",
    "+ 桶排序：每个桶存储一定范围的数值。\n",
    "\n",
    "## 动图演示\n",
    "![](./imgs/radixsort.gif)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 1, 1, 3, 4, 5, 5, 6, 7, 9]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def RadixSort(list):\n",
    "    i = 0                                    #初始为个位排序\n",
    "    n = 1                                     #最小的位数置为1（包含0）\n",
    "    max_num = max(list) #得到带排序数组中最大数\n",
    "    while max_num > 10**n: #得到最大数是几位数\n",
    "        n += 1\n",
    "    while i < n:\n",
    "        bucket = {} #用字典构建桶\n",
    "        for x in range(10):\n",
    "            bucket.setdefault(x, []) #将每个桶置空\n",
    "        for x in list: #对每一位进行排序\n",
    "            radix =int((x / (10**i)) % 10) #得到每位的基数\n",
    "            bucket[radix].append(x) #将对应的数组元素加入到相 #应位基数的桶中\n",
    "        j = 0\n",
    "        for k in range(10):\n",
    "            if len(bucket[k]) != 0: #若桶不为空\n",
    "                for y in bucket[k]: #将该桶中每个元素\n",
    "                    list[j] = y #放回到数组中\n",
    "                    j += 1\n",
    "        i += 1\n",
    "    return  list\n",
    "\n",
    "l = [1, 4, 5, 1, 10, 9, 7, 6, 3, 5]\n",
    "RadixSort(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.3 64-bit ('normal': conda)",
   "language": "python",
   "name": "python37564bitnormalconda4753448cc6a44aac9b24f65bfb6fcefd"
  },
  "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.8.3"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}