堆排序。 #include <iostream> #define MAXSIZE 1000 using namespace std; typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void HeapAdjust(SqList &L,int s,int m) { ElemType rc; int j; rc=L.r[s]; for(j=2*s;j<=m; j*=2 ) { if( j ) ++j; if( rc.key>=L.r[j].key ) break; L.r[s]=L.r[j]; s=j; } L.r[s]=rc; } void Create_Sq(SqList &L) { int i,n; cin>>n; //输入的值不大于 MAXSIZE for(i=1;i<=n;i++) { cin>>L.r[i].key; L.length++; } } void show(SqList L) { int i; for(i=1;i<=L.length;i++) if(i==1) cout<<L.r[i].key; else cout<<" "<<L.r[i].key; } //把无序序列L.r[1..n]建成大根堆 void CreatHeap(SqList &L) { int i,n; n=L.length; for(i=n/2;i>0;--i) HeapAdjust(L,i,n); } void HeapSort(SqList &L) { int i; ElemType x; CreatHeap(L); for( i=L.length;i>1;--i ) { x=L.r[1]; L.r[1]=L.r[i]; L.r[i]=x; HeapAdjust( L,1,i-1 ); } } int main() { SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); HeapSort(L); show(L); return 0; } 输入样例： 第一行输入一个数n(输入的值不大于 MAXSIZE)。 第二行依次输入n个数 9 30 45 53 78 65 9 12 17 23 输出样例： 输出升序排列的结果。 9 12 17 23 30 45 53 65 78

堆排序是一种基于完全二叉树结构的排序算法，它的核心思想是将待排序的数组看作是一棵完全二叉树，并将其转换为一个大顶堆或小顶堆。通过不断将根节点与最后一个节点交换，并重新构建大顶堆或小顶堆的方式来完成排序。它的时间复杂度为O(nlogn)，且是一种稳定的排序算法。

相关问题

运用代码 #include<iostream> #include<cstring> #define MAXSIZE 100 using namespace std; void Reverse(char *a,int n) {//递归实现字符串的逆序存储 }

好的，这是一个使用递归实现字符串逆序存储的基本框架，但没有完整地写出所有细节。在这个C++代码片段中，我们首先包含了必要的头文件`<iostream>`和`<cstring>`，然后定义了一个宏`MAXSIZE`表示数组的最大大小。`using namespace std;`使得我们可以直接使用标准库里的`std`命名空间。

`Reverse` 函数接收两个参数：一个是字符指针`a`，它指向要操作的字符串；另一个是整数`n`，表示字符串的长度。函数的目的是在原地（不额外分配新内存）将输入字符串翻转。

递归的核心思想会这样实现：
1. 首先判断字符串是否只有一个元素或为空，如果是，则无需做任何事情，直接返回；
2. 否则，将字符串的最后一个字符与第一个字符互换，然后递归调用 `Reverse` 函数处理剩下的子串（即去掉首尾已对齐的字符）。

下面给出一个简化的实现版本：

void Reverse(char* a, int n) {
    if (n == 1) {   // base case: one character or empty string
        return;
    }

    char temp = a[n - 1];  // store the last character
    a[n - 1] = a[0];     // swap it with the first character
    a[0] = temp;

    // recursive call on the remaining substring
    Reverse(a + 1, n - 1);
}

int main() {
    char str[MAXSIZE];
    // Fill the string and then call the function
    std::cin.getline(str, MAXSIZE);  // Read a line from user
    Reverse(str, strlen(str));       // Call the reverse function

    std::cout << "Reversed String: " << str << std::endl;
    return 0;
}

注意：在实际应用中，上述代码可能会遇到性能问题，因为每次递归都涉及字符串头部和尾部的元素交换，时间复杂度较高。如果需要优化，可以考虑使用迭代的方式来进行。

直接插入排序。 #include <iostream> #define MAXSIZE 1000 using namespace std; typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void InsertSort(SqList &L) { int i,j; for(i=2;i<=

L.length;i++) { //从第二个元素开始插入排序 　　　if(L.r[i].key<L.r[i-1].key) { 　　　　　L.r[0]=L.r[i]; //哨兵 　　　　　L.r[i]=L.r[i-1]; 　　　　　for(j=i-2;L.r[0].key<L.r[j].key;j--) { //从后往前比较 　　　　　　　L.r[j+1]=L.r[j]; //记录后移 　　　　　} 　　　　　L.r[j+1]=L.r[0]; //插入到正确位置 　　　} 　} }

以上是直接插入排序的 C++ 代码实现，使用了哨兵来简化代码。对于一个长度为n的序列，平均时间复杂度为O(n^2)，最坏时间复杂度为O(n^2)，空间复杂度为O(1)。