数据结构插入排序

插入排序是一种简单直观的排序算法，其基本思想是将待排序序列分为已排序区间和未排序区间，每次从未排序区间中取出一个元素，在已排序区间中从后向前扫描，找到相应位置并插入。

具体实现过程如下：

1. 将序列的第一个元素看作已排序区间，其余元素看作未排序区间。

2. 从未排序区间中取出第一个元素，将其插入到已排序区间中的合适位置。

3. 重复步骤 2，直到未排序区间为空。

下面是 C++ 代码实现：

void insertion_sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        int j = i - 1;
        int temp = nums[i];
        while (j >= 0 && nums[j] > temp) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = temp;
    }
}

其中，变量 `j` 用于指向已排序区间中的最后一个元素，`temp` 存储当前需要插入的元素值。在内部循环中，如果当前已排序元素大于 `temp`，则将该元素后移一位，直到找到合适的位置插入 `temp`。

相关问题

数据结构插入排序算法

插入排序算法是数据结构中的一种排序算法，它将待排序的元素分为已排序和未排序两部分，每次从未排序部分取出一个元素，将其插入到已排序部分的合适位置。插入排序算法有多种实现方式，其中最常见的有直接插入排序、折半插入排序和希尔排序。

直接插入排序算法的基本思想是将待排序元素逐个插入到已经排序好的序列中，从而得到一个新的有序序列。具体实现过程如下：
1. 将第一个元素视为已排序序列，剩余的元素视为未排序序列。
2. 从未排序序列中取出一个元素，将其与已排序序列中的元素从后往前依次比较，找到合适的位置插入。
3. 重复步骤2，直到未排序序列中的所有元素都插入到已排序序列中。

折半插入排序算法是对直接插入排序算法的改进，通过使用二分查找的方式确定插入位置，减少了比较次数。具体实现过程如下：
1. 将第一个元素视为已排序序列，剩余的元素视为未排序序列。
2. 从未排序序列中取出一个元素，使用二分查找的方法找到合适的插入位置。
3. 将元素插入到找到的位置，并将位置后的元素依次后移。
4. 重复步骤2和3，直到未排序序列中的所有元素都插入到已排序序列中。

希尔排序算法是对插入排序算法的另一种改进，通过对待排序序列进行分组，先进行局部排序，然后逐渐减少分组的长度，最终进行一次完整的插入排序。具体实现过程如下：
1. 选择一个增量序列，按照增量序列对待排序序列进行分组。
2. 对每个分组进行插入排序。
3. 不断缩小增量，重复步骤2，直到增量为1。
4. 进行一次完整的插入排序。

这些是插入排序算法的基本思想和实现方法，它们都可以对一组数据进行排序。具体选择哪种算法取决于实际的需求和数据规模。

王道数据结构插入排序

插入排序是一种简单直观的排序算法，它的基本思想是将待排序的数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，在已排序部分找到合适的位置插入该元素，以此类推直至完成排序。

下面是使用插入排序算法对数组进行排序的示例代码：

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        
        // 将比key大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

在插入排序中，我们从数组的第二个元素开始遍历，每次将当前元素与它前面的已排序部分进行比较，如果当前元素较小，则将前面的元素向后移动一位，直到找到合适的位置插入当前元素。

希望对你有所帮助！如果有任何疑问，请随时提问。