Chinaunix首页 | 论坛 | 博客
  • 博客访问: 131656
  • 博文数量: 38
  • 博客积分: 2050
  • 博客等级: 大尉
  • 技术积分: 471
  • 用 户 组: 普通用户
  • 注册时间: 2007-11-19 15:49
文章分类

全部博文(38)

文章存档

2009年(1)

2008年(37)

我的朋友

分类: LINUX

2008-06-09 14:17:48

几种排序算法的实现




//////////////////////////////////////////////////////////////////////////////////////////////
/*利用随机函数产生N个随机整数(2000以上),对这些数进行多种方法进行排序。

要求:

至少采用三种方法实现(提示,可采用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。
并把排序后的结果保存在不同的文件中。

统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法。
*/

////////////////////////////////////////////////////////////////////////////////////////////////
//distracb:
//   几种排序方法的实现


#include
<stdio.h>
#include
<time.h>
#include
<stdlib.h>

#define MAXSIZE  100
// const int MAXSIZE = 20 ;

//定义数据结构

typedef 
int KeyType;
typedef  
char InfoType;

typedef  
struct{
    KeyType key;
    InfoType otherinfo;
}
RcdType;  //记录类型

typedef 
struct{
    RcdType r[MAXSIZE
+1];
    
int length;
}
SqList;

typedef SqList HeapType;  
//堆采用顺序表存储结构表示

//函数声明部分
//(注意声明部分要加返回类型)
bool LT(KeyType a ,KeyType b);   //比较两个关键字大小的函数
void InsertSort(SqList L);   //直接插入排序
void BInsertSort(SqList L);  //折半插入排序
void BubbleSort(SqList L);  //冒泡排序
void QuickSort(SqList L);   //快速排序
void ShellSort(SqList L);   //希尔排序

//////////////////////////////////////////////////////////
bool LT(KeyType  a ,KeyType  b)
{
    
if(a <= b) return true;
    
else return false;
}

