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

简约男人

简约,不能简单

 
 
 

日志

 
 
关于我

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

网易考拉推荐

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

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

  下载LOFTER 我的照片书  |

一、标记排序

很简单,不需要分析看看代码注释吧。

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

using std::cout;
using std::swap;

//计算名次
template <class T>

void Rank(T *a, int n, int *r)

{
    //计算a [ 0 : n - 1 ]中n个元素的排名
    /*
        for ( int i = 0; i < n; i++)
            r[i] = 0;*/
    memset(r,0,n*sizeof(int));

    //逐对比较所有的元素

    for ( int i = 1; i < n; i++)

        for ( int j = 0; j < i; j++)
            if (a [j] <= a[i])
                r[i] ++ ;

            else r[j] ++ ;
}


//使用附加数组版
template <class T>

void Rearrange (T a[], int n)

{
    //按序重排数组a中的元素,使用附加数组u

    T *u = new T[n+1];

    int * r = new int[n];
    Rank(a,n,r);
    //在u中移动到正确的位置

    for ( int i = 0; i < n; i++)

        u[r[i]] = a[i];

    //移回到a中
/*
    for ( int i = 0; i < n; i++)

        a [i] = u [i] ; */
    memcpy(a,u,n*sizeof(T));

    delete [] u;
    delete [] r;


}

//就地排序版
template<class T>

void Rearrange1(T *a, int n)

{
    int * r = new int[n];

    Rank(a,n,r);
   
    // 原地重排数组元素

    for (int i = 0; i < n; i++)

        //  获取应该排在a [ i ]处的元素

        while(r[i] != i)
        {

            int t = r[i];

            swap(a[i], a[t]);

            swap(r[i], r[t]);

        }
    delete [] r;

}

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

 

二、冒泡排序

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

//冒泡排序以升序为列加以说明

//从数组的中第一个元素开始。将当前元素与后边紧邻的元素比较
//如果当前元素大于下一元素,则交换这两个元素。然后把下一个
//元素作为当前元素,进行上述操作。直到倒数第二个元素作为当
//前元素,完成了上述操作。此时最大值已被放到了最后。
//重复上述操作,但上述操作中的循环次数递减。重复的次数为数
//中元素个数减去1。

//上面的叫做正向冒泡。也可以逆向冒泡,即从最后一个元素开始
//不断的将小的冒到前边。下面的函数采用逆向冒泡。

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

void BubbleSort(int* pData,int Count)
{
    int iTemp;
    for (int i=1;i<Count;i++)
    {
        for (int j=Count-1;j>=i;j--)
        {
            if (pData[j]<pData[j-1])
            {
                iTemp = pData[j-1];
                pData[j-1] = pData[j];
                pData[j] = iTemp;
            }
        }
    }
}

//冒泡排序改进版
//如果在一次冒泡过程中没有发生元素互换,则说明数组已经有序,
//没有必要再继续进行冒泡过程。
template<class T>
bool Bubble(T a[], int n)
{
    //把 a[0:n-1]  中最大元素冒泡至右端
    bool swapped = false; //  尚未发生交换

    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] > a[i+1])
        {
            swap(a[i], a[i + 1]);
            swapped = true; // 发生了交换
        }
    }
    return swapped;
}

 

template<class T>
void BubbleSort(T a[], int n)

{
    // 及时终止的冒泡排序
    for (int i = n; i > 1 && Bubble(a, i); i--) ;
}

//双向冒泡排序
void Bubble2Sort(int* pData,int Count)
{
  int iTemp;
  int left = 1;
  int right =Count -1;
  int t,i;
  do
  {
    //正向的部分
    for(i=right;i>=left;i--)
    {
      if(pData[i]<pData[i-1])
      {
        iTemp = pData[i];
        pData[i] = pData[i-1];
        pData[i-1] = iTemp;
        t = i;
      }
    }
    left = t+1;

    //反向的部分
    for(i=left;i<right+1;i++)
    {
      if(pData[i]<pData[i-1])
      {
        iTemp = pData[i];
        pData[i] = pData[i-1];
        pData[i-1] = iTemp;
        t = i;
      }
    }
    right = t-1;
  }while(left<=right);
}


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

    return 0;
}


