【数据结构与算法】插入排序

[buckrudy]

插入排序

插入排序的思想是把要排序的数列看成一有序和一个无序的集合。开始时只有一个元素是有序的，排序的过程就是每次从无序的集合中取一个元素，插到有序集合中适当的位置。重复这个过程，完成排序。

代码实现

按升序排序的实现

void insertSort(int a[], int len)
{
    int i, j;
    int k;
    int temp;

    for (i=1; i<len; i++) {       // len - 1 趟
        for (j=i-1; j>=0; j--) {   // 在已有序的集合中找到插入位置
            if (a[i] > a[j]) {
                break;
            }
        }

        if (i-1 != j) {
            temp = a[i];
            for (k=i-1; k>j; k--) {  // 移动有序集合
                a[k+1] = a[k];
            }
            a[j+1] = temp;       //插入
        }
    }
}

// ------------------------------------------------------------------
void insertSort2(int a[], int len)
{
    int i, j;
    int temp;
    for (i=1; i<len; i++) {
        temp = a[i];
        j = i - 1;
        while (j>=0 && temp < a[j]) {   //边找边移
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

算法复杂度

插入排序算法复杂度为 O(n²)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。