1、插入排序
void InsertSort(RecType R[],int n){
int i,j,k;
RecType temp;
for (i=1; i<n; i++) {
temp=R[i];
j=i-1;
while (j>=0&&temp.key<R[j].key) {
R[j+1]=R[j];
j--;
}
R[j+1]=temp;
printf(" i=%d ",i);
for (k=0; k<n; k++) {
printf("%3d",R[k].key);
}
printf("\n");
}
}
2、冒泡排序
void BubbleSort(RecType R[],int n){
int i,j,k;
RecType temp;
for (i=0; i<n-1; i++) {
for (j=n-1; j>i; j--) {
if(R[j].key<R[j-1].key){
temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;
}
}
printf(" i=%d: ",i);
for (k=0; k<n; k++) {
printf("%2d",R[k].key);
}
printf("\n");
}
}
3、选择排序
void SelectSort(RecType R[],int n){
int i,j,k;
RecType temp;
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){
temp=R[i];
R[i]=R[k];
R[k]=temp;
}
printf(" i=%d: ",i);
for (k=0; k<n; k++) {
printf("%2d",R[k].key);
}
printf("\n");
}
}
4、希尔排序
void ShellSort(RecType R[],int n){
int i,j,d,k;
RecType temp;
d=n/2;
while (d>0) {
for (i=d; i<n; i++) {
j=i-d;
while (j>=0&&R[j].key>R[j+d].key) {
temp=R[j];
R[j]=R[j+d];
R[j+d]=temp;
j=j-d;
}
}
printf(" d=%d: ",d);
for (k=0; k<n; k++) {
printf("%3d",R[k].key);
}
printf("\n");
d=d/2;
}
}
5、快速排序
void QuickSort(RecType R[],int s,int t){
int i=s,j=t,k;
RecType temp;
if(s<t){
temp=R[s];
while(i!=j){
while(j>i&&R[j].key>temp.key)
j--;
if(i<j){
R[i]=R[j];
i++;
}
while(i<j&&R[i].key<temp.key)
i++;
if(i<j){
R[j]=R[i];
j--;
}
}
R[i]=temp;
printf(" ");
for(k=0;k<10;k++){
if(k==i){
printf(" [%d]",R[k].key);
}else{
printf("%4d",R[k].key);
}
}
printf("\n");
QuickSort(R,s,i-1);
QuickSort(R,i+1,t);
}
}
6、堆排序
void Sift(RecType R[],int low,int high){
int i=low,j=2*i;
RecType temp=R[i];
while(j<=high){
if(j<high&&R[j].key<R[j+1].key){
j++;
}
if(temp.key<R[j].key){
R[i]=R[j];
i=j;
j=2*i;
}else{
break;
}
}
R[i]=temp;
}
void HeapSort(RecType R[],int n){
int i;
RecType temp;
for(i=n/2;i>=1;i--)
Sift(R,i,n);
printf("初始堆: ");DispHeap(R,1,n);printf("\n");
for (i=n; i>=2; i--) {
printf("交换%d与%d,输出%d\n",R[i].key,R[1].key,R[1].key);
temp=R[1];
R[1]=R[i];
R[i]=temp;
Sift(R,1,i-1);
printf("筛选调整得到堆:");
DispHeap(R,1,i-1);
printf("\n");
}
}
7、归并排序
void Merge(RecType *R,int low,int m,int high)
{//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]
int i=low,j=m+1,p=0; //置初始值
RecType *R1; //R1是局部向量
R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
if(!R1)return; //申请空间失败
while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
while(i<=m) //若第1个子文件非空,则复制剩余记录到R1中
R1[p++]=R[i++];
while(j<=high) //若第2个子文件非空,则复制剩余记录到R1中
R1[p++]=R[j++];
for(p=0,i=low;i<=high;p++,i++)
R[i]=R1[p];//归并完成后将结果复制回R[low..high]
}
void MergeSort(RecType R[],int low,int high)
{//用分治法对R[low..high]进行二路归并排序
int mid;
if(low<high){//区间长度大于1
mid=(low+high)/2;//分解
MergeSort(R,low,mid);//递归地对R[low..mid]排序
MergeSort(R,mid+1,high); //递归地对R[mid+1..high]排序
Merge(R,low,mid,high);//组合,将两个有序区归并为一个有序区
}
}
分享到:
相关推荐
数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序
数据结构各种排序算法实现及比较 数据结构各种排序算法实现及比较 数据结构各种排序算法实现及比较
数据结构排序算法实现,文档中进行了比较,而且有代码!
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以...本资料详细总结了数据结构排序问题的实现与分析,希望对大家能有所帮助。
数据结构中几种排序的实现 数据结构中几种排序的实现
一、实验目的 1、掌握排序的不同方法,并能用高级语言实现排序算法 二、实验内容 1、实现希尔排序算法。
二叉排序树的实现 二叉排序补充概念(也可以参考书上第九章第二节) 左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,简单一点,二叉排序树左边的数据小于右边. ...课程设计数据结构二叉排序树
用c#代码实现快速排序 用c#代码实现快速排序 用c#代码实现快速排序 用c#代码实现快速排序
数据结构 各种排序 c语言 完整程序 完成1-20000的排序算法. 直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 希尔排序
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
数据结构之二叉排序树 数据结构之二叉排序树
算法:C语言实现第1-4部分基础知识、数据结构、排序及搜索
《算法:C语言实现(第1-4部分)基础知识、数据结构、排序及搜索(原书第3版)》细腻讲解计算机算法的C语言实现。全书分为四部分,共16章。包括基本算法分析原理,基本数据结构、抽象数据结构、递归和树等数据结构知识,...
数据结构排序一章的希尔结构排序,显示结果的
数据结构实验 各种排序的实现数据结构实验 各种排序的实现数据结构实验 各种排序的实现数据结构实验 各种排序的实现数据结构实验 各种排序的实现数据结构实验 各种排序的实现数据结构实验 各种排序的实现数据结构...
数据结构内的快速排序实现 内含测试程序 ·············
数据结构试验 排序问题的实现 内部排序等 C语言 源代码
起泡排序 直接插入排序 简单选择排序 快速排序 希尔排序 堆排序
数据结构的数据结构课程设计源代码,实现冒泡排序的源代码
数据结构-排序算法的实现(代码+报告)