学而不思则罔，思而不学则殆

有其事必有其理， 有其理必有其事

  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 易道 阅读(231) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法
只有注册用户登录后才能发表评论。