1.ipynb · 徐啸寅/优化算法

12月21日就在北京，来看大模型推理 + 国产硬件生态 + 开源社区分享，一起搞技术、聊开源、领福利~~

加入 Gitee

与超过 1200万开发者一起发现、参与优秀开源项目，私有仓库也完全免费：）

文件

该仓库未声明开源许可证文件（LICENSE），使用请关注具体项目描述及其代码上游依赖。

克隆/下载

1.ipynb 11.28 KB

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 冒泡排序（稳定）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [7, 5, 3, 6, 44, 22, 99, 11]\n",
    "a2 = [1, 2, 3, 5, 4, 6, 7]\n",
    "a3 = [3, 5, 6, 7, 11, 3, 22, 44, 99]\n",
    "\n",
    "# 时间复杂度为O(n2)\n",
    "def bubble_sort(alist):\n",
    "    n = len(alist)\n",
    "    for k in range(n-1):\n",
    "        # 只要循环n-1次即可， 因为最小的数是前一次已经转过去了\n",
    "        # 每次循环， 列表就小一截\n",
    "        for i in range(n-1-k):\n",
    "            if alist[i]>alist[i+1]:\n",
    "                alist[i], alist[i+1] = alist[i+1], alist[i]\n",
    "    return alist\n",
    "\n",
    "# 先进行检查，若是混乱的，再排序\n",
    "def bubble_sort2(alist):\n",
    "    n = len(alist)\n",
    "    for k in range(n-1):\n",
    "        # 只要循环n-1次即可， 因为最小的数是前一次已经转过去了\n",
    "        # 每次循环， 列表就小一截\n",
    "        count = 0\n",
    "        for i in range(n-1-k):\n",
    "            if alist[i]>alist[i+1]:\n",
    "                alist[i], alist[i+1] = alist[i+1], alist[i]\n",
    "                count += 1\n",
    "        if count == 0:\n",
    "            # 若列表是有序的 则少执行了外循环，这时是最优时间复杂度\n",
    "            break\n",
    "    \n",
    "    return alist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 3, 5, 6, 7, 11, 22, 44, 99]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bubble_sort2(a3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 选择排序（不稳定）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 有点吃空间复杂度， 用切片方式的话 时间复杂度为O(n)\n",
    "def selection_sort(alist):\n",
    "    n = len(alist)\n",
    "    for i in range(n-1):\n",
    "        min_index = alist[i:].index(min(alist[i:]))\n",
    "        b = alist[i:]\n",
    "        b[0], b[min_index] = b[min_index], b[0]\n",
    "        alist[i:] = b\n",
    "    return alist\n",
    "\n",
    "# 时间复杂度为O(n2)\n",
    "def selection_sort2(alist):\n",
    "    n = len(alist)\n",
    "    for i in range(n-1):\n",
    "        min_index = i\n",
    "        for j in range(i+1, n):\n",
    "            # 这一步循环是用来找最小值的\n",
    "            if alist[min_index]>alist[j]:\n",
    "                min_index = j\n",
    "                alist[i], alist[min_index] = alist[min_index], alist[i]\n",
    "    return alist\n",
    "\n",
    "def selection_sort3(alist):\n",
    "    n = len(alist)\n",
    "    for i in range(n-1):\n",
    "        min_index = i\n",
    "        for j in range(i+1, n):\n",
    "            # 这一步循环是用来找最小值的\n",
    "            if alist[min_index]>alist[j]:\n",
    "                min_index = j\n",
    "                \n",
    "        # 如果最小值在对的位置 就不需要进行交换\n",
    "        if min_index != i:\n",
    "            alist[i], alist[min_index] = alist[min_index], alist[i]\n",
    "    return alist\n",
    "\n",
    "def selection_sort4(alist):\n",
    "    n = len(alist)\n",
    "    for i in range(n-1):\n",
    "        max_index = n-1-i\n",
    "        for j in range(0, n-1-i):\n",
    "            if alist[max_index] < alist[j]:\n",
    "                max_index = j\n",
    "        if max_index != i:\n",
    "            alist[max_index], alist[n-1-i] = alist[n-1-i], alist[max_index]\n",
    "    return alist\n",
    "\n",
    "def selection_sort5(alist):\n",
    "    n = len(alist)\n",
    "    for i in range(n-1):\n",
    "        b = alist[:n-1-i]\n",
    "        max_index = b.index(max(b))\n",
    "        if b[-1] < b[max_index]:\n",
    "            b[-1], b[max_index] = b[max_index], b[-1]\n",
    "        alist[:n-1-i] = b\n",
    "    return alist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5, 6, 7, 22, 44, 99, 11]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "selection_sort5(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 插入排序（稳定）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 复杂度O(n2)\n",
    "def insert_sort(alist):\n",
    "    n = len(alist)\n",
    "    for j in range(1, n):\n",
    "        # 一共要排n-1个数\n",
    "        for i in range(j, 0, -1):\n",
    "            # 一共要比这么多次\n",
    "            if alist[i] < alist[i-1]:\n",
    "                alist[i], alist[i-1] = alist[i-1], alist[i]\n",
    "            else:\n",
    "                break\n",
    "    return alist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 快速排序(不稳定)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "a4 = [54, 26, 93, 10, 77, 31, 44, 55, 20]\n",
    "\n",
    "\n",
    "def quick_sort(alist, start, end):\n",
    "    if start>=end:\n",
    "        return alist\n",
    "    # 基准数\n",
    "    mid = alist[start]\n",
    "    low = start\n",
    "    high = end\n",
    "\n",
    "    while low<high:\n",
    "        # 从右向左alist[high]>mid, 则high-=1\n",
    "        while low<high and alist[high]>=mid:\n",
    "            high -= 1\n",
    "        alist[low] = alist[high]\n",
    "\n",
    "        # 从左往右\n",
    "        while low<high and alist[low]<mid:\n",
    "            low+=1\n",
    "        alist[high] = alist[low]\n",
    "    alist[low] = mid\n",
    "    \n",
    "    # 左边数据\n",
    "    quick_sort(alist, start, low-1)\n",
    "\n",
    "    # 右边\n",
    "    quick_sort(alist, low+1, end)\n",
    "    return alist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 20, 26, 31, 44, 54, 55, 77, 93]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quick_sort(a4, 0, len(a4)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 归并排序(稳定)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 时间复杂度为O(nlogn)\n",
    "def merge_sort(alist):\n",
    "    # 递归终止条件\n",
    "    if len(alist) ==1:\n",
    "        return alist\n",
    "    # 一分为二(递归输出结合终止条件来看)\n",
    "    mid = len(alist)//2\n",
    "    left_list = merge_sort(alist[:mid])\n",
    "    right_list = merge_sort(alist[mid:])\n",
    "\n",
    "    # 合并\n",
    "    left_point = 0\n",
    "    right_point = 0\n",
    "    result = []\n",
    "\n",
    "    # 循环是因为指针在动\n",
    "    while left_point<len(left_list) and right_point<len(right_list):\n",
    "        if left_list[left_point] <= right_list[right_point]:\n",
    "            result.append(left_list[left_point])\n",
    "            left_point += 1\n",
    "        elif left_list[left_point] > right_list[right_point]:\n",
    "            result.append(right_list[right_point])\n",
    "            right_point += 1\n",
    "    \n",
    "    # 随便一个越界了都会遗漏数据， 所以要加上\n",
    "    result += left_list[left_point:]\n",
    "    result += right_list[right_point:]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 20, 26, 31, 44, 54, 55, 77, 93]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge_sort(a4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 顺序查找法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "a4 = [54, 26, 93, 17, 77, 31, 44, 55, 20]\n",
    "\n",
    "def sequenceSearch(alist, v):\n",
    "    for i in range(len(alist)):\n",
    "        if alist[i] == v:\n",
    "            return 1\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequenceSearch(a4, 17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 二分查找\n",
    "### 假设已按照升序排列了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(alist, v):\n",
    "    \"\"\"\n",
    "    alist已经进行了升序排列\n",
    "    \"\"\"\n",
    "    n = len(alist)\n",
    "    low = 0\n",
    "    high = n-1\n",
    "    mid = n//2\n",
    "    \n",
    "    while low <= high:\n",
    "        if alist[mid] < v:\n",
    "            low = mid + 1\n",
    "        if alist[mid] > v:\n",
    "            high = mid - 1\n",
    "        if alist[mid] == v:\n",
    "            return mid\n",
    "        mid = (high + low)//2\n",
    "    return False\n",
    "\n",
    "# 下面的只能查找而不能查索引\n",
    "def binary_search2(alist, v):\n",
    "    n = len(alist)\n",
    "    if n == 0:\n",
    "        return False\n",
    "    mid = n//2\n",
    "    if alist[mid] == v:\n",
    "        return True\n",
    "    elif alist[mid] < v:\n",
    "        return binary_search2(alist[mid+1:], v)\n",
    "    else:\n",
    "        return binary_search2(alist[:mid], v)\n",
    "\n",
    "\n",
    "a = [1, 2, 3, 4, 5, 7, 8, 10]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binary_search2(a, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "f23faf4bfe871c203c8bec80520af5927fc7cb1ae3bd834ddf554ee587ad1c05"
  },
  "kernelspec": {
   "display_name": "Python 3.8.5 64-bit",
   "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.8.5"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

一键复制编辑原始数据按行查看历史

提交于 2022-02-23 20:56 +08:00 . 排序算法+链表框架

马建仓 AI 助手

尝试更多

代码解读

代码找茬

代码优化

https://gitee.com/xu-xiaoyin/optimization-algorithm-.git

git@gitee.com:xu-xiaoyin/optimization-algorithm-.git

xu-xiaoyin

optimization-algorithm-

优化算法

master

徐啸寅/优化算法

简介

发行版

贡献者

语言

近期动态

徐啸寅/优化算法 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

语言

近期动态

搜索帮助

徐啸寅/优化算法