基于C语言实现的6种排序算法的排序系统
排序系统
题目:自定义一个大小和元素自设的数组,能选择六种排序任意一个排序算法进行排序,并输出结果
需求分析:
需求1:需要设定一个大小和元素都可以自设的数组。
需求2:需要六种排序算法。
需求3:需要设定一个选择结构。
需求4:能循环使用 (没说自己加的)
设计流程
(1) 选择是否进入系统
(2) 输入要设计数组得大小
(3) 给数组中输入元素
(4) 选择排序得方法
(5) 输出结果
(6) 清屏并返回(1)操作
主要结构
重要代码片段
{
printf("\n\n 选择排序方法,用该方法排序并输出:
\n 0.简单排序
\n 1.直接插入排序
\n 2.冒泡排序
\n 3.快速排序
\n 4.归并排序
\n 5.堆排序
\n 6.退出\n");
scanf("%d",&n2);
switch(n2)
{
case 0:{SelectSort(a, n1);Print(a,n1);} break; //简单排序
case 1:{InsertSort(a, n1);Print(a,n1);} break; //直接插入排序
case 2:{bubbling_sort(a,n1);Print(a,n1);}break; //冒泡排序
case 3:{quickSort(a, 0, n1-1);Print(a,n1);} break; //快速排序
case 4:{MergeSort(a, b, n1);Print(b,n1);}break; //归并排序
case 5: {HeapSort(a,n1);Print(a,n1);}break; //堆排序
case 6:{flag=0;}break;
default:printf("请输入(0~6)范围之内的数字");
}
system("pause");
system("cls"); }break;
case 1:return 0;break;
}
程序思路
先利用switch语句设置一排序系统进入界面,进入选0,退出选1;
选择0进入case 0:后{}中的排序系统;代码为上面的重要代码片段
选择要采用的排序算法,因为有system(“pause”);代码,所以在结果界面会停下;
最后system(“cls”);清屏
排序算法可以参考的博客:https://blog.csdn.net/a3192048/article/details/80269862
我的代码
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
void Print(int a[],int n)
{
printf("排序后的结果为: ");
for (int j = 0; j<n; j++)
{
printf("%d ",a[j]);
}
printf("\n");
}
int SelectMinKey(int a[], int n, int i)
{
int k = i;
for (int j = i + 1; j< n; j++) {
if (a[k] > a[j])
k = j;
}
return k;
}
void SelectSort(int a[], int n) {
int key, tmp;
for (int i = 0; i < n-1; i++) {
key = SelectMinKey(a, n, i); //选择最小的元素
if (key != i) {
tmp = a[i];
a[i] = a[key];
a[key] = tmp; //最小元素与第i位置元素互换
}
}
}
//直接插入排序
void InsertSort(int a[], int n)
{
for (int i = 1; i<n; i++)
{
if (a[i] < a[i - 1])
{
int j = i - 1;
int x = a[i]; //将带插入的数赋值为哨兵
while (x < a[j]) //将比哨兵小的上移动一个单位,直到和哨兵一样大的或者比哨兵小的,将哨兵插入该位置后一个单位。
{
a[j + 1] = a[j]; //记录后移
j--;
}
a[j + 1] = x;
}
}
}
//冒泡排序
void bubbling_sort(int a[],int n)
{
int temp;
for (int i = 0; i < n - 1; ++i)
{
for (int j = 0; j < n - i - 1; ++j)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
//快速排序
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int a[], int low, int high)
{
int privotKey = a[low]; //基准元素
while (low < high)
{ //从表的两端交替地向中间扫描
while (low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
swap(&a[low], &a[high]);
while (low < high && a[low] <= privotKey) ++low;
swap(&a[low], &a[high]);
}
return low;
}
void quickSort(int a[], int low, int high)
{
if (low < high)
{
int privotLoc = partition(a, low, high); //将表一分为二
quickSort(a, low, privotLoc - 1); //递归对低子表递归排序
quickSort(a, privotLoc + 1, high); //递归对高子表递归排序
}
}
//归并排序
void Merge(int *r,int *rf, int i, int m, int n)
{
int j,k;
for(j=m+1,k=i; i<=m && j <=n ; ++k){
if(r[j] < r[i]) rf[k] = r[j++];
else rf[k] = r[i++];
}
while(i <= m) rf[k++] = r[i++];
while(j <= n) rf[k++] = r[j++];
}
void MergeSort(int *r, int *rf, int lenght)
{
int len = 1;
int *q = r ;
int *tmp ;
while(len < lenght) {
int s = len;
len = 2 * s ;
int i = 0;
while(i+ len <lenght){
Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
i = i+ len;
}
if(i + s < lenght){
Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并
}
tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf
}
}
//堆排序
void HeapAdjust(int H[],int s, int length)
{
int tmp = H[s];
int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
while (child < length) {
if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
++child ;
}
if(H[s]<H[child]) { // 如果较大的子结点大于父结点
H[s] = H[child]; // 那么把较大的子结点往上移动,替换它的父结点
s = child; // 重新设置s ,即待调整的下一个结点的位置
child = 2*s+1;
} else { // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出
break;
}
H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
}
}
/**
* 初始堆进行调整
* 将H[0..length-1]建成堆
* 调整完之后第一个元素是序列的最小的元素
*/
void BuildingHeap(int H[], int length)
{
//最后一个有孩子的节点的位置 i= (length -1) / 2
for (int i = (length -1) / 2 ; i >= 0; --i)
HeapAdjust(H,i,length);
}
/**
* 堆排序算法
*/
void HeapSort(int H[],int length)
{
//初始堆
BuildingHeap(H, length);
//从最后一个元素开始对序列进行调整
for (int i = length - 1; i > 0; --i)
{
//交换堆顶元素H[0]和堆中最后一个元素
int temp = H[i]; H[i] = H[0]; H[0] = temp;
//每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整
HeapAdjust(H,0,i);
}
}
int main()
{
int a[MAXSIZE];
int b[MAXSIZE];
int key;
int n1,n2;
int flag=1;
while(flag)
{
printf("------------欢迎来到排序系统-------------\n");
printf("| |\n");
printf("|----0.进入系统---------1.退出系统------|\n");
printf("| |\n");
printf("-----------------------------------------\n");
scanf("%d",&key);
switch(key)
{
case 0:{
printf("请输入您要输入数组的大小:");
scanf("%d",&n1);
if(n1<=0)
{
printf("输入数字不符合要求,请重新输入(大于0):\n ");
scanf("%d",&n1);
}
printf("请依次输入数据:");
for(int i=0;i<n1;i++)
{
scanf("%d",&a[i]);
}
printf("该数组中未排序前的值为:");
for (int j = 0; j<n1; j++)
{
printf("%d ",a[j]);
}
printf("\n\n 选择排序方法,用该方法排序并输出:\n 0.简单排序\n 1.直接插入排序\n 2.冒泡排序\n 3.快速排序\n 4.归并排序\n 5.堆排序\n 6.退出\n");
scanf("%d",&n2);
switch(n2)
{
case 0:{SelectSort(a, n1);Print(a,n1);} break;
case 1:{InsertSort(a, n1);Print(a,n1);} break;
case 2:{bubbling_sort(a,n1);Print(a,n1);}break;
case 3:{quickSort(a, 0, n1-1);Print(a,n1);} break;
case 4:{MergeSort(a, b, n1);Print(b,n1);}break;
case 5: {HeapSort(a,n1);Print(a,n1);}break;
case 6:{flag=0;}break;
default:printf("请输入(0~6)范围之内的数字");
}
system("pause");
system("cls"); }break;
case 1:return 0;break;
}
}
return 0;
}