gitbook-way-to-algorithm
  • Introduction
  • Preface 前言
  • Content 目录
  • MathSymbolTable 数学符号表
  • Chapter-1 BasicKnowledge 第1章 基础知识
    • TimeComplexity 时间复杂度
    • Recursion 递归式
  • Chapter-2 Sort 第2章 排序
    • InsertSort 插入排序
    • BubbleSort 冒泡排序
    • QuickSort 快速排序
    • MergeSort 归并排序
  • Chapter-3 Search 第3章 搜索
    • BinarySearch 二分查找法(折半查找法)
    • AdditionMultiplicationPrinciple 加法乘法原理
    • BruteForce 暴力枚举
    • Recursion 递归
    • BreadthFirstSearch 广度优先搜索
    • BidirectionalBreadthSearch 双向广度搜索
    • AStarSearch A*搜索
    • DancingLink 舞蹈链
  • Chapter-4 DataStructure 第4章 数据结构
    • DisjointSet 并查集
    • PrefixTree(TrieTree) 前缀树
    • LeftistTree(LeftistHeap) 左偏树(左偏堆)
    • SegmentTree 线段树
    • FenwickTree(BinaryIndexedTree) 树状数组
    • BinarySearchTree 二叉查找树
    • AVLTree AVL平衡树
    • RedBlackTree 红黑树
    • SkipList 跳跃表
    • BPlusTree B+树
    • BMinusTree B-树
  • Chapter-5 DynamicProgramming 第5章 动态规划
    • Section-1 LinearDP 第1节 线性动规
      • LongestCommonSubsequence 最长公共子序列
      • LongestIncreasingSubsequence 最长递增子序列
      • BidirectionalSubsequence 双向子序列
      • MaximumContinuousSubsequenceSum 最大连续子序列和
      • LongestPalindromicSubsequence 最长回文子序列
    • Section-2 BagDP 第2节 背包问题
      • 01-Bag 01背包
      • CompleteBag 完全背包
      • TwoDimensionBag 二维背包
    • Section-3 RegionalDP 第3节 区域动规
      • MinimumMergeCost - 最小合并代价
      • UniquePath 唯一路径
      • TrianglePath 三角形路径
    • Section-4 TreeDP 第4节 树形动规
      • MaximumBinaryTree 最大二叉树
      • MaxMultipleTree 最大多叉树
      • MaximumBinaryTreeRadiusSum 最大二叉树和
  • Chapter-6 GraphTheory 第6章 图论
    • Section-1 Traverse 第1节 遍历
      • DepthFirstSearch 深度优先搜索
      • BreadthFirstSearch 广度优先搜索
      • TopologicalSort 拓扑排序
      • EulerCycle 欧拉回路
    • Section-2 MinSpanningTree 第2节 最小生成树
      • Kruskal Kruskal算法
      • Prim Prim算法
    • Section-3 ShortestPath 第3节 最短路径
      • BellmanFord BellmanFord算法
      • Dijkstra Dijkstra算法
      • FloydWarshall FloydWarshall算法
      • DifferentConstraints 差分约束
    • Section-4 StronglyConnectedComponents 第4节 强连通分支
      • Kosaraju Kosaraju算法
      • Tarjan Tarjan算法
      • 2-SAT 2-SAT问题
    • Section-5 NetworkFlow 第5节 网络流
      • EdmondsKarp EdmondsKarp算法(最短路径增广算法)
      • PushRelabel 压入与重标记算法
      • Dinic - Dinic算法
      • MinimumCostFlow - 最小费用流
      • MultipleSourceMultipleSinkMaxflow - 多源点多汇点最大流
    • Section-6 BinaryMatch 第6节 二分匹配
      • Hungarian 匈牙利算法
      • HopcroftKarp Hopcroft-Karp算法
      • MatchToMaxflow 二分匹配转化为最大流
      • KuhnMunkres Kuhn-Munkres算法
      • Introduction-Domination,Independent,Covering,Clique 介绍支配集、独立集、覆盖集和团
      • WeightedCoveringAndIndependentSet 最小点权覆盖和最大点权独立集
      • MinimumDisjointPathCovering 最小不相交路径覆盖
      • MinimumJointPathCovering 最小可相交路径覆盖
      • Coloring 染色问题
  • Chapter-7 CombinatorialMathematics 第7章 组合数学
    • FullPermutation 全排列
    • Combination 组合
    • Permutation 排列
    • PermutationGroup 置换群
  • Chapter-8 NumberTheory 第8章 数论
    • PrimeSieve 素数筛法
    • GreatestCommonDivisor 最大公约数
    • Euclid 欧几里得算法
    • ExtendedEuclid 扩展欧几里得算法
    • ChineseRemainerTheorem 中国剩余定理
    • ModularExponentiation 模幂运算
  • Chapter-9 LinearAlgebra 第9章 线性代数
    • Section-1 Matrix 第1节 矩阵
      • Strassen Strassen算法
      • GaussElimination 高斯消元法
      • LUP LUP分解
      • InverseMatrix 矩阵求逆
    • Section-2 LinearProgramming 第2节 线性规划
      • Simplex 单纯形算法
      • Dinkelback Dinkelback算法
  • Chapter-10 AnalyticGeometry 第10章 解析几何
    • Section-1 Polygon 第1节 多边形
      • Cross 向量叉积
      • SegmentIntersection 线段相交
      • Sweeping 扫除算法
      • ConvexPolygonArea 凸多边形面积
      • ConvexPolygonGravityCenter 凸多边形重心
      • NearestNeighbor 最近点对
    • Section-2 ConvexHull 第2节 凸包
      • GrahamScan Graham扫描算法
      • QuickHull 快速凸包算法
      • RotatingCalipers 旋转卡壳
  • Chapter-11 PatternMatch 第11章 文本匹配
    • SimpleMatch 简单匹配
    • AhoCorasickAutomata AC自动机
    • KnuthMorrisPratt KMP匹配算法
    • RabinKarp RabinKarp算法
    • BoyerMoore BoyerMoore算法
  • Chapter-12 GameTheory 第12章 博弈论
    • BashGame 巴什博弈
    • WythoffGame 威佐夫博弈
    • NimGame 尼姆博弈
