[首页]
[文章]
[教程]
首页
Web开发
Windows开发
编程语言
数据库技术
移动平台
系统服务
微信
设计
布布扣
其他
数据分析
首页
>
编程语言
> 详细
各种排序算法的实现代码
时间:
2015-07-03 23:30:15
阅读:
724
评论:
0
收藏:
0
[点我收藏+]
#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
typedef int KeyType;
#define MAXSIZE 20
typedef struct
{
KeyType key;
}RedType;
typedef struct
{
RedType r[MAXSIZE+1];
int length;
}SqList,* SQLIST;
void play_choose(void);//显示菜单
void creat_list(SQLIST L) ;//创建顺序表
void traverse_list(SQLIST L);//遍历顺序表
int Search_Seq(SQLIST L,KeyType key);//顺序查找
void InsertSort(SQLIST L);//直接插入排序法
int Search_Bin(SQLIST L,KeyType key);//折半查找
void QSort(SQLIST L,int low,int high);//递归形式的快排
int Partition(SQLIST L,int low,int high);//递归形式的快排的一趟快排执行代码
void SelectSort(SQLIST L);//简单排序法
void Effervesce(SQLIST L);//冒泡排序
void BInsertSort(SQLIST L);//折半插入排序
void main()
{
int i;
int key=67,sum,sum1;
SQLIST L;
L=(SQLIST)malloc(sizeof(SqList));
if(L==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
play_choose();//显示菜单
while(true)
{
printf("\n\t请选择你要执行的操作:");
scanf("%d",&i);
switch(i)//实现用户选择操作
{
case 1:
creat_list(L);break;//创建顺序表
case 2:
printf("\n\t请选择你要查找的关键字的值:");//顺序查找
scanf("%d",&key);
sum=Search_Seq(L,key);
if(sum!=0)
{
printf("\n\t你要查找的关键字的值与第%d个元素相等\n",sum) ;
}
else
{
printf("\n你要查找的关键字不存在\n");
}
break;
case 3: InsertSort(L);traverse_list(L);break;//直接插入排序法
case 4: QSort(L,1,L->length);traverse_list(L);break;//递归形式的快排
case 5:
SelectSort(L);traverse_list(L);break;//简单排序法
case 6:Effervesce(L);traverse_list(L);break;//冒泡排序
case 7: BInsertSort(L);traverse_list(L);break;//折半插入排序
case 8: printf("\n\t请选择你要查找的关键字的值:");//折半查找
scanf("%d",&key);
Search_Bin(L,key);
sum1=Search_Bin(L,key);
if(sum1!=0)
{
printf("\n\t你要查找的关键字的值与第%d个元素相等\n",sum1) ;
}
else
{
printf("\n\t你要查找的关键字不存在\n");
}
break;
case 9: play_choose();traverse_list(L);break;//清屏显示菜单
case 0:
exit(-1);//退出
default:
printf("\t您输入的是非法值\n");
break;
}
}
}
void play_choose(void)
{
system("cls");
printf("\n\n\n\t\t.......................................\n\n\n");
printf("\t\t 1-建立顺序表 2-顺序查找 \n\n");
printf("\t\t 3-直接插入排序 4-快速排序 \n\n");
printf("\t\t 5-简单选择排序 6-冒泡排序 \n\n");
printf("\t\t 7-拆半插入排序 8-折半查找 \n\n");
printf("\t\t 9-清屏显示菜单 0-退出 \n\n");
printf("\n\n\t\t....................................... \n\n\n");
}
void creat_list(SQLIST L)//创建顺序表
{
int i;
int val;
int len;
printf("请输入你要建立的顺序表的长度(第一个位置不存储元素):");
scanf("%d",&len);
for(i=1;i<=len;i++)
{
printf("\t请输入第%d个元素的值:",i);
scanf("%d",&val);
L->r[i].key=val;
}
L->length=len;
printf("\n");
printf("\t\t\t恭喜您建表成功\n");
}
void traverse_list(SQLIST L)//遍历顺序表
{
printf("\t\t处理后的数据: ");
int i;
for(i=1;i<=L->length;i++)
{
printf("%d ",L->r[i].key);
}
printf("\n");
}
int Search_Seq(SQLIST L,KeyType key)//顺序查找
{
int i;
L->r[0].key=key;
for(i=L->length;L->r[i].key!=key;i--);
return i;
}
void InsertSort(SQLIST L)//直接插入排序法
{
int j,i;
for(i=2;i<=L->length;i++)
{
if(L->r[i].key < L->r[i-1].key)
{
L->r[0]=L->r[i];
L->r[i]=L->r[i-1];
for(j=i-2;L->r[0].key<L->r[j].key;j--)
{
L->r[j+1]=L->r[j];
}
L->r[j+1]=L->r[0];
}
}
}
int Search_Bin(SQLIST L,KeyType key)//折半查找
{
int low=1;
int high=L->length;
int mid;
while(low<=high)
{
mid=(low+high)/2;
if( key==L->r[mid].key)
return mid;
else if(key<L->r[mid].key) high=mid-1;
else low=mid+1;
}
return 0;
}
void QSort(SQLIST L,int low,int high)//递归形式的快排
{
int
pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
int Partition(SQLIST L,int low,int high)//递归形式的一趟快排
{
int pivotkey;
L->r[0]=L->r[low];
pivotkey=L->r[low].key;
while(low<high)
{
while(low<high && L->r[high].key>=pivotkey) --high;
L->r[low]=L->r[high];
while(low<high && L->r[low].key<=pivotkey) ++low;
L->r[high]=L->r[low];
}
L->r[low]=L->r[0];
return low;
}
void SelectSort(SQLIST L)//简单排序法
{
int k,i,j;
for(i=1;i<=L->length;++i)
{
j=i;
for(k=i+1;k<=L->length;k++)
{
if(L->r[k].key<L->r[j].key)
{
j=k;
}
}
if(i!=j)
{
RedType k=L->r[i];
L->r[i]=L->r[j];
L->r[j]=k;
}
}
}
void Effervesce(SQLIST L)//冒泡排序
{
int i,j;
for(i=1;i<L->length;i++)
{
for(j=1;j<=L->length-i;j++)
{
if(L->r[j].key>L->r[j+1].key)
{
RedType
temp=L->r[j];
L->r[j]=L->r[j+1];
L->r[j+1]=temp;
}
}
}
}
void BInsertSort(SQLIST L)//折半插入排序
{
int i,j,mid;
int low,high;
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];
}
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
各种排序算法的实现代码
原文:http://blog.csdn.net/u014180504/article/details/46745599
踩
(
1
)
赞
(
1
)
举报
评论
一句话评论(
0
)
登录后才能评论!
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
2021/09/28 scripts
2022-05-27
vue自定义全局指令v-emoji限制input输入表情和特殊字符
2022-05-27
9.26学习总结
2022-05-27
vim操作
2022-05-27
深入理解计算机基础 第三章
2022-05-27
C++ string 作为形参与引用传递(转)
2022-05-27
python 加解密
2022-05-27
JavaScript-对象数组里根据id获取name,对象可能有children属性
2022-05-27
SQL语句——保持现有内容在后面增加内容
2022-05-27
virsh命令文档
2022-05-27
教程昨日排行
更多>
1.
list.reverse()
2.
Django Admin 管理工具
3.
AppML 案例模型
4.
HTML 标签列表(功能排序)
5.
HTML 颜色名
6.
HTML 语言代码
7.
jQuery 事件
8.
jEasyUI 创建分割按钮
9.
jEasyUI 创建复杂布局
10.
jEasyUI 创建简单窗口
友情链接
汇智网
PHP教程
插件网
关于我们
-
联系我们
-
留言反馈
- 联系我们:wmxa8@hotmail.com
© 2014
bubuko.com
版权所有
打开技术之扣,分享程序人生!