注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

简约男人

简约,不能简单

 
 
 

日志

 
 
关于我

一个过分渴望被理解的人其实就是一个软弱的人, 勇往直前的力量来自斩钉截铁的决心,不是来自别人的理解.

网易考拉推荐

各种各样的排序算法分析(二)   

2009-10-03 11:26:37|  分类: 算法学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一、归并排序

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>


using std::cout;
using std::endl;

//将两个有序的数组归并为一个有序的数组或者将一个数组中
//两个有序的部分归并为有序的。
//如果数组只有一个元素,则这个数组肯定有序。把两个含有
//一个元素的数组归并为一个有序数组。
//使用递归的思想,把一个数组一分为二,如果数组任一部分
//有多于一个元素,则对继续对每一部分用归并排序,最后归
//并这两个各含一个元素的数组。函数返回上一层。

//以对数组a中的记录a[1..n]按递增序排序为列

//把一个有两个有序部分且长度分别为len1和len2的数组归并为一个有序数组
template<typename T>
void Merge(T *a,const int len1,const int len2)
{
    int *a1=new int[len1];
    int *a2=new int[len2];

    int len=len1+len2;
    int i,j,k,l;

    memcpy(a1,a,len1*sizeof(T));
    memcpy(a2,a+len1,len2*sizeof(T));
    i=0;
    j=0;
    for (k=0;k<len;k++)
    {
        if (i<len1&&j<len2)
        {
            if (a1[i]<a2[j])
                a[k]=a1[i++];
            else
                a[k]=a2[j++];
        }

        else if (i<len1&&j>=len2)
            a[k]=a1[i++];

        else if (j<len2&&i>=len1)
            a[k]=a2[j++];

    }
    delete[] a1;
    delete[] a2;
}

//归并两有序数组a1,a2,结果放入a中
template<typename T>
void Tmerge(T * a,T * a1,T * a2,int n1,int n2)
{
    int i=0,j=0,len = n1+n2;

    for (int k = 0; k < len; k++)
    {
        if (i<n1&&j<n2)
        {
            if (a1[i]<a2[j])
                a[k]=a1[i++];
            else
                a[k]=a2[j++];
        }
        else if (i<n1&&j>=n2)
            a[k]=a1[i++];
        else if (j<n2&&i>=n1)
            a[k]=a2[j++];
    }
}


//归并排序 分治思想
void MergeSort(int*a,int len) //len表示数组的大小
{
    int c;
    if (len > 1)
    {
        c=len/2;
        MergeSort(a,c);
        MergeSort(a+c,len-c);
        Merge(a,c,len-c);
    }

}

//二路归并排序
void Tmergesort(int * a,int size)
{
    int i,j;
    for (i=1;i<size;i*=2)
    {
        for (j=0;j+2*i<=size;j=j+2*i)
            Merge(a+j,i,i);//归并长度为i的两个相邻串
        if (j+i-1<size)
            Merge(a+j,i,size-i-j);
    }
}

//就地归并
template<typename T>
void merge_sort(T * a,int size)
{
    int    i,j = 0,k = 1,l;
    int   *sorted = new int[size];

    for (i = 1; i < size; i++)
    {
        if (a[i] >= a[i-1])
        {
            k++;
        }
        else
        {
            sorted[j] = k;
            k = 1;
            j++;
        }
    }

    sorted[j] = k;
    j++;

    k = sorted[0];

    for (i = 1; i < j; i++)
    {
        Merge(a,k,sorted[i]);
        k += sorted[i];
    }

    delete [] sorted;
}

int main()
{
    const unsigned SIZE = 2000;
    int i;
    int *a = new int[SIZE];
    clock_t start,end;
    srand(time(0));
    for (i = 0;i < SIZE;i++)
        a[i] = rand();
    start = clock();
    merge_sort(a,SIZE);
    end = clock();
    cout <<"我们用了 "<< (end -start) <<"个CPU时钟的时间来排序" <<endl;
/*
    for (i=1;i<=SIZE;i++)
    {
        cout<<std::ios::right<<a[i-1]<<" ";
        if (i%12 == 0)
            cout <<endl;
    }
    cout<<endl;
*/
    return 0;
}

