练习.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 快排\n",
    "def QuickSort(arr):\n",
    "    def quick(arr, left, right):\n",
    "        if left >= right:\n",
    "            return\n",
    "        low, high = left, right\n",
    "        key = arr[left]\n",
    "        while left < right:\n",
    "            while left < right and arr[right] > key:\n",
    "                right -= 1\n",
    "            arr[left] = arr[right]\n",
    "            while left < right and arr[left] <= key:\n",
    "                left += 1\n",
    "            arr[right] = arr[left]\n",
    "        arr[left] = key\n",
    "        quick(arr, low, left-1)\n",
    "        quick(arr, left+1, high)\n",
    "        \n",
    "    quick(arr, 0, len(arr)-1)\n",
    "    return arr\n",
    "    \n",
    "arr = [9,6,0, 8,5,4,7,2,3,1]\n",
    "QuickSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# shell sort\n",
    "def ShellSort(arr):\n",
    "    def shell(arr, d):\n",
    "        for i in range(d, len(arr)):\n",
    "            target = arr[i]\n",
    "            j = i\n",
    "            while j >= d and target < arr[j-d]:\n",
    "                arr[j] = arr[j-d]\n",
    "                j -= d\n",
    "            arr[j] = target\n",
    "    d = len(arr)//2\n",
    "    while d >= 1:\n",
    "        shell(arr, d)\n",
    "        d //= 2\n",
    "    return arr\n",
    "\n",
    "arr = [9,6,0, 8,5,4,7,2,3,1]\n",
    "ShellSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# heap\n",
    "def HeapSort(arr):\n",
    "    def adjust(arr, i, size):\n",
    "        lchild = 2*i+1\n",
    "        rchild = 2*i+2\n",
    "        largest = i\n",
    "        if lchild < size and arr[lchild] > arr[largest]:\n",
    "            largest = lchild\n",
    "        if rchild < size and arr[rchild] > arr[largest]:\n",
    "            largest = rchild\n",
    "        if largest != i:\n",
    "            arr[largest], arr[i] = arr[i], arr[largest]\n",
    "            adjust(arr, largest, size)\n",
    "    \n",
    "    size = len(arr)\n",
    "    for i in range(len(arr)//2)[::-1]:\n",
    "        adjust(arr, i, size)\n",
    "        \n",
    "    for i in range(len(arr))[::-1]:\n",
    "        arr[0], arr[i] = arr[i], arr[0]\n",
    "        adjust(arr, 0, i)\n",
    "    return arr\n",
    "\n",
    "arr = [9,6,0, 8,5,4,7,2,3,1]\n",
    "HeapSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}