任务五：编写程序实现直接插入排序的功能。 直接插入排序，是指将无序序列中的各元素依次插入到已经有序的数组中。 假设数组中前i-1元素已经有序，现在要将线性表中第i个元素插入到前面的有序子表中，插入过程如下： 举例：以长度为n=8的序列（13，6，1，31，9，27，5，11）的插入排序过程做示范： 第1趟：将数组第2个元素6向前插入后，则数组中元素为（6，13，1，31，9，27，5，11）； 第2趟：将数组第3个元素1向前插入后，则数组中元素为（1，6，13，31，9，27，5，11）； 第3趟：

以下是Python实现直接插入排序的代码：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        j = i - 1
        key = arr[i]
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

该程序接收一个数组作为输入，使用for循环遍历数组中除第一个元素以外的所有元素。对于每个元素，我们将其与前面的有序子序列中的元素进行比较，找到合适的位置插入该元素。具体地，我们使用while循环比较元素的值，如果前面的元素比当前元素大，则将前面的元素后移一位，直到找到一个小于或等于当前元素的位置，然后将当前元素插入到该位置之后。最终，程序返回已排序的数组。

例如，对于输入数组[13, 6, 1, 31, 9, 27, 5, 11]，程序输出为[1, 5, 6, 9, 11, 13, 27, 31]，这就是该数组的有序排列。

相关问题

编写函数实现直接插入排序 编写函数实现直接插入排序。输入若干正整数，以0结束，采用直接插入排序将这些整数按照从大到小的顺序排序。 函数接口定义： void InsertSort(SqList &L)； 其中 L 是待排序的关键字，采用顺序表存储。

好的，以下是直接插入排序的 C++ 实现：

void InsertSort(SqList &L) {
    int i, j;
    for (i = 2; i <= L.length; i++) { // 从第二个元素开始，即第一个无序元素
        if (L.data[i] > L.data[i-1]) continue; // 如果该元素比它前一个元素大，说明已有序，无需排序
        L.data[0] = L.data[i];
        for (j = i-1; L.data[j] < L.data[0]; j--) // 从后向前查找插入位置
            L.data[j+1] = L.data[j]; // 向后移动元素
        L.data[j+1] = L.data[0]; // 插入元素
    }
}

这个函数实现了对顺序表 `L` 的直接插入排序。其中，`L.data` 是存储关键字的数组，`L.length` 是顺序表中元素的个数。

函数的主要思路是：从第二个元素开始循环，如果该元素比它前一个元素大，说明已有序，无需排序。否则，将该元素插入到前面有序序列的适当位置，同时将后面的元素依次向后移动一位。循环结束后，`L` 中的元素就按照从大到小的顺序排好了。

for(i=1;i<len;i++){ //从数组的第二个元素开始依次遍历无序序列 int tem = array[i]; //临时保存将要排序的元素 //第二个for循环遍历有序序列 for(j=i-1;tem<=array[j]&&j>=0;j--){ //将待排序元素依次和有序序列中的元素比较 //待排序元素 小于 有序序列中当前元素时 将该元素后移 array[j+1] = array[j]; } array[j+1] = tem; //待排序元素 大于 有序序列最后一个元素 直接将该元素插入到有序序列最后 } printf("\n排序完成!\n\n"); } main(){ int array[10] = {4,3,10,5,6,7,1,2,8,9} ; int len = sizeof(array) / sizeof(int); printf("初始序列：\n"); Print(array,len); InsertSort(array,len); printf("排序后序列：\n"); Print(array,len); } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

这段代码是使用插入排序算法对一个整数数组进行排序的示例。插入排序的基本思想是将数组划分为有序和无序两部分，然后依次将无序部分的元素插入到有序部分的适当位置，最终得到一个完全有序的数组。

在这段代码中，通过两个嵌套的循环来实现插入排序。外层循环从数组的第二个元素开始遍历到最后一个元素，内层循环遍历有序部分的元素。在内层循环中，比较待排序元素与有序部分的元素，将大于待排序元素的元素后移一位，直到找到合适的位置插入待排序元素。

最后，将待排序元素插入到有序部分的最后一个位置。重复以上步骤，直到所有的元素都被插入到有序部分，完成排序。

在主函数中，创建了一个包含10个元素的整数数组，并调用InsertSort函数对其进行排序。最后，输出排序前和排序后的数组。

注意：这段代码使用的是C语言编写。