#include <iostream> using namespace std; #define MAXSIZE 1000 #define T 3 typedef int KeyType; //关键字项类型定义 typedef int InfoType; //其他数据项类型定义 //typedef string ElemType; typedef struct { KeyType key; InfoType otherinfo; }RedType; //记录类型 typedef struct BSTNode { RedType r[MAXSIZE+1]; int length; }SqList; //希尔插入排序 void ShellInsert(SqList &L,int dk) { int i,j; for( i=dk+1; i <= L.length; i++) { if(L.r[i].key < L.r[i-dk].key) { L.r[0] = L.r[i]; //将L.r[i]插入有序增量子表 L.r[i] = L.r[i-1]; //暂存在L.r[0] for( j=i-dk; j>0 && L.r[0].key < L.r[j].key; j-=dk) L.r[j+dk] = L.r[j]; //记录逐个后移，直到找到插入位置 L.r[j+dk] = L.r[0]; //将r[0]就是r[i]插入到正确位置 }//if }//for } //按增量序列dt[0..t-1]对顺序表L进行t趟希尔排序 void ShellSort(SqList &L,int dt[],int t) { for( int k=0;k<t; k++) { ShellInsert(L,dt[k]); }//for } int main() { SqList L; int n,i,dt[T]={5,3,1}; cin >> n; L.length=n; for(i=1;i<=n;i++) { cin >> L.r[i].key; } ShellSort(L,dt,T); for(i=1;i<=n;i++) { cout << L.r[i].key <<" "; } //cout << "Hello world!" << endl; return 0; }

这是一段 C++ 代码，实现了希尔排序算法。其中定义了关键字项类型为整数型，其他数据项类型为整数型的记录类型 RedType。通过结构体 SqList 定义了一个长度为 MAXSIZE+1 的记录数组 r，以及数组的长度 length。主函数中读入了需要排序的元素个数 n 和每个元素的值，以及增量序列 dt。然后调用 ShellSort 函数进行排序。排序过程中，先按照增量序列进行希尔插入排序，然后逐渐缩小增量，直到增量为 1，完成最后一趟直接插入排序。排序完成后，输出排序后的数组。

相关问题

//折半查找 #include<iostream> #include<fstream> #include<string> #include <algorithm> using namespace std; #define MAXSIZE 10000 #define KEYSIZE 10//关键词个数 #define OK 0 #define ERROR -1 typedef string KeyType; typedef struct { KeyType key;//关键字域 int count;//词频 int index;//在关键词列表中的序号 }ElemType; typedef struct { ElemType *R;//存储空间基地址 int length;//当前长度 }SSTable; //关键词列表 KeyType key[KEYSIZE] = {"little","prince","sheep","flowers","believe","stars","one","my","he","the"}; //初始化一个空的查找表ST //ST的0号单元闲置不用 int InitSSTable(SSTable &ST) { /*-----------代码开始--------------*/ /*-----------代码结束--------------*/ return OK; }

折半查找（二分查找）是一种高效的查找算法，它要求待查找的序列必须是有序的。它的基本思想是：首先确定待查找区间的中间位置，然后将待查找关键字与中间位置关键字进行比较，如果相等则查找成功；否则根据比较结果确定下一步查找的区间，直到找到所需的关键字或者区间为空为止。

在代码中，SSTable是一个结构体，它包含了一个关键字数组和一些其他的属性，如当前长度等。InitSSTable函数的作用是初始化一个空的查找表ST，即将ST中的R指向一个新分配的空间，并将其长度初始化为0。

实现函数sort #include<iostream> using namespace std; #define MaxSize 20 typedef char KeyType; typedef struct { //字母 KeyType character; //字频 int count; } RedType; void merge(RedType SR[], RedType TR[], int i, int m, int n) { } void Sort(RedType SR[], RedType TR1[], int s, int t) { } int main() { //统计结果，已经按字母序排好序 RedType SR[MaxSize]; //按照字频排序后的结果 RedType TR1[MaxSize]; string data; int i = 0; //读取输入 while (i < MaxSize && cin >> data) { SR[i].character = data[0]; SR[i++].count = stoi(data.substr(1, data.length())); if (cin.get() == '\n') { break; } } //排序 Sort(SR, TR1, 0, i - 1); //打印排序后的结果 for (int j = 0; j < i; ++j) { cout << TR1[j].character << TR1[j].count << " "; } }

下面是使用归并排序对 RedType 数组按照字频进行排序的 C++ 代码实现：

#include<iostream>
using namespace std;

#define MaxSize 20

typedef char KeyType;

typedef struct {
    //字母
    KeyType character;
    //字频
    int count;
} RedType;

//归并排序合并两个有序序列
void merge(RedType SR[], RedType TR[], int i, int m, int n) {
    int j = m + 1;
    int k = i;

    while (i <= m && j <= n) {
        if (SR[i].count <= SR[j].count) {
            TR[k++] = SR[i++];
        } else {
            TR[k++] = SR[j++];
        }
    }

    while (i <= m) {
        TR[k++] = SR[i++];
    }

    while (j <= n) {
        TR[k++] = SR[j++];
    }
}

//归并排序
void Sort(RedType SR[], RedType TR1[], int s, int t) {
    if (s == t) {
        TR1[s] = SR[s];
    } else {
        int m = (s + t) / 2;
        RedType TR2[MaxSize];
        Sort(SR, TR2, s, m);
        Sort(SR, TR2, m + 1, t);
        merge(TR2, TR1, s, m, t);
    }
}

int main() {
    //统计结果，已经按字母序排好序
    RedType SR[MaxSize];
    //按照字频排序后的结果
    RedType TR1[MaxSize];

    string data;
    int i = 0;

    //读取输入
    while (i < MaxSize && cin >> data) {
        SR[i].character = data[0];
        SR[i++].count = stoi(data.substr(1, data.length()));

        if (cin.get() == '\n') {
            break;
        }
    }

    //排序
    Sort(SR, TR1, 0, i - 1);

    //打印排序后的结果
    for (int j = 0; j < i; ++j) {
        cout << TR1[j].character << TR1[j].count << " ";
    }

    return 0;
}

在主函数中，先读取输入的统计结果，然后调用`Sort`函数进行排序，最后输出排序后的结果。`Sort`函数使用归并排序算法进行排序，先将原始序列分成两个子序列，分别对两个子序列进行排序，最后将两个有序子序列合并成一个有序序列。`merge`函数用于合并两个有序序列，具体实现过程中，先将原始序列复制到临时数组中，然后分别从两个子序列中取出较小的元素放入目标序列中，直到有一个子序列为空，最后将剩余的元素依次放入目标序列中。