学而不思则罔,思而不学则殆

有其事必有其理, 有其理必有其事

  IT博客 :: 首页 :: 联系 :: 聚合  :: 管理
  85 Posts :: 12 Stories :: 47 Comments :: 0 Trackbacks

从大的方面来说,排序可以分成内排序和外排序——内排序是外排序的基础。我们常用的内排序又可以粗略分成下面的类型:

    1.经典算法:如冒泡排序;

    2.插入排序及希尔排序;

    3.选择交换排序;

    4.堆排序;

    5.归并排序;

    6.快速排序。

别看排序有那么多种类型,但它们都离不开这样的核心思想   

 

一个待排序列总是被不断从无序序列转变为有序序

一。经典算法:冒泡排序
     
原理 :在每一遍历中,通过相邻元素的比较 (“冒泡”的比较形象),找到这趟遍历的最小值(或者最大值),并且放到合适的位置
     时间复杂度 O(n^2)


//////////////////////////////////////////////////////////////////////////
///// 冒泡排序
template
<typename T>
inline void my_swap(T
& l , T& r)
{
    T  tmp 
= l ;
    l 
=r ;
    r 
= tmp ;
}
 
template
<typename T>
void BubbleSort(T Arr[] ,
int N)
{    
    
for (int i= 0 ; i < N  ; i++ )
    {
        
for(int j= N-1 ; j > i ; j--)
        {
            
if (Arr[j] < Arr[j -1])
            {
                my_swap(Arr[j] , Arr[j 
-1])   ;
            }
        }
    }
}

 

 

二。插入排序:

   原理  每一趟处理一个元素,将该元素放于该元素之前的子数组(有序)中的正确位置,共需n-1趟。    时间复杂度 O(n^2)
   (思想来源玩扑克的时候,插牌)

 



template
<typename T>
void InsertSort(T Arr[] ,
int N)
{
    
int j ;
    
for (int p =1 ; p < N ;p++)
    {
        T tmp 
= Arr[p] ;
        
for (j = p ;j> 0 && tmp < Arr[j -1] ; j--)
        {
            Arr[j] 
= Arr[j-1]  ;
        }

        Arr[j] 
= tmp ;
    }
}

 
三 希尔排序

       


//////////////////////////////////////////////////////////////////////////
/// shell 发明者Donald Shell 该算法是冲破2次时间障碍的第一批算法,
///  通过比较一定间隔的元素工作,距离随着算法的进行而减小
//// 直到比较相邻元素最后一趟位置   ----》 也叫缩减增量排序
//// 最坏 Θ(O^2)  不同的增量最坏的时间复杂度 不一样                 
template<typename T>
void ShellSort(T Arr[] ,
int N)
{
    
for(int gap = N /2 ; gap > 0 ; gap /=2)
        
for(int i =gap ; i < N ; i++)
        {
            T tmp
= Arr[i] ;
            
int j= i ;
            
for( ; j>= gap && tmp<Arr[j -gap] ;j -= gap)
                Arr[j]  
=Arr[j -gap] ;
        
            Arr[j] 
=tmp  ;
        }
}

 

posted on 2012-06-20 11:58 易道 阅读(147) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法
只有注册用户登录后才能发表评论。