王道考研数据结构课后题代码题（2026版）——排序部分

一、前言

       本合集以王道考研《数据结构》辅导书（2026版）课后习题代码题部分为参考依据，给出课后习题代码题的可执行代码的实现，本合集使用编程语言以C/C++语言为主，也不限于使用Python和Java语言，本套合计代码由作者参考网络或部分《数据结构》书籍自主编码而成，既作为本人考研路上练习记录的办法，也为广大有需要的CSDN的伙伴们提供参考，若有鄙陋不足之处，请诸位大佬批评指教，在此万分感谢！

二、题目

题目1、给出关键字序列{4,5,1,2,6,3)的直接插入排序过程.（王道课后习题综合应用题8.2.4-01）

（一）直接插入排序算法思想

1. 初始假设 ：将数组的第一个元素视为一个有序序列，而剩下的元素视为无序序列。

2. 逐个插入 ：从第二个元素开始，依次将每个元素与前面的有序序列中的元素进行比较。具体来说，将当前元素与有序序列中的元素从后往前依次比较，找到第一个比它小的元素的位置，然后将当前元素插入到该位置之后，从而将有序序列的长度增加 1。

3. 重复过程 ：重复上述步骤，直到所有元素都插入到有序序列中，完成整个数组的排序。

（二）可执行C++代码

#include<iostream>
#include<vector>
using namespace std;
vector<int> num = {4,5,1,2,6,3};//直接插入排序算法---wandao26--8.2.4-01
void InsertSort(vector<int> &num)
{int n = num.size();int i,j,temp,count=1;bool flag = false; for(i=1;i<n;i++){if(num[i]<num[i-1]){flag = true;temp = num[i];for(j=i-1;j>=0&&temp<num[j];--j) num[j+1]=num[j];num[j+1]=temp; }printf("第%d趟排序后的序列为:\n",count);for(int k=0;k<num.size();k++) printf("%d ",num[k]);cout<<endl;count++;}	
} 
int main()
{InsertSort(num);printf("完全排序后的序列为:\n");for(int m=0;m<num.size();m++){printf("%d ",num[m]);}return 0;
}

附：运行结果截图

（三）代码具体实现说明

1. 初始数组 ：{4,5,1,2,6,3}

2. 第 1 趟排序 ：

   • 比较 5 和 4，发现 5 不小于 4，不进行插入操作，所以数组仍为 {4,5,1,2,6,3}，但没有输出第 1 趟排序结果。

3. 第 2 趟排序 ：

   • 比较 1 和 5，发现 1 小于 5，触发插入操作。

   • 将 1 插入到合适的位置，得到数组 {4,1,5,2,6,3}。

   • 输出第 1 趟排序后的序列为：4 1 5 2 6 3。

4. 第 3 趟排序 ：

   • 比较 2 和 5，发现 2 小于 5，触发插入操作。

   • 将 2 插入到合适的位置，得到数组 {4,1,2,5,6,3}。

   • 输出第 2 趟排序后的序列为：4 1 2 5 6 3。

5. 第 4 趟排序 ：

   • 比较 6 和 5，发现 6 不小于 5，不进行插入操作，数组仍为 {4,1,2,5,6,3}，所以输出第 3 趟排序后的序列为：4 1 2 5 6 3。

6. 第 5 趟排序 ：

   • 比较 3 和 6，发现 3 小于 6，触发插入操作。

   • 将 3 插入到合适的位置，得到数组 {4,1,2,3,5,6}。

   • 输出第 4 趟排序后的序列为：4 1 2 3 5 6。

7. 最终排序结果 ：完全排序后的序列为 {1,2,3,4,5,6}。

题目2、给出关键字序列(50,26,38,80,70,90,8,30,40,20)的希尔排序过程（取增量序列为d= (5,3,1})，排序结果为从小到大排列).(王道课后习题综合应用题8.2.4-02)

（一）希尔排序算法思想

1. 分组：将数组按特定间隔（增量，如n/2, n/4...1）分成多个子序列，每个子序列内的元素间隔相同；
2. 子序列插入排序：对每个子序列分别进行插入排序，使数组逐渐 “基本有序”；
3. 缩小间隔：逐步减小间隔至 1，最终对整个数组进行一次插入排序（此时数组接近有序，效率高）。
   通过减少逆序对数量，希尔排序比直接插入排序更高效，适用于中等规模数据。

（二）可执行C++代码

#include<iostream>
#include<vector>
using namespace std;//希尔排序算法---wandao26--8.2.4-02
void ShellSort(vector<int> &num)
{int n = num.size();int d[]={5,3,1};int i,j,k,index,count=1;//count 用于记录排序趟数for(index=0;index<3;index++)//遍历增量序列数组d,依次取出每个增量值{k = d[index];for(i=k;i<num.size();i++){int temp = num[i];j = i;while(j>=k&&temp<num[j-k])//在已排序的序列中找到插入位置,判断temp是否小于j-k索引处的元素{num[j]=num[j-k];//将j-k索引处的元素向后移动一位j-=k;}num[j] = temp; //将临时变量 temp 中存储的元素插入到找到的位置}printf("第%d趟排序后的序列为:\n",count);for(int x=0;x<num.size();x++) printf("%d ",num[x]);cout<<endl;count++;}
} 
int main()
{vector<int> num = {50,26,38,80,70,90,8,30,40,20};ShellSort(num);printf("完全排序后的序列为:\n");for(int m=0;m<num.size();m++){printf("%d ",num[m]);}return 0;
}

附：运行结果截图

（三）代码具体实现说明

1. 初始数组 ：{50,26,38,80,70,90,8,30,40,20}

2. 第一趟排序（增量 5） ：

   • 按照增量 5 将数组分为 5 个子序列，对每个子序列进行直接插入排序。

   • 排序后的数组为 {50,8,30,40,20,90,26,38,80,70}。

   • 输出第 1 趟排序后的序列为：50 8 30 40 20 90 26 38 80 70。

3. 第二趟排序（增量 3） ：

   • 按照增量 3 将数组分为 3 个子序列，对每个子序列进行直接插入排序。

   • 排序后的数组为 {26,8,30,40,20,80,50,38,90,70}。

   • 输出第 2 趟排序后的序列为：26 8 30 40 20 80 50 38 90 70。

4. 第三趟排序（增量 1） ：

   • 按照增量 1 将整个数组作为一个子序列，进行直接插入排序。

   • 排序后的数组为 {8,20,26,30,38,40,50,70,80,90}。

   • 输出第 3 趟排序后的序列为：8 20 26 30 38 40 50 70 80 90。

5. 最终排序结果 ：完全排序后的序列为 {8,20,26,30,38,40,50,70,80,90}。