插入排序

将目标元素插入到前方有序序列中合适的位置，插入一次，有序序列长度加一,就是你打牌整理牌序的过程。

伪代码

INSERTION_SORT(A)    for j = 2 to A.length        key = A[j]        i = j - 1        while i > 0 and A[i] > key            A[i+1] = A[i]            i = i - 1        A[i+1] = key

python

A = [5,2,4,6,1,3]print("排序前", A)j = 1while j < len(A):    key = A[j]    i = j - 1    while i >= 0 and A[i] > key:        A[i+1] = A[i]        i = i - 1    A[i+1] = key    j = j + 1print("排序后", A)

c++

#include 
    
     using namespace std;int main(){    int A[] = {5,2,4,6,1,3};    cout << "排序前 ";    for(int i = 0; i < 6; i++)    {        cout << A[i] << " ";    }    cout << endl;    for(int j = 1; j < 6; j++)    {        int key = A[j];        int i = j - 1;        while(i >= 0 && A[i] > key)        {            A[i+1] = A[i];            i = i - 1;        }        A[i+1] = key;    }    cout << "排序后 ";    for(int i = 0; i < 6; i++)    {        cout << A[i] << " ";    }    return 0;}
    

算法分析

运行时间

• 依赖于输入的顺序，最好顺序，最差逆序
• 依赖于输入的规模
  • 将运行时间看作以输入规模为参数的函数
• 时间上界，对用户的承诺
• 时间复杂度\(\theta(n^2)\)