|
/*
* sort.c
*
* Created on: 2010-12-22
* Author: qiang
*/
#include <stdio.h>
#include <stdlib.h>
#define LENGTH 5
typedef int Status;
typedef int ElemType;
//直接插入排序
Status InsertSort(ElemType *r,int len)
{
int i,j; //无序列表i,有序列表j
for(i=2;i<=len;i++) //把第一个元素看成有序列，进行len-1次插入
{
if(r[i]<r[i-1])
{
r[0]=r[i]; //将a[i]复制为哨兵
r[i]=r[i-1]; //后移，留出空位
for(j=i-2;r[0]<r[j];j--) //j=i-2,指向有序列最后一个元素
r[j+1]=r[j]; //有序列后移，找出插入的位置
r[j+1]=r[0];
}
}
return 0;
}
//我的插入算法
Status myinsert(ElemType *r,int len)
{
int i,j;
for(i=2;i<=len;i++)
{
r[0]=r[i];
if(r[0]<r[i-1])
{
r[i]=r[i-1]; //后移
j=i-2; //j指向有序列最后一个元素
while(r[0]<r[j])
{
r[j+1]=r[j];//有序列后移
j--;
}
r[j+1]=r[0];
}
}
return 0;
}
//冒泡排序-大数下沉
Status BubbleSort(ElemType *r,int len)
{
int i,j;
ElemType tmp;
for(i=0;i<len;i++)
for(j=0;j<len-i;j++)
{
if(r[j]>r[j+1])
{
tmp=r[j];
r[j]=r[j+1];
r[j+1]=tmp;
}
}
return 0;
}
//快速排序
int Partition(ElemType *r,int low,int high)
{
ElemType pivotkey;
r[0]=r[low]; //存放第一个元素到r[0]
pivotkey=r[low]; //将第一个元素作为曲轴记录点
while(low<high)
{
while(low<high&&r[high]>=pivotkey)
high--;
r[low]=r[high]; //交换位置
while(low<high&&r[low]<=pivotkey)
low++;
r[high]=r[low]; //交换位置
}
r[low]=r[0]; //将保护的元素r[0]插入到合适的位置
return low; //返回曲轴位置
}
Status QSort(ElemType *r,int low,int high)
{
int pivotloc; //定义曲轴位置
if(low<high)
{
pivotloc = Partition(r,low,high);
QSort(r,low,pivotloc-1); //对前段分区进行递归排序
QSort(r,pivotloc+1,high); //对后段分区进行递归排序
}
return 0;
}
//希尔插入排序
//前后记录的位置增量是k,而不是1；r[0]是暂存单元，而不是哨兵
Status ShellSort(ElemType *r,int len)
{
int k; //假定增量k
for(k=len/2;k>0;k--) //0
{
//一趟增量k插入法排序
int i,j;
for(i=k+1;i<=len;i++) //注意范围
{
if(r[i]<r[i-k])
{
r[0]=r[i]; //将r[i]暂存到r[0]
j=i-k;
while(j>0&&r[0]<r[j])
{
r[j+k]=r[j];
j-=k;
}
r[j+k]=r[0];
}
}
} //end_for
return 0;
}
int main()
{
int i;
ElemType a[LENGTH],r[LENGTH+1];
r[0]=0; //预留出r[0]哨兵位置
printf("请输入5个排序的字符： \n");
for(i=0;i<5;i++)
{
scanf("%d",&a[i]);
r[i+1]=a[i]; //为插入法排序打下基础
}
/*
//插入法排序
myinsert(r,LENGTH);
printf("InsertSort result: \n");
int j;
for(j=1;j<=LENGTH;j++)
printf("data: %d \n",r[j]);
*/
/*
//冒泡法排序
BubbleSort(a,LENGTH);
printf("BubbleSort result: \n");
int j;
for(j=0;j printf("data: %d \n",a[j]);
*/
/*
//快速排序
QSort(r,1,LENGTH);
printf("QSort result: \n");
int j;
for(j=1;j<=LENGTH;j++)
printf("data: %d \n",r[j]);
*/
//Shell排序
ShellSort(r,LENGTH+1);
printf("ShellSort result: \n");
int j;
for(j=1;j<=LENGTH;j++)
printf("data: %d \n",r[j]);
return 0;
}
|
