一、前言

? ? ? ?本合集以王道考研《數據結構》輔導書（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}。