用C语言编写代码:1.任务:设计一个内部排序算法模拟系统,利用该系统实现常用的7种排序算法,并测试各种排序算法的性能。 2.内容:通过一个简单的菜单,分别实现下列排序要求,采用几组不同数据测试各排序算法的性能(比较次数和移动次数)及稳定性。 实现简单选择排序、直接插入排序和冒泡排序; 实现折半插入排序; 实现希尔排序算法; 实现快速排序算法(递归和非递归); 实现堆排序算法。 实验说明: 1.输入和输出: (1)输入形式:根据菜单提示选择排序算法,输入一组带排序数据。 (2)输出形式:输出排序结果(体现排序过程),及排序过程中数据的比较次数和移动次数,判断排序算法的稳定性。 2.实验要求: 实现一个简单的交互式界面,包括系统菜单、清晰的输入提示等。 要输出每一趟排序的结果。 能够上机编辑、调试出完整的程序。 3.数据类型定义 #define MAXSIZE 100 /*参加排序元素的最大个数*/ typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; // 其他字段(自行设计) }RedType; typedef struct { RedType r[MAXSIZE+1]; int length; /*参加排序元素的实际个数*/ }SqList;
时间: 2024-02-14 20:15:55 浏览: 106
排序算法,用C语言来做的
以下是C语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 100 /*参加排序元素的最大个数*/
typedef int KeyType;
typedef struct {
KeyType key;
//其他字段(自行设计)
}RedType;
typedef struct {
RedType r[MAXSIZE+1];
int length; /*参加排序元素的实际个数*/
}SqList;
/* 交换L中数组r的下标为i和j的记录 */
void Swap(SqList *L, int i, int j) {
RedType temp;
temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
/* 输出排序结果 */
void PrintList(SqList L) {
int i;
for (i = 1; i <= L.length; i++) {
printf("%d ", L.r[i].key);
}
printf("\n");
}
/* 1. 简单选择排序 */
void SelectSort(SqList *L) {
int i, j, min;
for (i = 1; i <= L->length - 1; i++) {
min = i;
for (j = i + 1; j <= L->length; j++) {
if (L->r[j].key < L->r[min].key) {
min = j;
}
}
if (min != i) {
Swap(L, i, min);
}
printf("第%d趟排序结果:", i);
PrintList(*L);
}
}
/* 2. 直接插入排序 */
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];
for (j = i - 1; L->r[j].key > L->r[0].key; j--) {
L->r[j+1] = L->r[j];
}
L->r[j+1] = L->r[0];
}
printf("第%d趟排序结果:", i-1);
PrintList(*L);
}
}
/* 3. 冒泡排序 */
void BubbleSort(SqList *L) {
int i, j;
for (i = 1; i <= L->length - 1; i++) {
for (j = L->length - 1; j >= i; j--) {
if (L->r[j].key > L->r[j+1].key) {
Swap(L, j, j+1);
}
}
printf("第%d趟排序结果:", i);
PrintList(*L);
}
}
/* 4. 折半插入排序 */
void BinaryInsertSort(SqList *L) {
int i, j, low, high, mid;
for (i = 2; i <= L->length; i++) {
L->r[0] = L->r[i];
low = 1;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (L->r[0].key < L->r[mid].key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (j = i - 1; j >= high + 1; j--) {
L->r[j+1] = L->r[j];
}
L->r[high+1] = L->r[0];
printf("第%d趟排序结果:", i-1);
PrintList(*L);
}
}
/* 5. 希尔排序 */
void ShellSort(SqList *L) {
int i, j, k;
int increment = L->length;
do {
increment = increment / 3 + 1;
for (i = increment + 1; i <= L->length; i++) {
if (L->r[i].key < L->r[i-increment].key) {
L->r[0] = L->r[i];
for (j = i - increment; j > 0 && L->r[0].key < L->r[j].key; j -= increment) {
L->r[j+increment] = L->r[j];
}
L->r[j+increment] = L->r[0];
}
}
printf("增量为%d的排序结果:", increment);
PrintList(*L);
} while (increment > 1);
}
/* 6. 快速排序 */
int Partition(SqList *L, int low, int high) {
int pivot = L->r[low].key;
while (low < high) {
while (low < high && L->r[high].key >= pivot) {
high--;
}
L->r[low] = L->r[high];
while (low < high && L->r[low].key <= pivot) {
low++;
}
L->r[high] = L->r[low];
}
L->r[low].key = pivot;
return low;
}
void QSort(SqList *L, int low, int high) {
if (low < high) {
int pivotpos = Partition(L, low, high);
printf("第%d趟排序结果:", pivotpos);
PrintList(*L);
QSort(L, low, pivotpos - 1);
QSort(L, pivotpos + 1, high);
}
}
void QuickSort(SqList *L) {
QSort(L, 1, L->length);
}
/* 7. 堆排序 */
void HeapAdjust(SqList *L, int s, int m) {
int j;
RedType temp = L->r[s];
for (j = 2 * s; j <= m; j *= 2) {
if (j < m && L->r[j].key < L->r[j+1].key) {
j++;
}
if (temp.key >= L->r[j].key) {
break;
}
L->r[s] = L->r[j];
s = j;
}
L->r[s] = temp;
}
void HeapSort(SqList *L) {
int i;
for (i = L->length / 2; i > 0; i--) {
HeapAdjust(L, i, L->length);
}
for (i = L->length; i > 1; i--) {
Swap(L, 1, i);
HeapAdjust(L, 1, i - 1);
printf("第%d趟排序结果:", L->length - i + 1);
PrintList(*L);
}
}
int main() {
SqList L;
int i;
srand(time(NULL));
printf("请输入数据的个数(不超过%d):", MAXSIZE);
scanf("%d", &L.length);
if (L.length > MAXSIZE) {
printf("输入的数据个数不能超过%d\n", MAXSIZE);
exit(1);
}
printf("请输入%d个数据:\n", L.length);
for (i = 1; i <= L.length; i++) {
scanf("%d", &L.r[i].key);
}
printf("输入的数据为:");
PrintList(L);
printf("请选择排序算法:\n");
printf("1. 简单选择排序\n");
printf("2. 直接插入排序\n");
printf("3. 冒泡排序\n");
printf("4. 折半插入排序\n");
printf("5. 希尔排序\n");
printf("6. 快速排序\n");
printf("7. 堆排序\n");
int choice;
scanf("%d", &choice);
switch (choice) {
case 1:
SelectSort(&L);
break;
case 2:
InsertSort(&L);
break;
case 3:
BubbleSort(&L);
break;
case 4:
BinaryInsertSort(&L);
break;
case 5:
ShellSort(&L);
break;
case 6:
QuickSort(&L);
break;
case 7:
HeapSort(&L);
break;
default:
printf("请输入1-7之间的数字\n");
break;
}
printf("排序后的结果为:");
PrintList(L);
return 0;
}
```
注意,这只是一个简单的模拟系统,实际上还有很多细节需要注意,比如输入的数据类型、排序算法的复杂度等等。为了更好地理解和学习,建议先自己手动模拟几个排序算法的过程,再去看代码实现。
阅读全文