文档章节

经典排序算法和C++ stl 排序算法

刘大神
 刘大神
发布于 2015/05/21 16:50
字数 3108
阅读 253
收藏 0

经典排序算法和C++ stl 排序算法

1.经典排序算法

    1.1 冒泡排序

    1.2 选择排序

    1.3 直接插入排序

    1.4 归并排序

    1.5 快速排序

    1.6 希尔排序

    1.7 堆排序

2. C++ stl 排序算法

    2.1 sort

3. inline

1.经典排序算法

    1.1冒泡排序

        何为冒泡排序?即像冒泡一样,将大数放在前面,小数放在后面,像冒泡一样的排序方式。

        那么冒泡排序的原理又是什么呢?冒泡算法的基本原理是:依次比较相邻的两个数,将较大数放在前面,较小数放在后面。即比较第1个和第2个数,将大数放前,小数放后,再接着比较第2个数和第3个数,将大数放前,小数放后,如此继续,直到比较最后2个数。此时,第1轮结束,如此,在第1轮之后,位于最后的数必是最小的数。然后使用上一轮的结果重复第一轮的过程,将所有的最小数都放在后面。到所有的数都已经有序时,算法结束。

        算法实现:

   1: void BubbleSort(int *pData,int Count) 
   2: {
   3:     int iTemp;
   4:     for(int i=1;i<Count;++i)
   5:     {
   6:         for(int j=Count-1;j>=i;j--)
   7:         {
   8:             if(pData[j]<pData[j-1])
   9:             {
  10:                 iTemp = pData[j-1];
  11:                 pData[j-1] = pData[j];
  12:                 pData[j] = iTemp; 
  13:              } 
  14:          }
  15:      } 
  16: }

ps:冒泡排序效率还可以优化。

1.2 选择排序

    何为选择排序呢?即:从需要排序的队列中,选择最小的数同第一个交换,再从剩下的队列中选择最小的数同第二个交换,循环执行下去,直到实现全队列的排序。

   算法实现:

   1: void SelectSort(int *pData, int Count)
   2: {
   3:     int iTemp;
   4:     int iPos;
   5:     for (int i = 0; i < Count - 1; i++)
   6:     {
   7:         iTemp = pData[i];
   8:         iPos = i;
   9:         for (int j = i + 1; j < Count; j++)
  10:         {
  11:             if (pData[j] < iTemp)
  12:             {
  13:                 iTemp = pData[j];
  14:                 iPos = j;
  15:             }
  16:         }
  17:         pData[iPos] = pData[i];
  18:         pData[i] = iTemp;
  19:     }
  20: }

1.3 直接插入排序

    何为直接插入排序呢?这种排序较为复杂,它的基本工作原理是:可以做个比喻,抽出牌,在前面的牌中找到适合的位置插进去。

    算法实现:

   1: void InsertSort(int *pData, int Count)
   2: {
   3:     int iTemp;
   4:     int iPos;
   5:     for (int i = 0; i < Count; i++)
   6:     {
   7:         iTemp = pData[i];
   8:         iPos = i - 1;
   9:         while(iPos >= 0 && iTemp < pData[iPos])
  10:         {
  11:             pData[iPos + 1] = pData[iPos];
  12:             iPos--;
  13:         }
  14:         pData[iPos + 1] = iTemp;
  15:     }
  16: }

 

1.4 归并排序

何为归并排序呢?归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。

算法实现,不予以给出。此处不作重点。

 

 

1.5 快速排序

何为快速排序呢?算法通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

一趟快速排序的算法是:

1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;

2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];

3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;

4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;

5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

算法实现:

   1: void Qsort(int a[], int low, int high) {
   2:     if (low >= high)
   3:     {
   4:         return;
   5:     }
   6:     int first = low;
   7:     int last = high;
   8:     int key = a[first];
   9:     while (first < last)
  10:     {
  11:         while (first < last && a[last] >= key)
  12:         {
  13:             --last;
  14:         }
  15:         a[first] = a[last];
  16:         while (first < last && a[first] <= key)
  17:         {
  18:             ++first;
  19:         }
  20:         a[last] = a[first];
  21:     }
  22:     a[first] = key;
  23:     Qsort(a, low, first - 1);
  24:     Qsort(a, first + 1, high);
  25: }

1.6 希尔排序

何为希尔排序呢?希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。

 

 