Powered by GitBook
On this page
  • 问题
  • 解法
  • 复杂度
  • 源码
  • 测试
  1. Chapter-2 Sort 第2章 排序

InsertSort 插入排序

PreviousChapter-2 Sort 第2章 排序NextBubbleSort 冒泡排序

Last updated 6 years ago

问题

用Insert Sort对长度为nnn的无序序列sss从小到大(升序)排序。

解法

将长度为nnn的序列s=[x0,x1,…,xn−1]s = [x_0, x_1, \dots, x_{n-1}]s=[x0​,x1​,…,xn−1​]分为左右两个部分,已排序的left=[x0,…,xk]left = [x_0, \dots, x_k]left=[x0​,…,xk​]和未排序的right=[xk+1,…,xn−1]right = [x_{k+1}, \dots, x_{n-1}]right=[xk+1​,…,xn−1​],其中0≤k≤n0 \le k \le n0≤k≤n。如图:

初始时left=∅,right=[x0,…,xn−1]left = \varnothing, right = [x_0, \dots, x_{n-1}]left=∅,right=[x0​,…,xn−1​]。

对leftleftleft和rightrightright进行如下操作:

function Insert(s, k, n):
    let x = s[k+1]
    for i = [0, k+1]
        if i = 0 and x <= s[i]
            break
        if i > 0 and s[i-1] <= x <= s[i]
            break
    if i <= k
        move s[i...k] to s[i+1...k+1]
        let s[i] = x

(1) Insert函数第3-7行:遍历leftleftleft找出一个适合xxx插入的位置s[i]s[i]s[i]。其中i=0i = 0i=0属于边界条件,只需判断x<=s[0]x <= s[0]x<=s[0]即可;

(2) Insert函数第8-10行:若找到一个合适的插入位置0<=i<=k0 <= i <= k0<=i<=k则将其插入;若找不到(i=k+1i = k + 1i=k+1)则说明xxx比leftleftleft中所有元素都大,不需要移动。下次调用Insert函数时输入参数kkk变成k+1k + 1k+1,就可以将现在的s[k+1]s[k+1]s[k+1]加入leftleftleft中;

上述操作如图:

运行一次Insert函数可以将rightrightright最左边的元素插入到leftleftleft中合适的位置(leftleftleft长度减1,rightrightright长度加1)。初始时leftleftleft长度为000,rightrightright长度为nnn,只需重复调用nnn次Insert函数即可完成排序:

function InsertSort(s, n):
    for k = [0, n-2]
        Insert(s, k, n)

例如下图中,leftleftleft部分为s[0,5]s[0,5]s[0,5],rightrightright部分为s[6,n−1]s[6,n-1]s[6,n−1],rightrightright最左边的首部元素x=s[6]=41x = s[6] = 41x=s[6]=41,在leftleftleft部分中合适的插入位置为i=3i = 3i=3(s[2]≤x≤s[3]s[2] \le x \le s[3]s[2]≤x≤s[3])。

将s[3,5]s[3,5]s[3,5]向右移动一位到s[4,6]s[4,6]s[4,6],将原xxx移动到s[3]s[3]s[3],就完成了一次插入。

复杂度

与BubbleSort算法类似,该算法的时间复杂度为O(n2)O(n^2)O(n2),空间复杂度为O(1)O(1)O(1)。

源码

测试

InsertSort.h
InsertSort.cpp
InsertSortTest.cpp
InsertSort3.png
InsertSort4.png
InsertSort5.png
InsertSort1.png
InsertSort2.png