二、堆排序

#include <iostream>
#include <cstdlib>
using namespace std;

//堆,就是完全二叉树。没有有兄弟节点的节点一定是叶子节点的二叉树
 
//若堆的根节点存储的值大于所有其它节点存储的值则该堆被称作大根堆

//将用数组表示的堆调整为大根堆,根节点放到数组的起始位。再把数组
//中的最后一个元素与第一个元素交换,此时最后的元素就是最大值。然
//后把数组最后一个元素之前的所有元素组成的数组调整为大根堆。重复
//调整为堆和替换的操作直到某次调整数组只有一个元素。此时就完成了
//以对数组a中的记录a[1..n]按递增序排序为列

//降序排列可以用调整小根堆的办法

void HeapAdjust(int *a,int root,int len)
{
    int child,x=a[root];
    while (child=root<<1|1,child<len)
    {
        if (child<len-1 && a[child]<a[child+1])
      child++;
        if (x<a[child])
        {
            a[root]=a[child];
            root=child;
        }
        else break;
    }
    a[root]=x;
}

//堆排序
void HeapSort(int*a,int len)
{
    for (int i=len/2-1;i>=0;i--)
        HeapAdjust(a,i,len);
    
    while (--len)
    {
        swap(a[0],a[len]);
        HeapAdjust(a,0,len);
    }
}


//最大堆,符合父节点大于左孩子,左孩子大于右孩子的完全二叉树。
//最小堆,符合父节点小于左孩子,左孩子小于右孩子的完全二叉树。

//可见用最大堆、最小堆也可排序。使用最大(小)堆排序有两种方式
//第一如上所述,将堆用数组表示,不断将堆的根节点与数组的最后
//一个元素替换。然后将除去最后一个元素的数组调整为最大(小)堆
//再重复调整为堆和替换的操作直到某次调整数组只有一个元素。

//第二,新构造一个堆,不断将堆中的根节点删除,并按删除顺序放
//入到数组中。

//第二种方法明显效率要高于第一种及前述几种。因为第二种,将堆
//的根节点删除后只需将堆进行一次调整;而前述两种,每一的交换
//都需对堆进行初始化操作。

//说句实话,前两种方法和选择排序几乎没区别。弃堆于一旁,再看
//前两种方法就是,在数组选择最大或最小的元素,放到数组的最后
//然后在除去最后一个元素的数组中选择最大或最小的元素放到缩小
//了的数组的最后。这不就是选择排序吗?
int main()
{
    int a[10]={15,6,3,16,25,48,48,59,23,12};
    HeapSort(a,10);
    cout<<a[0];
    for (int i=1;i<10;i++)
    {
        cout<<","<<a[i];
    }
}

三、快速排序

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
using std::cout;
using std::swap;
using std::endl;

//如果数组只有两或者三个元素,将大于其中一个值的元素放到一边
//另一个元素放到另一边。则这个数组就变为有序的了。那么对于有n
//个元素的数组,从其中任选一个值作为基准(轴值),将大于此值的
//元素放到一边,小于此值的元素放到另一边。这样就把数组分为了
//两段。把每一段都看作一个数组,执行上面的分区操作,直到所有
//子数组都有不多于3个元素且分为有序数组。

//以对数组a中的记录a[1..n]按递增序排序为列