1.7 堆排序

何为堆排序呢?堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。

堆排序原理:堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

算法实现:

   1: //本函数功能是:根据数组array构建大根堆 
   2: void HeapAdjust(int array[],int i,int nLength)
   3: {   
   4:     int nChild;    
   5:     int nTemp;    
   6:     for(;2*i+1<nLength;i=nChild)    
   7:     {         //子结点的位置=2*(父结点位置)+1     
   8:         nChild=2*i+1;         //得到子结点中较大的结点       
   9:         if(nChild<nLength-1&&array[nChild+1]>array[nChild])++nChild;    
  10:         //如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点        
  11:         if(array[i]<array[nChild])     
  12:         {          
  13:             nTemp=array[i];       
  14:             array[i]=array[nChild];      
  15:             array[nChild]=nTemp;        
  16:         }
  17:         else break; //否则退出循环     
  18:     }
  19: }
  20: //堆排序算法
  21: void HeapSort(int array[],int length)
  22: {    
  23:     int i;     //调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素     //length/2-1是最后一个非叶节点,此处"/"为整除    
  24:     for(i=length/2-1;i>=0;--i)   
  25:         HeapAdjust(array,i,length);  
  26:     //从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素     
  27:     for(i=length-1;i>0;--i)   
  28:     {         //把第一个元素和当前的最后一个元素交换,         //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的   
  29:         array[i]=array[0]^array[i];      
  30:         array[0]=array[0]^array[i];     
  31:         array[i]=array[0]^array[i];         //不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值       
  32:         HeapAdjust(array,0,i);   
  33:     }
  34: }

 

2 C++ STL 排序算法

2.1 sort

sort是stl标准库提供的,比较高效的算法。sort是通过分割法,集成快速排序,插入排序和堆排序为一体的算法。

源码:

   1: template<class _RanIt,
   2: class _Pr> inline
   3:     void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)
   4: {    // order [_First, _Last), using _Pred
   5:         _DEBUG_RANGE(_First, _Last);
   6:         _DEBUG_POINTER(_Pred);
   7:         _Sort(_Unchecked(_First), _Unchecked(_Last), _Last - _First, _Pred);
   8:     }
   9: 
  10: // TEMPLATE FUNCTION sort
  11: template<class _RanIt> inline
  12: void sort(_RanIt _First, _RanIt _Last)
  13: {    // order [_First, _Last), using operator<
  14:     _STD sort(_First, _Last, less<>());
  15: }

    首先,我们来看sort函数的声明。stl为sort提供了2个版本的声明,一个是只有2个迭代器参数的声明,一个是除了2个迭代器参数之外还有一个用于使用<的一个方法。即:第2版本的sort的第3个参数可以是一个Compare算法的函数。

    这里就要注意了:

                第一点:这个2个迭代器参数的使用,sort的参数要求,你传进来的2个迭代器参数必须是随机的迭代器,这样才能保证内部算法的赋值等其他的操作的实现,所以,这个迭代器应该是一个随机的可读可写的迭代器。(ps:这里为什么不使用指针,而是使用迭代器呢?那是因为迭代器是一种抽象的对象,它能够遍历标准模版库中的容易的部分或全部元素。这样可以更加高效的执行算法。)

                第二点:在sort的第2个版本中的第3个参数,我们就叫它compare参数吧(不是正规叫法哈),它是采用严格弱排序,严格是是说,在判断的时候会用“<” ,弱排序是因为一旦“<” 成立便认为存在“<”关系,返回true,而忽略“=”和“>”关系,返回false,这也是执行sort不保证稳定性的原因。

下面是sort方法中的定义:

