直接插入排序。 #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)。

相关问题

#include <iostream> #define MAXSIZE 1000 using namespace std; typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void SelectSort(SqList &L) { int i,j,k; ElemType t; for(i=1; ;++i) { k=i; for(j=i+1; ;++j) if( ) k=j; if(k!=i) {t=L.r[i];L.r[i]=L.r[k];L.r[k]=t;} } } 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; } int main() { SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); SelectSort(L); show(L); return 0; }

这是一个使用选择排序算法对输入的一组数据进行排序的 C++ 程序。程序中定义了一个结构体类型 ElemType，其中 key 表示关键字，otherinfo 表示其他信息。另外还定义了一个 SqList 结构体类型，其中 r 指向 ElemType 类型的数组，length 表示数组的长度。程序中定义了函数 SelectSort，用于实现选择排序算法；函数 Create_Sq 用于创建 SqList 类型的数据；函数 show 用于输出排序后的结果。程序的主函数中先创建 SqList 类型的数据，然后调用 SelectSort 函数对数据进行排序，最后调用 show 函数输出排序后的结果。

将这段代码改为键盘输入需要排序的数字#include <iostream> using namespace std; #define MAXSIZE 100 typedef struct { int key; char* otherinfo; } ElemType; typedef struct { ElemType* r; int length; } SqList; void BubbleSort(SqList* L) { int m = L->length - 1; int flag = 1; ElemType t; while (m > 0 && flag == 1) { flag = 0; for (int j = 1; j <= m; j++) { if (L->r[j].key > L->r[j + 1].key) { flag = 1; t = L->r[j]; L->r[j] = L->r[j + 1]; L->r[j + 1] = t; } } m--; } } void InsertSort(SqList* L) { for (int i = 2; i <= L->length; i++) { if (L->r[i].key < L->r[i - 1].key) { L->r[0] = L->r[i]; int j; for (j = i - 1; L->r[0].key < L->r[j].key; j--) { L->r[j + 1] = L->r[j]; } L->r[j + 1] = L->r[0]; } } } int main() { int j; SqList L; L.r = new ElemType[MAXSIZE + 1]; L.length = 0; // 初始化 SqList 的 r 数组 for (int i = 1; i <= MAXSIZE; i++) { L.r[i].key = rand(); } L.length = MAXSIZE; printf("排序\n"); printf("***************************************************\n"); printf(" 1-----冒泡排序 \n"); printf(" 2-----直接插入 *\n"); printf

可以将代码改为以下形式，使用循环读取键盘输入的数字，并将其存储到数组中，然后再进行排序：

#include <iostream>
using namespace std;

#define MAXSIZE 100

typedef struct {
    int key;
    char* otherinfo;
} ElemType;

typedef struct {
    ElemType* r;
    int length;
} SqList;

void BubbleSort(SqList* L) {
    int m = L->length - 1;
    int flag = 1;
    ElemType t;
    while (m > 0 && flag == 1) {
        flag = 0;
        for (int j = 1; j <= m; j++) {
            if (L->r[j].key > L->r[j + 1].key) {
                flag = 1;
                t = L->r[j];
                L->r[j] = L->r[j + 1];
                L->r[j + 1] = t;
            }
        }
        m--;
    }
}

void InsertSort(SqList* L) {
    for (int i = 2; i <= L->length; i++) {
        if (L->r[i].key < L->r[i - 1].key) {
            L->r[0] = L->r[i];
            int j;
            for (j = i - 1; L->r[0].key < L->r[j].key; j--) {
                L->r[j + 1] = L->r[j];
            }
            L->r[j + 1] = L->r[0];
        }
    }
}

int main() {
    int n, j;
    SqList L;
    L.r = new ElemType[MAXSIZE + 1];
    L.length = 0; // 初始化 SqList 的 r 数组
    printf("请输入需要排序的数字个数（不超过100个）：");
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        printf("请输入第%d个数字：", i);
        scanf("%d", &(L.r[i].key));
    }
    L.length = n;
    printf("排序\n");
    printf("***************************************************\n");
    printf(" 1-----冒泡排序 \n");
    printf(" 2-----直接插入 *\n");
    printf("***************************************************\n");
    printf("请选择排序算法：");
    scanf("%d", &j);
    switch (j) {
    case 1:
        BubbleSort(&L);
        break;
    case 2:
        InsertSort(&L);
        break;
    default:
        printf("输入有误！\n");
        break;
    }
    printf("排序结果：\n");
    for (int i = 1; i <= L.length; i++) {
        printf("%d ", L.r[i].key);
    }
    printf("\n");
    return 0;
}