第1关：插入排序与选择排序
#include<iostream> using namespace std; #define MAXSIZE 100 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef struct SqList { int *R; //顺序表基地址，元素存储位置为[1..length] int length; }SqList; void InsertSort(SqList &L) { //对顺序表L进行直接插入排序 int i, j; for (i = 2; i <= L.length; i++) { // 从第2个元素开始（第1个元素默认已排序） if (L.R[i] < L.R[i-1]) { // 当前元素比前一个元素小，需要插入 L.R[0] = L.R[i]; // 哨兵暂存当前元素 L.R[i] = L.R[i-1]; // 前一个元素后移 for (j = i-2; L.R[0] < L.R[j]; j--) { // 向前找插入位置 L.R[j+1] = L.R[j]; // 元素后移 } L.R[j+1] = L.R[0]; // 插入到正确位置 } } } void SelectSort(SqList &L) { //对顺序表L进行简单选择排序 int i, j, min_idx; for (i = 1; i <= L.length-1; i++) { // 第i趟排序，确定第i个位置的元素 min_idx = i; // 假设当前位置是最小值下标 for (j = i+1; j <= L.length; j++) { // 遍历未排序部分找最小值 if (L.R[j] < L.R[min_idx]) { min_idx = j; // 更新最小值下标 } } if (min_idx != i) { // 若最小值不在当前位置，交换 int temp = L.R[i]; L.R[i] = L.R[min_idx]; L.R[min_idx] = temp; } } }
第2关：快速排序
#include<iostream> using namespace std; #define MAXSIZE 100 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef struct SqList { int *R; //顺序表基地址，元素存储位置为[1..length] int length; }SqList; int Partition(SqList &L,int low,int high) { //实现快速排序的划分算法：以L.R[low]为基准，划分[low..high] L.R[0] = L.R[low]; // 哨兵暂存基准元素 while (low < high) { // 从右向左找小于基准的元素 while (low < high && L.R[high] >= L.R[0]) { high--; } L.R[low] = L.R[high]; // 小于基准的元素放到左部 // 从左向右找大于基准的元素 while (low < high && L.R[low] <= L.R[0]) { low++; } L.R[high] = L.R[low]; // 大于基准的元素放到右部 } L.R[low] = L.R[0]; // 基准元素放到最终位置 return low; // 返回基准元素的下标 } void QSort(SqList &L,int low,int high) { //实现快速排序算法，对顺序表L[low..high]进行快速排序 if (low < high) { int pivot = Partition(L, low, high); // 划分得到基准位置 QSort(L, low, pivot - 1); // 递归排序左子序列 QSort(L, pivot + 1, high); // 递归排序右子序列 } }
第3关：奇偶元素移动
#include<iostream> using namespace std; #define MAXSIZE 100 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef struct SqList { int *R; //顺序表基地址，元素存储位置为[1..length] int length; }SqList; void move(SqList L) { //将顺序表所有的奇数都移动到偶数之前 int low = 1; // 左指针（从第一个元素开始） int high = L.length; // 右指针（从最后一个元素开始） while (low < high) { // 左指针找偶数（找到则暂停） while (low < high && L.R[low] % 2 != 0) { low++; } // 右指针找奇数（找到则暂停） while (low < high && L.R[high] % 2 == 0) { high--; } // 交换左指针的偶数和右指针的奇数 if (low < high) { int temp = L.R[low]; L.R[low] = L.R[high]; L.R[high] = temp; } } }
第4关：第k小的数
#include<iostream> using namespace std; #define MAXSIZE 100 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef struct SqList { int *R; //顺序表基地址，元素存储位置为[1..length] int length; }SqList; // 快速选择的划分函数（同快速排序的Partition） int Partition(SqList &L, int low, int high) { L.R[0] = L.R[low]; // 哨兵暂存基准元素 while (low < high) { // 右指针找小于基准的元素 while (low < high && L.R[high] >= L.R[0]) { high--; } L.R[low] = L.R[high]; // 左指针找大于基准的元素 while (low < high && L.R[low] <= L.R[0]) { low++; } L.R[high] = L.R[low]; } L.R[low] = L.R[0]; return low; // 返回基准的最终位置 } int kth_elem(SqList L,int k) { //实现函数，返回顺序表内第k小的元素的值，若不存在返回-1 if (k < 1 || k > L.length) { // 检查k的合法性 return -1; } int low = 1, high = L.length; while (low <= high) { int pivot = Partition(L, low, high); // 划分后基准的位置 if (pivot == k) { // 基准位置恰好是第k小元素 return L.R[pivot]; } else if (pivot > k) { // 第k小元素在左半部分 high = pivot - 1; } else { // 第k小元素在右半部分 low = pivot + 1; } } return -1; // 理论上不会走到这一步 }
第5关：单链表排序
#include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef struct LNode { int data; struct LNode *next; }LNode, *LinkList; void ListSort(LinkList &L) { // 对带头结点的单链表L进行直接插入排序 if (L == NULL || L->next == NULL) { return; // 空链表或只有头结点，无需排序 } LNode *sorted = L->next; // 已排序部分的尾节点（初始为第一个有效节点） LNode *unsorted = sorted->next; // 未排序部分的头节点 sorted->next = NULL; // 已排序部分初始为单个节点，断开与后续的连接 while (unsorted != NULL) { LNode *curr = unsorted; // 当前待插入节点 unsorted = unsorted->next; // 未排序部分后移 // 找到curr在已排序部分的插入位置（prev的下一个节点应大于curr） LNode *prev = L; // 从头结点开始找前驱 while (prev->next != NULL && prev->next->data < curr->data) { prev = prev->next; } // 将curr插入到prev和prev->next之间 curr->next = prev->next; prev->next = curr; } }