2.1.1sort中的快排

   1: template<class _RanIt,
   2: class _Diff,
   3: class _Pr> inline
   4:     void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
   5: {    // order [_First, _Last), using _Pred
   6:         _Diff _Count;
   7:         for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal;)
   8:         {    // divide and conquer by quicksort
   9:             pair<_RanIt, _RanIt> _Mid =
  10:                 _Unguarded_partition(_First, _Last, _Pred);
  11:             _Ideal /= 2, _Ideal += _Ideal / 2;    // allow 1.5 log2(N) divisions
  12: 
  13:             if (_Mid.first - _First < _Last - _Mid.second)
  14:             {    // loop on second half
  15:                 _Sort(_First, _Mid.first, _Ideal, _Pred);
  16:                 _First = _Mid.second;
  17:             }
  18:             else
  19:             {    // loop on first half
  20:                 _Sort(_Mid.second, _Last, _Ideal, _Pred);
  21:                 _Last = _Mid.first;
  22:             }
  23:         }
  24: 
  25:         if (_ISORT_MAX < _Count)
  26:         {    // heap sort if too many divisions
  27:             _STD make_heap(_First, _Last, _Pred);
  28:             _STD sort_heap(_First, _Last, _Pred);
  29:         }
  30:         else if (1 < _Count)
  31:             _Insertion_sort(_First, _Last, _Pred);    // small
  32:     }

2.1.2 sort中的插入排序

   1: template<class _BidIt,
   2:     class _Pr> inline
   3:     void _Insertion_sort(_BidIt _First, _BidIt _Last, _Pr _Pred)
   4:     {    // insertion sort [_First, _Last), using _Pred
   5:     _Insertion_sort1(_First, _Last, _Pred, _Val_type(_First));
   6:     }
   7: template<class _BidIt,
   8:     class _Pr,
   9:     class _Ty> inline
  10:     void _Insertion_sort1(_BidIt _First, _BidIt _Last, _Pr _Pred, _Ty *)
  11:     {    // insertion sort [_First, _Last), using _Pred
  12:     if (_First != _Last)
  13:         for (_BidIt _Next = _First; ++_Next != _Last; )
  14:             {    // order next element
  15:             _BidIt _Next1 = _Next;
  16:             _Ty _Val = _Move(*_Next);
  17: 
  18:             if (_DEBUG_LT_PRED(_Pred, _Val, *_First))
  19:                 {    // found new earliest element, move to front
  20:                 _Move_backward(_First, _Next, ++_Next1);
  21:                 *_First = _Move(_Val);
  22:                 }
  23:             else
  24:                 {    // look for insertion point after first
  25:                 for (_BidIt _First1 = _Next1;
  26:                     _DEBUG_LT_PRED(_Pred, _Val, *--_First1);
  27:                     _Next1 = _First1)
  28:                     *_Next1 = _Move(*_First1);    // move hole down
  29:                 *_Next1 = _Move(_Val);    // insert element in hole
  30:                 }
  31:             }
  32:     }

2.1.3 sort中的堆排序1   建堆算法

   1: template<class _RanIt,
   2:     class _Pr> inline
   3:     void make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
   4:     {    // make [_First, _Last) into a heap, using _Pred
   5:     _DEBUG_RANGE(_First, _Last);
   6:     _DEBUG_POINTER(_Pred);
   7:     if (1 < _Last - _First)
   8:         _Make_heap(_Unchecked(_First), _Unchecked(_Last), _Pred,
   9:             _Dist_type(_First), _Val_type(_First));
  10:     }
  11: template<class _RanIt,
  12:     class _Diff,
  13:     class _Ty,
  14:     class _Pr> inline
  15:     void _Make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *, _Ty *)
  16:     {    // make nontrivial [_First, _Last) into a heap, using _Pred
  17:     _Diff _Bottom = _Last - _First;
  18:     for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
  19:         {    // reheap top half, bottom to top
  20:         --_Hole;
  21:         _Ty _Val = _Move(*(_First + _Hole));
  22:         _Adjust_heap(_First, _Hole, _Bottom,
  23:             _Move(_Val), _Pred);
  24:         }
  25:     }

2.1.3 sort中的堆排序2 堆排序算法

   1: template<class _RanIt,
   2:     class _Pr> inline
   3:     void sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
   4:     {    // order heap by repeatedly popping, using _Pred
   5:     _DEBUG_RANGE(_First, _Last);
   6:     _DEBUG_POINTER(_Pred);
   7:     _DEBUG_HEAP_PRED(_First, _Last, _Pred);
   8:     _Sort_heap(_Unchecked(_First), _Unchecked(_Last), _Pred);
   9:     }
  10: 
  11: template<class _RanIt,
  12:     class _Pr> inline
  13:     void _Sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
  14:     {    // order heap by repeatedly popping, using _Pred
  15:     for (; 1 < _Last - _First; --_Last)
  16:         _Pop_heap(_First, _Last, _Pred);
  17:     }
  18: 

 