/*
//直接插入排序
void InsertSort(SqList L)
{
    for(int i=2;i<=L.length;i++)
    if(LT(L.r[i].key,L.r[i-1].key))
    {
        L.r[0]=L.r[i];       //复制为哨兵
        L.r[i]=L.r[i-1];
        for(int j=i-2;LT(L.r[0].key,L.r[j].key);j--)
        L.r[j+1]=L.r[j];       //记录后移
        L.r[j+1]=L.r[0];     //插入到正确位置
    }
    printf("after insertsort the recodelist is : ");
    for(i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
}


//折半插入排序
void BInsertSort(SqList L)
{
    for(int i=2;i<=L.length;i++)
    {
        L.r[0]=L.r[i];
        L.r[i]=L.r[i-1];
        int low=0,high=i-1;
        while(low        {
            int m=(low+high)/2;
            if(LT(L.r[0].key,L.r[m].key))
            high=m-1;
            else low=m+1;
        }
        for(int j=i-1;j>=high+1;j--)
        L.r[j+1]=L.r[j];       //记录后移
        L.r[high+1]=L.r[0];       //插入记录
    }
    printf("after Binary insertsort the recodelist is : ");
    for(i=1;i<=L.length;i++)
    printf("%d  ",L.r[i].key);
}


//希尔排序
void ShellInsert(SqList L ,int dk )  //一趟希尔插入排序
{
    for(int i=dk+1;i<=L.length;i++)
        if(LT(L.r[i].key,L.r[i-dk].key))
        {
            L.r[0]=L.r[i];
            for(int j=i-dk;(j>0) && LT(L.r[0].key,L.r[j].key);j-=dk)
            L.r[j+dk]=L.r[j];
            L.r[j+dk]=L.r[0];
        }
}

int dlta[]={8,4,2,1};  //增量序列dlta[k]=2^(t-k-1)  t为排序趟数4
int t=4;
void ShellSort(SqList L ,int dlta[],int t )
{
    for(int k=0;k    ShellInsert( L ,dlta[k] );
    
    printf("after ShellSort the recodelist is : ");
    for(int i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
}


//冒泡排序
void BubbleSort(SqList L)
{
    int flag=1;
    for(int i=1;i<=L.length && flag!=0;i++)
    {
        flag=0;
        for(int j=1;j<=(L.length-i);j++)
            if(LT(L.r[j].key,L.r[j+1].key))
            {
                RcdType temp = L.r[j];
                L.r[j] = L.r[j+1];
                L.r[j+1] = temp;
                flag=1;
            }
    }
    printf("after BubbleSort the recodelist is : ");
    for(i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
}


//快速排序
int Partition(SqList L,int low ,int high)  //一次划分
{
    L.r[0] = L.r[low];
    KeyType pivotkey = L.r[low].key;  //第一个记录作为枢轴记录
    while(low    {
        while((low < high) && LT(pivotkey,L.r[high].key))
          --high;
          L.r[low] = L.r[high];
        while(low            ++low;
            L.r[high] = L.r[low];
    }
    L.r[low]=L.r[0];       //枢轴记录到位
    return low;           //返回枢轴位置
}

void Qsort(SqList L,int low,int high)
{
    if(low    {
        int pivotkey = Partition(L,low,high);
        Qsort(L,pivotkey+1 ,high);
        Qsort(L,low,pivotkey-1);
    }

}

void QuickSort(SqList L)
{
    Qsort( L, 1, L.length);
    printf("after QuickSort the recodelist is : ");
    for(int i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
}


//简单选择排序
SelectMinKey(SqList,int); //声明

void SelectSort(SqList L)
{    
    for(int i=1;i    {
        int j = SelectMinKey(L,i); //在L.r[i....L.length]中选择一个最小的记录
        if(i!=j)   //交换记录
        {
            RcdType temp = L.r[j];
            L.r[j] = L.r[i];
            L.r[i] = temp;
        }
    }
    printf("after SelectSort the recodelist is : ");
    for(i=1;i<=L.length;i++)
    printf("%d ",L.r[i].key);
}

int SelectMinKey(SqList L,int i)  //寻找记录中最小值的位置
{
    KeyType k;
    int position;
    k = L.r[i].key;
    for(;i<=L.length;i++)
    {
        if(LT(L.r[i].key,k))
        {
            k = L.r[i].key;
            position=i;
        }
    }
    return position;
}

//堆排序


void HeapAdjust(HeapType H, int s ,int m)   //堆调整函数(筛选)
//已知H.r[s...m]中记录的关键字除H.r[s].key 之外均满足堆的定义,本函数调整H.r[s]的关键字
//使H.r[s....m]成为一个大顶堆(对其中的关键字而言)
{
    RcdType rc = H.r[s];  //现在的顶部结点
    for(int j=2*s;j<=m;j*=2)        //沿key 较大的孩子结点像下筛选
    {
        if(j        if(!LT(rc.key,H.r[j].key))  break;  //rc应插入在位置s上
        H.r[s]=H.r[j];
        s=j;
    }
    H.r[s]=rc;   //插入
}

void HeapSort(HeapType H)   //堆排序
{
    for(int i=H.length/2; i>0;i--)  //把H.r[1...L.length]建成大顶堆
    HeapAdjust( H, 1 ,H.length);
    for(i=H.length;i>1;i--)
    {
        RcdType temp = H.r[1];      //将堆顶记录和子序列H.r[1...i]中的最后一个记录交换
        H.r[1]=H.r[i];
        H.r[i]=temp;
        HeapAdjust(H, 1 ,i-1);  //重新调整为大顶堆
    }
    printf("after HeapSort the recodelist is : ");
    for(i=1;i<=H.length;i++)
    printf("%d ",H.r[i].key);
}

*/

//2-路归并排序
void Merge(RcdType SR[],RcdType TR[],int i,int m,int n)  /////////////????RcdType &TR[]为什么就提示好多错误??
//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
{
    
for(int k=i,j=m+1;(i<=m) && (j<=n);++k)  //将SR中的记录由小到大的并入到TR
    {
        
if(LT(SR[i].key,SR[j].key))
        TR[k]
= SR[i++];
        
else TR[k]=SR[j++];
    }

    
if(i<=m)
    

        
for(;i<=m;i++,k++)
        TR[k]
=SR[i];
    }

    
if(j<=n)
    
{
        
for(;j<=n;j++,k++)
        TR[k]
=SR[j];
    }

}


