第一个算法：插入排序

测试案例：

伪代码：

INSERTION-SORT(A)
for j ← 2 to length[A]
    do key ← A[j]
        i ← j - 1
        while i>0 && A[i]>key
            do A[i+1] ← A[i]
            i ← i - 1
        A[i+1] ← key

源码：

int a[] = {8,6,2,3,1,421,15,6,11,22};
        int key,i;
        for (int j = 1; j < a.length; j++) {
            key = a[j]; //保存当前索引位置的值
            i = j-1; //将索引前移

            //判断当前索引是否到头和当前索引位置的值是否大于key值
            while(i>-1&&a[i]>key){
                //如果大于则将当前值后移
                a[i+1] = a[i];
                // ①索引继续前移
                i--;
            }
            //与①操作呼应，索引后移，保证索引位置数据正确性
            a[i+1] = key;
        }

        for (int j = 0; j < a.length; j++) {
            System.out.println(a[j]);
        }

该算法对n个数据项进行排序的时间大约：c1 n²
适用于小规模输入，如果输入规模n变得足够大，则合并排序将占据大优势。