排序算法之插入排序

插入排序是一种基本的排序算法，其思想是将待排序的数据分为已排序区间和未排序区间，每次从未排序区间中取出一个数，在已排序区间中找到合适的位置插入，并使得已排序区间仍有序。其时间复杂度为O(n^2)，空间复杂度为O(1)。

插入排序的实现方式有两种：

1. 直接插入排序

直接插入排序的思想是：将待排序的数据分为有序区和无序区，从无序区中取出一个数，将其插入到有序区中，使得插入后仍保持有序。具体实现过程如下：

（1）初始时，有序区只有一个元素，为 个元素。

（2）依次将无序区的元素插入到有序区中，插入的方式是将当前元素与有序区的最后一个元素进行比较，如果当前元素比有序区最后一个元素小，则将有序区最后一个元素后移一位；否则，当前元素的位置就是有序区的最后一个位置。

（3）重复上述步骤，直至所有元素都插入到有序区中。

C++代码实现：

void InsertionSort(int a[], int n)  
{  
    for (int i = 1; i < n; i++)  
    {  
        int j = i - 1;  
        int temp = a[i];  
        while (j >= 0 && a[j] > temp)  
        {  
            a[j + 1] = a[j];  
            j--;  
        }  
        a[j + 1] = temp;  
    }  
}  

2. 希尔排序

希尔排序是直接插入排序的优化，它采用了增量序列的思想，将待排序序列分成若干个子序列，并对每个子序列进行插入排序，直至整个序列有序。具体实现过程如下：

（1）选择一个增量序列，将待排序的数据分组，每组包含若干个元素。

（2）对于每组数据，进行插入排序，每次将当前组的最后一个元素与前面所有元素比较，然后将元素插入到正确的位置。

（3）减小增量序列，重新分组，重复上述步骤，直至增量序列为1。

C++代码实现：

void ShellSort(int a[], int n)  
{  
    for (int gap = n / 2; gap > 0; gap /= 2)  
    {  
        for (int i = gap; i < n; i++)  
        {  
            int temp = a[i];  
            int j = i - gap;  
            while (j >= 0 && a[j] > temp)  
            {  
                a[j + gap] = a[j];  
                j -= gap;  
            }  
            a[j + gap] = temp;  
        }  
    }  
}  

总结：

插入排序是一种简单而又实用的排序算法，适用于小规模数据的排序。在实际应用中，可以通过对插入排序进行优化，比如使用希尔排序，来获得更好的效率。