三、选择排序


#include <iostream>
#include <cstdlib>

//算法思想,首先在集合中找最大(小)的元素放到第一位,然后从
//余下的元素中找最大(小)的,放到第二位;如此直到剩下一个元素

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

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


template <class T>

void SelectionSort (T a[], int n)
{
    //对数组a [ 0 : n-1 ]中的n个元素进行排序
    for ( int size = n; size > 1; size--)
    {
        int j = 0;
        for(int i = 1;i < size; i++)
  {
   if(a[j] < a[i])
       j = i;
  }
        swap ( a[j], a[size-1]);
    }
}

//上述函数的缺点是:即使元素已经按序排列,程序仍然继续运行
//例如,即使在第二次循环过后数组元素可能已经有序.for循环仍
//需要执行n-1次。为了终止不必要的循环,在查找最大元素期间,
//可以顺便检查数组是否已按序排列。

template<typename T>
void selectionsort(T * a,int n)
{
    bool sorted = false;

    for (int size=n;(!sorted)&&(size>1);size--)
    {
        int pos=0;
        sorted = true;

        for (int i=1;i<size;i++)
        {
            if (a[pos]>a[i])
                sorted = false;
            else pos = i;
        }

        swap(a[pos],a[size-1]);
    }
}

int main()
{
    int a[10]={1,26,45,36,48,2,59,36,78,1};
    SelectionSort(a,10);
    for (int i=0;i<10;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

四、插入排序

//因为只有一个元素的数组是一个有序数组,所以可以从包含欲排序的n个
//元素的第一个元素的数组开始。通过把第二个元素插入到这个单元数组
//中,可以得到一个大小为 2 的有序数组。插入第三个元素可以得到一个
//大小为3的有序数组。按照这种方法继续进行下去,最终将得到一个大小
//为n 的有序数组,这种排序方式为插入排序(insertion sort )

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

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

using std::cout;


template<class T>
void Insert(T a[], int n, const T& x)
{
    //  向有序数组 a [ 0 : n - 1 ]中插入元素x
    int i;

    for (i = n-1; i >= 0 && x < a[i]; i--)
   
        a[i+1] = a[i];

    a[i+1] = x;

}

template<class T>
void InsertionSort(T a[], int n)
{
    // 对 a [ 0 : n-1 ]进行排序

    for (int i = 1; i < n; i++)
    {

        T t = a[i];

        Insert(a, i, t);

    }

}

template<class T>

void insertion_sort(T a[], int n)
{

    for (int i = 1; i < n; i++)
    {

        //将a [ i ]插入a [ 0 : i-1 ]

        T t = a[i];

        int j;

        for (j = i-1; j >= 0 && t < a[j]; j--)

            a[j+1] = a[j];

        a[j+1] = t;

    }

}

void Insert_Sort(int * R,int n)
{

    int i,j,x;
    for (i=1;i<n;i++)
    {
        x=R[i];
        j=i-1;
        while ((j+1)&&x<R[j])
        {
            R[j+1]=R[j];
            j--;
        }

        R[j+1]=x;
    }
}

void InsertSort(int*a,int len)
{
    /* 对数组a中的记录a[1..n]按递增序进行插入排序  */
    for (int i=1;i<len;i++)
    {
        int j=i,x=a[i];

        //若a[i]小于等于有序区中所有的a
        //从右向左在有序区a[1..i-1]中查找a[i]的插入位置
        while (j && a[j-1]>x)
            a[j]=a[j-1],j--;
        // R[i]插入到正确的位置上
        a[j]=x;
    }
}


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

    return 0;
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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