一、需求
1.实现插入排序有关算法（直接插入排序、折半插入排序、希尔排序）
2.实现交换排序有关算法（冒泡排序、快速排序）
3.实现选择排序有关算法（简单选择排序、堆排序）
4.其他排序算法（归并排序、基数排序）
二、解决方案
1.采用顺序存储结构，待排关键字个数可变
2.采用顺序表判空函数和清空函数，实现一块内存多次使用，实现最低空间复杂度
三、代码
#include "pch.h"
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include"string.h"
#include"math.h"
#include<Windows.h>
#define MAXSIZE 100 //顺序表最大长度
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define RADIX 10
#define MAX_NUM_OF_KEY 8
#define MAX_SPACE 10000
typedef int KeyType; //关键字类型
typedef int Status;
typedef struct
{
KeyType key;
}RedType;
typedef struct
{
RedType r[MAXSIZE + 1]; //r[0]闲置或用作哨兵单元
int length ;
}SqList;
/**************创建顺序表******************/
Status InitSqList(SqList *S)
{
S->length = 0;
return OK;
}
/******************输入*********************/
Status Input(SqList *S)
{
int n;
printf("请输入待排整数序列的长度:");
scanf_s("%d", &n);
printf("请输入待排整数序列的关键字:");
for (int i = 1; i <=n; i++)
{
scanf_s("%d", &S->r[i].key);
S->length++; //顺序表长度与关键字个数统一，第二次调用Input,时length的内容已经被清空
}
return OK;
}
/*************直接插入排序******************/
Status InsearSort(SqList *S)
{
int j;
printf("直接插入排序后");
for (int i = 0; i <= S->length; ++i)
if (S->r[i].key < S->r[i - 1].key)
{
S->r[0] = S->r[i];
S->r[i] = S->r[i - 1];
for (j = i - 2; S->r[0].key < S->r[j].key; --j)
S->r[j + 1] = S->r[j];
S->r[j + 1] = S->r[0];
}
return OK;
}
/****************折半插入排序****************/
Status BInsertSort(SqList *S)
{
int low, high, mid;
int i, j;
printf("折半插入排序后");
for (i = 2; i <= S->length; ++i)
{
S->r[0] = S->r[i];
low = 1, high = i - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (S->r[0].key < S->r[mid].key)
high = mid - 1;
else
low = mid + 1;
}
for (j = i - 1; j >= high + 1; --j)
S->r[j + 1] = S->r[j];
S->r[high + 1] = S->r[0];
}
return OK;
}
/*************冒泡排序优化算法**************/
Status BubbleSort(SqList *S)
{
printf("冒泡排序后");
RedType tampe;
int change = TRUE;
for (int i = S->length; i > 1 && change; i--)
{
change = FALSE;
for (int j = 1; j < i; ++j)
if (S->r[j].key > S->r[j + 1].key)
{
tampe = S->r[j];
S->r[j] = S->r[j + 1];
S->r[j + 1] = tampe;
change = TRUE;
}
}
return OK;
}
/****************选择排序****************/
Status SelectSort(SqList *S)
{
printf("选择排序后");
int i, j, k;
for (i = 1; i <= S->length - 1; i++)
{
k = i;
for (j = i + 1; j <= S->length; ++j)
if (S->r[j].key < S->r[k].key)
k = j;
if (k != i)
{
RedType tampe = S->r[i];
S->r[i] = S->r[k];
S->r[k] = tampe;
}
}
return OK;
}
/**************希尔排序***************/
Status ShellInsert(SqList *S)
{
printf("希尔排序后");
int dk, i, j;
for (dk = S->length / 2; dk >= 1; dk = dk / 2)
{
for (i = dk + 1; i <= S->length; ++i)
if (S->r[i].key < S->r[i - dk].key)
{
S->r[0] = S->r[i];
for (j = i - dk; j > 0 && S->r[0].key < S->r[j].key; j -= dk)
S->r[j + dk] = S->r[j];
S->r[j + dk] = S->r[0];
}
}
return OK;
}
/*****************快速排序**************/
int Partition(SqList *S, int low, int high) //交换顺序表中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置
{
S->r[0] = S->r[low];
KeyType pivotkey = S->r[low].key;
while (low < high)
{
while (low < high&&S->r[high].key >= pivotkey)
--high;
S->r[low] = S->r[high];
while (low < high&&S->r[low].key <= pivotkey)
++low;
S->r[high] = S->r[low];
}
S->r[low] = S->r[0];
return low;
}
Status QSort(SqList *S, int low, int high) //对顺序表中的子序列S.r[low..high]做快速排序
{
if (low < high)
{
int pivotloc = Partition(S, low, high);
QSort(S, low, pivotloc - 1);
QSort(S, pivotloc + 1, high);
}
return OK;
}
Status QuickSort(SqList *S)
{
printf("快速排序后");
QSort(S, 1, S->length);
return OK;
}
/*****************堆排序******************/
Status HeapAdjust(SqList *S, int s, int m)
{
RedType rc = S->r[s];
for (int j = 2 * s; j <= m; j *= 2)
{
if (j < m && (S->r[j].key < S->r[j + 1].key))
{
j++;
}
if (rc.key >= S->r[j].key) break;
S->r[s] = S->r[j];
s = j;
}
S->r[s] = rc;
return OK;
}
Status HeapSort(SqList *S)
{
printf("堆排序后");
RedType tampe;
for (int i = S->length / 2; i > 0; --i)
{
HeapAdjust(S, i, S->length);
}
for (int i = S->length; i > 1; i--)
{
tampe = S->r[1];
S->r[1] = S->r[i];
S->r[i] = tampe;
HeapAdjust(S, 1, i - 1);
}
return OK;
}
/******************归并排序*******************/
Status Merge(RedType SR[], RedType TR[], int i, int m, int n) //如果需要将一个数组当作实参传入函数，则应把对应的形参声明成下面的形式,RedType TR[],当把数组名作为函数实参时，它会自动被转换为指针
{
int j, k;
for (j = m + 1, k = i; i <= m && j <= n; ++k)
{
if (SR[i].key <= SR[j].key)
{
TR[k] = SR[i++];
}
else {
TR[k] = SR[j++];
}
}
if (i <= m)
{
for (int a = 0; a <= m - i; a++)
TR[k + a] = SR[i + a];
}
if (j <= n)
{
while (n - j >= 0)
TR[k++] = SR[j++];
}
return OK;
}
Status MSort(RedType SR[], RedType TR1[], int s, int t)
{
RedType TR2[MAXSIZE + 1]; //定义与结构体类型中类型大小相同的数组
if (s == t)
TR1[s] = SR[s];
else
{
int m = (s + t) / 2;
MSort(SR, TR2, s, m);
MSort(SR, TR2, m + 1, t);
Merge(TR2, TR1, s, m, t);
}
return OK;
}
Status MergeSort(SqList *S)
{
//对整体做归并排序
printf("归并排序后");
MSort(S->r, S->r, 1, S->length);
return OK;
}
/***************基数排序****************/
int maxbit(RedType r[], int length) //保存最大的位数
{
int d = 1;
int p = 10;
for (int i = 1; i <= length; ++i)
{
while (r[i].key >= p)
{
p *= 10;
++d;
}
}
return d;
}
Status RadixSort(SqList *S)
{
printf("基数排序后");
int d = maxbit(S->r, S->length);
RedType *tmp = (RedType *)malloc(S->length * sizeof(RedType));
int count[10];
int i, j, k;
int radix = 1;
for (i = 1; i <= d; i++)
{
for (j = 0; j < 10; j++)
count[j] = 0;
for (j = 1; j <= S->length; j++)
{
k = (S->r[j].key / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for (j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //确认数据所放的位置
for (j = S->length; j > 0; j--)
{
k = (S->r[j].key / radix) % 10;
tmp[count[k] - 1] = S->r[j];
count[k]--;
}
for (j = 1; j <= S->length; j++) //将临时数组的内容复制到s.r中
S->r[j] = tmp[j - 1];
radix *= 10;
}
return OK;
}
Status Display(SqList S) //显示函数
{
printf("整数序列为:");
for (int i = 1; i <= S.length; i++)
printf("%d ", S.r[i].key);
printf("\n");
printf("\n");
return OK;
}
Status ClearSqList(SqList *S) //清空顺序表
{
S->length = 0;
return OK;
}
bool ListEmpty(SqList *S) //顺序表判空
{
return(S->length == 0);
}
int main()
{
SqList S;
InitSqList(&S); //创建顺序表
int i, k = 1;
while (k)
{
printf("*--------------排序-------------*\n");
printf("| 1.直接插入排序 |\n");
printf("| 2.折半插入排序 |\n");
printf("| 3.冒泡排序 |\n");
printf("| 4.选择排序 |\n");
printf("| 5.希尔排序 |\n");
printf("| 6.快速排序 |\n");
printf("| 7.堆排序 |\n");
printf("| 8.归并排序 |\n");
printf("| 9.基数排序 |\n");
printf("| 0.结束程序 |\n");
printf("*-------------------------------*\n");
printf("请输入你的选择(0-9):");
scanf_s("%d", &i);
switch (i)
{
case 1: {
if (!ListEmpty(&S))
ClearSqList(&S);
Input(&S);
InsearSort(&S);
Display(S);
break;
}
case 2: {
if (!ListEmpty(&S))
ClearSqList(&S);
Input(&S);
BInsertSort(&S);
Display(S);
break;
}
case 3: {
if (!ListEmpty(&S))
ClearSqList(&S);
Input(&S);
BubbleSort(&S);
Display(S);
break;
}
case 4: {
if (!ListEmpty(&S))
ClearSqList(&S);
Input(&S);
SelectSort(&S);
Display(S);
break;
}
case 5: {
if (!ListEmpty(&S))
ClearSqList(&S);
Input(&S);
ShellInsert(&S);
Display(S);
break;
}
case 6: {
if (!ListEmpty(&S))
ClearSqList(&S);
Input(&S);
QuickSort(&S);
Display(S);
break;
}
case 7: {
if (!ListEmpty(&S))
ClearSqList(&S);
Input(&S);
HeapSort(&S);
Display(S);
break;
}
case 8: {
if (!ListEmpty(&S))
ClearSqList(&S);
Input(&S);
MergeSort(&S);
Display(S);
break;
}
case 9: {
if (!ListEmpty(&S))
ClearSqList(&S);
Input(&S);
RadixSort(&S);
Display(S);
break;
}
case 0: {k = 0; printf("操作结束!"); break; }
default:printf("输入有误，请重新输入!");
break;
}
}
system("pause");
return 0;
}
四、运行结果演示
