Top-k.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "test=np.random.rand(10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 插入排序\n",
    "    插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中\n",
    "    先排第一个，把第二个插入，然后在把第三个插入。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insert_sort(lists):\n",
    "    # 插入排序\n",
    "    count = len(lists)\n",
    "    for i in range(1, count):\n",
    "        key = lists[i]\n",
    "        j = i - 1\n",
    "        while j >= 0:\n",
    "            if lists[j] > key:\n",
    "                lists[j + 1] = lists[j]\n",
    "                lists[j] = key\n",
    "            j -= 1\n",
    "    return lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 15 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([2.59103536e-05, 4.30852707e-05, 8.32045091e-05, ...,\n",
       "       9.99886735e-01, 9.99895469e-01, 9.99963724e-01])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time insert_sort(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 冒泡排序 \n",
    "    它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bubble_sort(lists):\n",
    "    # 冒泡排序\n",
    "    count = len(lists)\n",
    "    for i in range(0, count):\n",
    "        for j in range(i + 1, count):\n",
    "            if lists[i] > lists[j]:\n",
    "                lists[i], lists[j] = lists[j], lists[i]\n",
    "    return lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 8.88 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([2.59103536e-05, 4.30852707e-05, 8.32045091e-05, ...,\n",
       "       9.99886735e-01, 9.99895469e-01, 9.99963724e-01])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time insert_sort(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 快速排序\n",
    "    通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def quick_sort(lists, left, right):\n",
    "    # 快速排序\n",
    "    if left >= right:\n",
    "        return lists\n",
    "    key = lists[left]\n",
    "    low = left\n",
    "    high = right\n",
    "    while left < right:\n",
    "        while left < right and lists[right] >= key:\n",
    "            right -= 1\n",
    "        lists[left] = lists[right]\n",
    "        while left < right and lists[left] <= key:\n",
    "            left += 1\n",
    "        lists[right] = lists[left]\n",
    "    lists[right] = key\n",
    "    quick_sort(lists, low, left - 1)\n",
    "    quick_sort(lists, left + 1, high)\n",
    "    return lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 0 ns\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([2.59103536e-05, 4.30852707e-05, 8.32045091e-05, ...,\n",
       "       9.99886735e-01, 9.99895469e-01, 9.99963724e-01])"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time quick_sort(test,10,50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 501 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([2.59103536e-05, 4.30852707e-05, 8.32045091e-05, ...,\n",
       "       9.99886735e-01, 9.99895469e-01, 9.99963724e-01])"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time np.sort(test)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}