李春葆《数据结构》-排序-课后习题代码

void fun(int a[],int n,int b[]){
int i;
for(i=0;i<n;i++){
b[[ai]-1]=a[i];
}
} 

void DBobbleSort(ElemType A[], int n) {
    int i = 0, j; // 初始化变量i为0，用于控制外层循环次数；j为内层循环的索引。
    bool exchange = true; // 初始化exchange为true，用于控制外层while循环是否继续执行。

    while (exchange) { // 当exchange为true时，继续执行循环。
        exchange = false; // 每次进入循环时，将exchange设置为false。
        
        // 从后往前找最小元素，并将其放到前面的位置。
        for (j = n - i - 1; j > i; j--) {
            if (A[j].key < A[j - 1].key) { // 如果当前元素的键值小于前一个元素的键值，则交换它们。
                exchange = true; // 设置exchange为true，表示发生了交换。
                swap(A[j], A[j - 1]); // 交换两个元素的位置。
            }
        }
        
        // 从前往后找最大元素，并将其放到后面的位置。
        for (j = i; j < n - i - 1; j++) {
            if (A[i].key > A[j + 1].key) { // 如果当前元素的键值大于后一个元素的键值，则交换它们。
                exchange = true; // 设置exchange为true，表示发生了交换。
                swap(A[j], A[j + 1]); // 交换两个元素的位置。
            }
        }
        
        if (!exhange) return; // 如果在某次循环中没有发生任何交换，则排序完成，退出函数。
        i++; // 增加i的值，缩小下一次循环的范围。
    }
}

代码：

void SelectSort1(ElemType A[],int n,int m){
int i,j,max;
for(i=0;i<m,i++){//前m个，则外层循环m次 
max=i;//假设第一个为最大值 
for(j=i+1;j<n;j++){//与后面元素进行比较，判断是否为最大值 
if(A[j].key>A[max].key){
max=j;
}
}
if(max!=i){
swap(A[i].A[max]);//交换 
}
}
} 

四：对于给定的含有 n 元素的无序数据序列（所有元素的关键字不相同），利用快速排序方法求这个序列中第 k（1≤k≤n）小元素的关键字，并分析所设计算法的最好和平均时间复杂度。

代码：

int QuickSort(ElemType A[],int low,int high,int k){
ElemType temp;
if(low!=high){
temp=A[low];
while(low<high){
while(low<high&&A[high].key>=temp.key){
high--;
}
A[low]=A[high];
while(low<high&&A[low].key<=temp.key){
low++;
}
A[high]=A[low];
}
A[low]=temp;
if(k-1==low) return A[low].key;
else if(k-1<i)  return QuickSort(A,s,low-1,k);//左边找 
else return QuickSort(A,low+1,high,k);//右边找  
}else if(low==high&&low==k-1){//只有一个元素，而且为要找的关键词 
retuen A[k-1].key;
}else  return -1;//返回错误 
} 

五：设 n 个记录 R[0..n-1]的关键字只取 3 个值：0，1，2。采用基数排序方法将这 n 个记录排序。并用相关数据进行测试。

代码：

#include "seqlist.cpp" // 包含顺序表基本运算算法的头文件
#include <malloc.h>    // 包含动态内存分配函数的头文件
#define Max 3          // 定义链队的最大数量为3

// 定义节点结构体，用于存储记录和指向下一个节点的指针
typedef struct node {
    RecType Rec;       // 记录数据
    struct node *next; // 指向下一个节点的指针
} NodeType;

// 基数排序函数，对记录数组R进行排序，n为记录的数量
void RadixSort1(RecType R[], int n) {
    NodeType *head[Max], *tail[Max], *p, *t; // 定义各链队的首尾指针
    int i, k;

    // 初始化各链队首、尾指针为空
    for (i = 0; i < Max; i++) {
        head[i] = tail[i] = NULL;
    }

    // 遍历记录数组，将每个记录插入到对应的链队中
    for (i = 0; i < n; i++) {
        p = (NodeType *)malloc(sizeof(NodeType)); // 创建新节点
        p->Rec = R[i];                            // 将记录赋值给新节点
        p->next = NULL;                           // 新节点的next指针置空
        k = R[i].key;                             // 根据记录的key值确定链队编号

        // 如果对应链队为空，则初始化该链队
        if (head[k] == NULL) {
            head[k] = p;
            tail[k] = p;
        } else {
            // 否则将新节点插入到链队的尾部
            tail[k]->next = p;
            tail[k] = p;
        }
    }

    p = NULL;

    // 将所有非空链队合并成一个单链表
    for (i = 0; i < Max; i++) {
        if (head[i] != NULL) { // 如果链队不为空
            if (p == NULL) {
                p = head[i]; // 第一个非空链队的头节点作为结果链表的头节点
                t = tail[i]; // 更新结果链表的尾节点
            } else {
                t->next = head[i]; // 将当前链队的头节点连接到结果链表的尾部
                t = tail[i];       // 更新结果链表的尾节点
            }
        }
    }

    i = 0;
    // 将排序后的结果从链表中取出并放回原数组R中
    while (p != NULL) {
        R[i++] = p->Rec;
        p = p->next;
    }
}

int main() {
    int i, n = 5;
    RecType R[MAXL] = {{1, 'A'}, {0, 'B'}, {0, 'C'}, {2, 'D'}, {1, 'F'}};

    printf("排序前:\n");
    for (i = 0; i < n; i++) {
        printf("[%d,%c] ", R[i].key, R[i].data); // 打印排序前的记录数组
    }
    printf("\n");

    RadixSort1(R, n); // 调用基数排序函数对记录数组进行排序

    printf("排序后:\n");
    for (i = 0; i < n; i++) {
        printf("[%d,%c] ", R[i].key, R[i].data); // 打印排序后的记录数组
    }
    printf("\n");

    return 1; // 返回1表示程序正常结束
}