直接插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

具体步骤如下：

1. 创建一个空的有序序列。

2. 从第一个元素开始，将每个元素依次插入到已排序的序列中。对于当前元素，从已排序的序列的末尾开始向前扫描，找到合适的位置并插入。

3. 重复步骤2，直到所有元素都插入到已排序的序列中。

直接插入排序的时间复杂度为O(n^2)，其中n为待排序元素的个数。这种算法比较适合于数据量较小、初始序列基本有序的情况。如果数据量较大，建议使用更高效的排序算法，如快速排序、归并排序等。

以下是使用C++实现直接插入排序的示例代码：

#include <iostream>  
using namespace std;  
  
void insertionSort(int arr[], int n) {  
    for (int i = 1; i < n; i++) {  
        int key = arr[i];  
        int j = i - 1;  
        while (j >= 0 && arr[j] > key) {  
            arr[j + 1] = arr[j];  
            j--;  
        }  
        arr[j + 1] = key;  
    }  
}  
  
int main() {  
    int arr[] = {5, 2, 9, 1, 5, 6};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    insertionSort(arr, n);  
    for (int i = 0; i < n; i++) {  
        cout << arr[i] << " ";  
    }  
    cout << endl;  
    return 0;  
}

在这个示例中，定义了一个insertionSort函数来实现直接插入排序。该函数接受一个整数数组和数组的大小作为参数，并按升序对数组进行排序。在主函数中，定义了一个整数数组arr，并调用insertionSort函数对其进行排序。最后，输出排序后的数组。

二分插入排序是一种改进的插入排序算法，其基本思想是将待插入的元素插入到已排序序列的正确位置，而不是从后向前扫描已排序序列。具体步骤如下：

1. 从第一个元素开始，将其视为已排序序列。

2. 每次从待排序序列中取出第一个元素，利用二分查找法在已排序序列中查找其正确的位置。

3. 将该元素插入到已排序序列的正确位置，并更新已排序序列。

4. 重复步骤2和3，直到待排序序列为空。

以下是使用C++实现二分插入排序的示例代码：

#include <iostream>  
using namespace std;  
  
void binaryInsertionSort(int arr[], int n) {  
    for (int i = 1; i < n; i++) {  
        int key = arr[i];  
        int left = 0, right = i - 1;  
        while (left <= right) {  
            int mid = left + (right - left) / 2;  
            if (arr[mid] > key) {  
                right = mid - 1;  
            } else {  
                left = mid + 1;  
            }  
        }  
        for (int j = i - 1; j >= left; j--) {  
            arr[j + 1] = arr[j];  
        }  
        arr[left] = key;  
    }  
}  
  
int main() {  
    int arr[] = {5, 2, 9, 1, 5, 6};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    binaryInsertionSort(arr, n);  
    for (int i = 0; i < n; i++) {  
        cout << arr[i] << " ";  
    }  
    cout << endl;  
    return 0;  
}

在这个示例中，定义了一个binaryInsertionSort函数来实现二分插入排序。该函数接受一个整数数组和数组的大小作为参数，并按升序对数组进行排序。在主函数中，定义了一个整数数组arr，并调用binaryInsertionSort函数对其进行排序。最后，输出排序后的数组。

希尔排序(Shell Sort)是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

以下是使用C++实现希尔排序的示例代码：

#include <iostream>  
using namespace std;  
  
void shellSort(int arr[], int n) {  
    int gap = n / 2;  
    while (gap > 0) {  
        for (int i = gap; i < n; i++) {  
            int temp = arr[i];  
            int j;  
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {  
                arr[j] = arr[j - gap];  
            }  
            arr[j] = temp;  
        }  
        gap /= 2;  
    }  
}  
  
int main() {  
    int arr[] = {5, 2, 9, 1, 5, 6};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    shellSort(arr, n);  
    for (int i = 0; i < n; i++) {  
        cout << arr[i] << " ";  
    }  
    cout << endl;  
    return 0;  
}

在这个示例中，定义了一个shellSort函数来实现希尔排序。该函数接受一个整数数组和数组的大小作为参数，并按升序对数组进行排序。在主函数中，定义了一个整数数组arr，并调用shellSort函数对其进行排序。最后，输出排序后的数组。