1、实验目的
实现几种典型的排序算法
2、实验具体要求
分别利用直接插入/折半插入/希尔/冒泡/快速/简单选择排序算法实现将待排序序列{26,6,18,8,36,66,56,76，99}由小到大排序，并输出结果。
3、实验设计思路（编程语言、模块划分及函数功能描述等）
模块划分及函数功能描述：
主函数模块main():主函数负责整个程序的控制流程，包括初始化待排序数组、调用各种排序算法进行排序、打印排序前后的数组状态。
排序算法函数模块:每种排序算法都被实现为一个独立的函数，各自负责对传入的数组进行排序。每个排序算法函数均有统一的参数形式，即待排序数组和数组长度。函数内部实现按照各自算法的逻辑进行数组操作，确保最终数组按照升序排列。
辅助函数模块:
printArray() 函数负责打印数组内容，用于在排序前后显示数组状态。
partition() 函数是快速排序的辅助函数，负责确定分区点并进行数组元素交换。
函数功能描述：
排序算法函数
·直接插入排序 (insertionSort())：
从第二个元素开始，逐个将元素插入已排序序列的适当位置。
·折半插入排序 (binaryInsertionSort())：
利用二分搜索找到插入位置，然后移动元素以插入新元素。
·希尔排序 (shellSort())：
根据不同的步长进行插入排序，步长逐渐减小直至为1。
·冒泡排序 (bubbleSort())：
依次比较相邻的两个元素，将较大的元素向后移动，每一轮将最大的元素移动到最后。
·快速排序 (quickSort() 和 partition())：
使用递归方式分治数组，将小于分区点的元素放到左边，大于分区点的元素放到右边，然后对左右两部分递归调用快速排序。
·简单选择排序 (selectionSort())：
每次从未排序部分选择最小的元素，与当前位置进行交换。
<3>.辅助函数
·printArray() 函数：
打印数组内容，用于在排序前后显示数组状态。
实验流程：初始化阶段：在 main() 函数中定义待排序数组 arr。调用 printArray() 打印初始数组内容。
排序阶段：分别调用六种排序算法函数对数组进行排序，每种排序算法均在独立的函数中实现特定的排序逻辑。每次排序完成后，调用 printArray() 打印排序后的数组内容。
4、实验源程序、程序调试结果
源程序：
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 20
typedef int KeyType;
typedef char InfoType;
typedef struct {
KeyType key;
InfoType data;
}RecType;
// 创建顺序表
void CreateList(RecType R[], KeyType keys[], int n) {
for (int i = 0; i < n; i++) {
R[i].key = keys[i];
}
}
// X,Y交换
void swap(RecType& x, RecType& y) {
RecType tmp = x;
x = y;
y = tmp;
}
//输出顺序表
void DispList(RecType R[], int n) {
for (int i = 0; i < n; i++)
printf("%5d", R[i].key);
printf("\n");
}
// 直接插入排序
void InsertSort(RecType R[], int n) {
int i, j;
RecType tmp;
for (i = 1; i < n; i++) {
if (R[i].key < R[i - 1].key) {
tmp = R[i];
j = i - 1;
do {
R[j + 1] = R[j];
j--;
} while (j >= 0 && R[j].key > tmp.key);
R[j + 1] = tmp;
}
}
DispList(R, n);
}
// 折半插入排序
void BinInsertSort(RecType R[], int n) {
int i, j, low, high, mid;
RecType tmp;
for (i = 1; i < n; i++) {
if (R[i].key < R[i - 1].key) {
tmp = R[i];
low = 0; high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (tmp.key < R[mid].key)
high = mid - 1;
else
low = mid + 1;
}
for (j = i - 1; j >= high; j--)
R[j + 1] = R[j];
R[high + 1] = tmp;
}
}
DispList(R, n);
}
//希尔排序
void ShellSort(RecType R[], int n) {
int i, j, d;
RecType tmp;
d = n / 2;
while (d > 0) {
for (i = d; i < n; i++) {
tmp = R[i];
j = i - d;
while (j >= 0 && tmp.key < R[j].key) {
R[j + d] = R[j];
j = j - d;
}
R[j + d] = tmp;
}
d = d / 2;
}
DispList(R, n);
}
// 冒泡排序
void BubbleSort(RecType R[], int n) {
int i, j;
bool flag;
for (i = 0; i < n - 1; i++) {
flag = false;
for (j = n - 1; j > i; j--)
if (R[j].key < R[j - 1].key) {
swap(R[j], R[j - 1]);
flag = true;
}
if (!flag)
return;
}
}
// 快速排序
int partition(RecType R[], int s, int t) {
int i = s, j = t;
RecType tmp = R[i];
while (i < j) {
while (j > i && R[j].key >= tmp.key)
j--;
R[i] = R[j];
while (i < j && R[i].key <= tmp.key)
i++;
R[j] = R[i];
}
R[i] = tmp;
return i;
}
void QuickSort(RecType R[], int s, int t) {
int i;
if (s < t) {
i = partition(R, s, t);
QuickSort(R, s, i - 1);
QuickSort(R, i + 1, t);
}
}
// 简单选择排序
void SelectSort(RecType R[], int n) {
int i, j, k;
for (i = 0; i < n - 1; i++) {
k = i;
for (j = i + 1; j < n; j++)
if (R[j].key < R[k].key)
k = j;
if (k != i)
swap(R[i], R[k]);
}
DispList(R, n);
}
int main() {
int n = 12;
RecType R1[MaxSize], R2[MaxSize], R3[MaxSize], R4[MaxSize], R5[MaxSize], R6[MaxSize], R7[MaxSize];
KeyType a1[] = { 3,6,2,10,1,20,88,8,5,7,4,9 };
CreateList(R1, a1, n);
printf("原序列：\n");
DispList(R1, n);
printf("直接插入排序：\n");
InsertSort(R1, n);
KeyType a2[] = { 3,6,2,10,1,20,88,8,5,7,4,9 };
CreateList(R2, a2, n);
printf("折半插入排序：\n");
BinInsertSort(R2, n);
KeyType a3[] = { 3,6,2,10,1,20,88,8,5,7,4,9 };
CreateList(R3, a3, n);
printf("希尔排序：\n");
ShellSort(R3, n);
KeyType a4[] = { 3,6,2,10,1,20,88,8,5,7,4,9 };
CreateList(R4, a4, n);
printf("冒泡排序：\n");
BubbleSort(R4, n);
DispList(R4, n);
KeyType a5[] = { 3,6,2,10,1,20,88,8,5,7,4,9 };
CreateList(R5, a5, n);
printf("快速排序：\n");
QuickSort(R5, 0, n - 1);
DispList(R5, n);
KeyType a6[] = { 3,6,2,10,1,20,88,8,5,7,4,9 };
CreateList(R6, a6, n);
printf("简单选择排序：\n");
SelectSort(R6, n);
system("pause");
}调试结果：
5、程序调试过程中遇到的问题及解决办法
CreateList函数未初始化数据部分：虽然这不影响排序算法的实现，但如果需要用到RecType的data字段，应该在创建时或后续操作中进行初始化。
解决方法：
如果需要在后续操作中使用data字段，可以在CreateList函数中或后续某个地方进行初始化。
6、实验收获与体会
加深了对排序算法的理解：通过实现不同的排序算法，对它们的原理、优缺点和适用场景有了更深入的理解。