排序2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def BubbleSort(arr):\n",
    "    for i in range(len(arr)):\n",
    "        for j in range(len(arr)-i-1):\n",
    "            if arr[j] > arr[j+1]:\n",
    "                arr[j], arr[j+1] = arr[j+1], arr[j]\n",
    "    return arr\n",
    "arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]\n",
    "BubbleSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]\n",
    "def NewBubbleSort(arr):\n",
    "    for i in range(len(arr)):\n",
    "        for j in range(len(arr)-i-1):\n",
    "            if arr[j] > arr[j+1]:\n",
    "                arr[j], arr[j+1] = arr[j+1], arr[j]\n",
    "    return arr\n",
    "NewBubbleSort(arr.copy())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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",
    "arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]\n",
    "QuickSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def NewQuickSort(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",
    "    quick(arr, 0, len(arr)-1)\n",
    "    return arr\n",
    "NewQuickSort(arr.copy())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def InsertSort(arr):\n",
    "    for i in range(len(arr)):\n",
    "        target = arr[i]\n",
    "        j = i\n",
    "        while j > 0 and arr[j-1] > target:\n",
    "            arr[j] = arr[j-1]\n",
    "            j -= 1\n",
    "        arr[j] = target\n",
    "    return arr\n",
    "arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]\n",
    "InsertSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def NewInsertSort(arr):\n",
    "    for i in range(len(arr)):\n",
    "        target = arr[i]\n",
    "        j = i\n",
    "        while j > 0 and arr[j-1] > target:\n",
    "            arr[j] = arr[j-1]\n",
    "            j -= 1\n",
    "        arr[j] = target\n",
    "    return arr\n",
    "NewInsertSort(arr.copy())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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 >= 0 and arr[j-d] > target:\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",
    "arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]\n",
    "ShellSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def NewShellSort(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>=0 and arr[j-d] > target:\n",
    "                arr[j] = arr[j-d]\n",
    "                j -= d\n",
    "            arr[j] = target\n",
    "    d = len(arr)//2\n",
    "    while d:\n",
    "        shell(arr, d)\n",
    "        d //= 2\n",
    "    return arr\n",
    "NewShellSort(arr.copy())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def SelectSort(arr):\n",
    "    for i in range(len(arr)-1):\n",
    "        target = i\n",
    "        for j in range(i+1, len(arr)):\n",
    "            if arr[j] < arr[target]:\n",
    "                target = j\n",
    "        arr[i], arr[target] = arr[target], arr[i]\n",
    "    return arr\n",
    "arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]\n",
    "SelectSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def NewSelectSort(arr):\n",
    "    for i in range(len(arr)):\n",
    "        target = i\n",
    "        for j in range(i+1, len(arr)):\n",
    "            if arr[target] > arr[j]:\n",
    "                target = j\n",
    "        arr[target], arr[i] = arr[i], arr[target]\n",
    "    return arr\n",
    "NewSelectSort(arr.copy())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def HeapSort(arr):\n",
    "    def adjust(arr, start, end):\n",
    "        temp = arr[start]\n",
    "        i = start\n",
    "        j = 2*i\n",
    "        while j <= end:\n",
    "            if j < end and arr[j] < arr[j+1]:\n",
    "                j += 1\n",
    "            if temp < arr[j]:\n",
    "                arr[i] = arr[j]\n",
    "                i = j\n",
    "                j = 2*i\n",
    "            else:\n",
    "                break\n",
    "        arr[i] = temp\n",
    "    \n",
    "    arr = [0] + arr\n",
    "    length = len(arr)-1\n",
    "    split = length//2\n",
    "    for i in range(split):\n",
    "        adjust(arr, split-i, length)\n",
    "        \n",
    "    for i in range(length):\n",
    "        arr[1], arr[length-i] = arr[length-i], arr[1]\n",
    "        adjust(arr, 1, length-i-1)\n",
    "        \n",
    "    return arr[1:]\n",
    "arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]\n",
    "HeapSort(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def NewHeapSort(arr):\n",
    "    def adjust(arr, start, end):\n",
    "        lchild = start*2+1\n",
    "        rchild = start*2+2\n",
    "        best = start\n",
    "        if lchild < end and arr[best] < arr[lchild]:\n",
    "            best = lchild\n",
    "        if rchild < end and arr[best] < arr[rchild]:\n",
    "            best = rchild\n",
    "        if best != start:\n",
    "            arr[best], arr[start] = arr[start], arr[best]\n",
    "            adjust(arr, best, end)\n",
    "    \n",
    "    for i in range(len(arr)//2)[::-1]:\n",
    "        adjust(arr, i, len(arr))\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",
    "NewHeapSort(arr.copy())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "a = TreeNode(1)\n",
    "b = TreeNode(2)\n",
    "c = TreeNode(3)\n",
    "d = TreeNode(4)\n",
    "e = TreeNode(5)\n",
    "f = TreeNode(6)\n",
    "g = TreeNode(7)\n",
    "h = TreeNode(8)\n",
    "a.left = b\n",
    "a.right = c\n",
    "b.left = d\n",
    "b.right = e\n",
    "c.right = f\n",
    "e.left = g\n",
    "e.right = h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "4\n",
      "5\n",
      "7\n",
      "8\n",
      "3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "def preLoop(root):\n",
    "    if root:\n",
    "        print(root.val)\n",
    "        preLoop(root.left)\n",
    "        preLoop(root.right)\n",
    "preLoop(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "4\n",
      "5\n",
      "7\n",
      "8\n",
      "3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "def nopreLoop(root):\n",
    "    stack = []\n",
    "    while root or len(stack) > 0:\n",
    "        if root:\n",
    "            print(root.val)\n",
    "            stack.append(root)\n",
    "            root = root.left\n",
    "        else:\n",
    "            root = stack.pop()\n",
    "            root = root.right\n",
    "nopreLoop(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "2\n",
      "7\n",
      "5\n",
      "8\n",
      "1\n",
      "3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "def inLoop(root):\n",
    "    if root:\n",
    "        inLoop(root.left)\n",
    "        print(root.val)\n",
    "        inLoop(root.right)\n",
    "inLoop(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "2\n",
      "7\n",
      "5\n",
      "8\n",
      "1\n",
      "3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "def noinLoop(root):\n",
    "    stack = []\n",
    "    while root or len(stack) != 0:\n",
    "        if root:\n",
    "            stack.append(root)\n",
    "            root = root.left\n",
    "        else:\n",
    "            root = stack.pop()\n",
    "            print(root.val)\n",
    "            root = root.right\n",
    "noinLoop(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "7\n",
      "8\n",
      "5\n",
      "2\n",
      "6\n",
      "3\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "def postLoop(root):\n",
    "    if root:\n",
    "        postLoop(root.left)\n",
    "        postLoop(root.right)\n",
    "        print(root.val)\n",
    "postLoop(a)"
   ]
  },
  {
   "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
}