3. inline

    1.先扼要的说说什么是inline吧:

    在C++中,相对于C来说,引入了inline关键字,inline关键字用来定义一个类的内联函数,引入inline的主要原因是为了代替C中的表达式样式的宏,例如:

           #define ExpressionName(Var1,Var2) ((Var1)+(Var2))*((Var1)-(Var2))

2 下面再说说inline关键字的好处:

    1)inline定义的类的内联函数,函数的代码存在符号集中,在使用的时候随时替换(像宏一样),这样做既省去了创建函数的开销,又提高了效率;

    2)就算函数被定义成了inline,其依然是函数,编译器在调用内联函数的时候依然遵循正常函数的检查过程,这样就消除了内联函数的隐患和 局限性;

    3)inline 可以作为某个类的成员函数,这样,就可以在其中使用该类的私有成员及保护成员。

3 最后再说说 使用inline需要注意的地方:

    内联函数一般只会用在函数内容非常简单的时候,这是因为,内联函数的代码会在任何调用它的地方展开,如果函数太复杂,代码膨胀带来的恶果很可能会大于效率的提高带来的益处。内联函数最重要的使用地方是用于类的存取函数。

 

 

 

ps:以上就是作者对排序算法的见解,此见解纯属个人见解,如有不当之处,欢迎指正。

© 著作权归作者所有

刘大神
粉丝 8
博文 21
码字总数 18133
作品 0
朝阳
高级程序员
私信 提问
腾讯阿里网易游戏华为科大讯飞面经

本人是一非科班妹子,在找实习的过程中面试了腾讯、阿里、网易游戏、华为、科大讯飞(面试的顺序),前面三个都挂了。。。 1.腾讯提前批——游戏客户端开发 自我介绍+项目经历(问的很细) ...

牛客网
2018/06/13
0
0
STL vector+sort排序和multiset/multimap排序比较

本文由 www.169it.com 搜集整理 在C++的STL库中,要实现排序可以通过将所有元素保存到vector中,然后通过sort算法来排序,也可以通过multimap实现在插入元素的时候进行排序。在通过vector+so...

小星星程序员
2014/11/05
0
0
C++ STL编程轻松入门 3

2 牛刀小试:且看一个简单例程   2.1 引子   如果你是一个纯粹的实用主义者,也许一开始就可以从这里开始看起,因为此处提供了一个示例程序,它可以带给你有关使用STL的最直接的感受。是...

暖冰
2015/11/21
0
0
STL系列之四 heap 堆

下面再介绍STL中与堆相关的4个函数——建立堆make_heap(),在堆中添加数据push_heap(),在堆中删除数据pop_heap()和堆排序sort_heap(): 头文件 #include 下面的_First与_Last为可以随机访问...

彭博
2012/04/12
693
0
STL系列之四 heap 堆

下面再介绍STL中与堆相关的4个函数——建立堆make_heap(),在堆中添加数据push_heap(),在堆中删除数据pop_heap()和堆排序sort_heap(): 头文件 #include 下面的_First与_Last为可以随机访问...

长平狐
2012/12/10
87
0

没有更多内容

加载失败,请刷新页面

加载更多

抽象同步队列AQS——AbstractQueuedSynchronizer锁详解

AQS——锁的底层支持 谈到并发,不得不谈ReentrantLock;而谈到ReentrantLock,不得不谈AbstractQueuedSynchronizer(AQS)! 类如其名,抽象的队列式的同步器,AQS定义了一套多线程访问共享资...

须臾之余
今天
2
0
springboot配置百度UEditor 富文本详解

富文本简介 UEditor是由百度web前端研发部开发所见即所得富文本web编辑器,具有轻量,可定制,注重用户体验等特点,开源基于MIT协议,允许自由使用和修改代码... 准备工作 ueditor需要单独文...

wotrd
昨天
3
0
mysql 5.7之my.cnf配置大全

[client]port = 3306socket = /tmp/mysql.sock[mysqld]###############################基础设置######################################Mysql服务的唯一编号 每个mysql服务...

Online_Reus
昨天
2
0
MAVEN打包时引入外部链接的包

1.项目引入了ORACLE的jar包,MAVEN配置如下 2.打jar包的时候需要指定下main入口函数mainClass <dependency> <groupId>com.oracle</groupId> <artifactId>ojdbc6</artifactId> ......

Cobbage
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部