//调整a中从n到num间的元素
//将小于轴值的元素放到轴值左边,
//大于轴值的元素放到轴值的右边
//返回调整后的轴元素位置
template<typename T>
int partition(T a[],int n,int num)
{
    int i=(n+num)/2; //确定一个轴值
    T b=a[i];

    while (n<num)
    { 
        //从左向右找到第一个小于轴值的元素
        while ((i<num)&&a[num]>=b)
            num--;
 
        //如果找到了小于轴值的元素
        //且该元素在轴值的左边
        //则交换改值与轴值
        if (num>i)
        {
            swap(a[i],a[num]);
            i=num; //改变轴值的位置
        }

        //从右向左找到第一个大于轴值的元素
        while ((n<i)&&a[n]<=b)
            n++;

        //如果找到了大于轴值的元素
        //且该元素在轴值的右边
        //则交换改值与轴值
        if (n<i)
        {
            swap(a[i],a[n]);
            i=n; //改变轴值的位置
        }
    }
    return i;
}

/*用快速排序法排列a中从n到num间的元素*/
template<typename T>
void quick_sort(T a[],int n,int m)
{
    if (m > n)
    {
        int q = partition(a,n,m);
        quick_sort(a,n,q-1);
        quick_sort(a,q+1,m);
    }
}

 

int main()
{
    const unsigned SIZE = 30000;
    int i;
    int *a = new int[SIZE];
    clock_t start,end;
    srand(time(0));
    for(i = 0;i < SIZE;i++)
        a[i] = rand();
    start = clock();
    quick_sort(a,0,SIZE-1);
    end = clock();
    cout <<"我们用了 "<< (end -start) <<"个CPU时钟的时间来排序" <<endl;
    /*
    for (i=0;i<SIZE;i++)
        cout<<a[i]<<" ";
    cout<<endl;*/
}

四、希尔排序

#include <iostream>
#include <cstdlib>
#include <cstring>

using std::cout;

//首先把数组中间隔一定步长的元素调整为有序的,然后任意
//缩小步长,再把数组中间隔缩小后的步长的元素调整为有序
//不断缩小步长。只要最后一次步长为一,就可以排序成功。

//这个算法的关键是选择步长,不可使用2的幂次步长,这将
//低算法的效率。原因复杂,俟后解决。

//前两个函数有问题
//希尔插入
void ShellInsert(int*a,int inc,int len)
{
    for (int i=inc;i<len;i+=inc)
    {
        int j=i,x=a[i];
        while (j>0 && a[j-inc]>x)
      a[j]=a[j-inc],j-=inc;
        a[j]=x;
    }
}

//插入式希尔排序
void ShellSort(int*a,int len)
{
    int inc=len;
    do
    {
        inc=inc/3+1;
        for(int s=0;s<inc;s++)
            ShellInsert(a-s,inc,len+s);
    }
    while (inc>1);
}

void ShellSort1(int* pData,int Count)
{
  int step[4];
  step[0] = 9;
  step[1] = 5;
  step[2] = 3;
  step[3] = 1;

  int iTemp;
  int k,s,w;
  for(int i=0;i<4;i++)
  {
    k = step[i];
    s = -k;
    for(int j=k;j<Count;j++)
    {
      iTemp = pData[j];
      w = j-k;//求上step个元素的下标
      if(s ==0)
      {
        s = -k;
        s++;
        pData[s] = iTemp;
      }
      while((iTemp<pData[w]) && (w>=0) && (w<=Count))
      {
        pData[w+k] = pData[w];
        w = w-k;
      }
      pData[w+k] = iTemp;
    }
  }
}


void shell(int *a,int n)
{
    int i,j,k,x;
    k=n/2; /*间距值*/
    while (k>=1)
    {
        for (i=k;i<n;i++)
        {
            x=a[i];
            j=i-k;
            while (j>=0&&x<a[j])
            {
                a[j+k]=a[j];
                j-=k;
            }
            a[j+k]=x;
        }
        k/=2; /*缩小间距值*/
    }
}


int main()
{
    int a[10]={15,6,3,16,25,48,48,59,23,12};
    shell(a,10);
    cout<<a[0];
    for (int i=1;i<10;i++)
    {
        cout<<","<<a[i];
    }
}

 

  评论这张
 
阅读(581)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017