void MSort(RcdType SR[],RcdType TR1[],int s,int t)
//将SR[s..t]归并排序为TR1[s..t]
{
    RcdType TR2[
20]; ///////////////////////////////////////????????????????????这里应该定义数组多大呢 、?
    if(s == t) TR1[s]=SR[s];
    
else{
        
int m=(s+t)/2;  //将SR平分成两部分
        MSort(SR,TR2,s,m);  //递归地将SR[s..m]归并为有序的TR2[s.m]
        MSort(SR,TR2,m+1,t); //递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
        Merge(TR2,TR1,s,m,t); //将TR2[s.m]  TR2[m+1..t]归并到 TR1[s..m]
    }

}


void MerqeSort(SqList L)
{
    MSort(L.r,L.r,
1,L.length);
    printf(
"after MerqeSort the recodelist is : ");
    
for(int i=1;i<=L.length;i++)
    printf(
"%d ",L.r[i].key);
}


void menu()
{
    printf(
" *************************** ");
    printf(
" 1: Insert Sort ");
    printf(
" 2: BInsert Sort ");
    printf(
" 3: Bubble Sort ");
    printf(
" 4: Quick Sort ");
    printf(
" 5: Straight Selection Sort ");
    printf(
" 6: Heap Sort ");
    printf(
" 7: Merge Sort ");
    printf(
" 8: Exit ");
    printf(
" *************************** ");
}


//主函数
void main()
{
    SqList L;
    srand(
10);
    
for(int i=1;i<=MAXSIZE;i++)
    L.r[i].key
=rand()+2000;
    L.length
=MAXSIZE;
    
        menu();
        clock_t start, finish; 
double duration; 
/*        double duration[8]; 
        int count=0;
        
             start = clock();  
             InsertSort( L);
             finish = clock();  
             duration[count] = (double)(finish - start) / CLOCKS_PER_SEC; 
             printf( "InsertSort cost time %f seconds: ", duration[count] ); 
             count++;
             system("pause"); 
        
             start = clock();    
             BInsertSort( L);
             finish = clock();  
             duration[count] = (double)(finish - start) / CLOCKS_PER_SEC; 
             printf( "BInsertSort cost time %f seconds: ", duration[count] ); 
             count++;
             system("pause"); 
                 
             start = clock();
             ShellSort( L ,dlta,4 );
             finish = clock();  
             duration[count]= (double)(finish - start) / CLOCKS_PER_SEC; 
             printf( "ShellInsert cost time %f seconds: ", duration[count] ); 
             count++;
             system("pause"); 
         
             start = clock();
             BubbleSort( L);
             finish = clock();  
             duration[count] = (double)(finish - start) / CLOCKS_PER_SEC; 
             printf( "BubbleSort cost time %f seconds: ", duration[count]  ); 
             count++;
             system("pause"); 
                 
             start = clock();
             QuickSort( L);
             finish = clock();  
             duration[count] = (double)(finish - start) / CLOCKS_PER_SEC; 
             printf( "QuickSort cost time %f seconds: ", duration[count]  ); 
             count++;
             system("pause"); 
         
             start = clock();
             SelectSort(L);
             finish = clock();  
             duration[count] = (double)(finish - start) / CLOCKS_PER_SEC; 
             printf( "SelectSort cost time %f seconds: ", duration[count] ); 
             count++;
             system("pause"); 
                 
             start = clock();
             HeapSort( L);
             finish = clock();  
             duration[count] = (double)(finish - start) / CLOCKS_PER_SEC; 
             printf( "HeapSort cost time %f seconds: ", duration[count] ); 
             count++;
             system("pause"); 
*/
             
             start 
= clock();
             MerqeSort( L);
             finish 
= clock();  
        
//     duration[count] = (double)(finish - start) / CLOCKS_PER_SEC; 
        
//     printf( "MerqeSort cost time %f seconds: ", duration[count] ); 
             
//count++;
             duration = (double)(finish - start) / CLOCKS_PER_SEC; 
             printf( 
"MerqeSort cost time %f seconds: ", duration ); 
             system(
"pause"); 
         
/*         printf("compare the cost time here : ");
         for(count=0;count<8;count++)
         {
               printf( "T%d cost time %f seconds: ", count+1,duration[count] );
         }
*/
         
}

阅读(949) | 评论(0) | 转发(0) |
0

上一篇:LRU 算法

下一篇:LRU算法实现

给主人留下些什么吧!~~