当前位置: 首页 > 数据结构&&算法 > 正文

初探几种排序算法

                                                                                     

                                                                                     多种排序算法的总结(不包括复杂度的详细推算)

稳定排序与不稳定排序

   稳定排序:相同元素在排序中的相对位置不改变。

   不稳定排序:相同元素在排序中的相对位置改变。

内部排序与外部排序:

内部排序:待排的记录与内容都放在计算机的随机存储器中进行的排序过程

外部排序:一般指待排序记录的数量很大,以致内存中一次不能完全容纳全部的记录,在排序过程中,需要对外存进行访问的排序过程。

排序算法的复杂度:

      在此我们一般只要考虑的就是时间复杂度,当然个别排序的空间复杂度也很大,如希尔排序。这里时间复杂度的计算方法和一般复杂度计算方法类似。

     

按照排序的过程中所依据的不同可以分类为:

插入排序,交换排序,选择排序,归并排序,基数排序,二叉排序树排序


       插入排序:

                 利用有序表的插入操作进行排序

                 有序表的插入:将一个记录插入到已经安排好的有序表中,从而得到一个新的有序表。

                直接插入排序算法主要应用比较和移动两种操作。

                   

希尔排序(有一种直接插入排序的改进)

 方法:先将待排序列分割成为若干的子序列分别进行直接插入排序;待整个序列中的记录基本有序后,在进行一次直接插入排序。

希尔排序的时间复杂度:

       O(nlog2n)和O(N平方)之间大约O(N的1.3次方)

               
 

交换排序–冒泡排序

思想:通过不断比较相邻元素的大小,进行交换实现排序

 


交换排序–快速排序

冒泡排序的一种改进算法

    思想:以首记录作为轴记录,从前,后向扫描序列,通过交换,实现大值记录后移,小值记录前移,最终将轴记录安置在一个适当的位置(小值记录在前,大值记录在后)

 

 

轴记录将原序列分割成两个部分,依次对前后两部分重新设定轴记录,继而分别在进行快速排序。直至整个序列有序。

快速排序—-分割过程

快速排序是一个分治的算法

对于一个序列,取它的一个元素作为轴,把所有小与轴的元素放在它的左边,大于它的元素放在它的右边

分割算法:

     用临时变量对轴进行备份

取链噶个指针LOW 和HING ,他们的初始值就是序列的两端小表,在整个过程中保证LOW 不大于HIGH

移动两个指针

首先从HING 所知的位置向左搜索,找到第一个小与轴的元素,把这个元素放在LOW 的位置

在从LOW开始向右,找到第一个大与轴的元素,把它放在HING 的位置

重复上述过程,直到LOW=HIGH

把轴放在LOW 所指的位置

这样所有大于轴的元素北方在右边,所有小与轴的元素被放在左边。


时间复杂度:平均O(nlog2n)

空间复杂度:O(N平方)

快速排序是一种不稳定的排序方法

 

简单选择排序:

        每一趟都选出一个最大或最小的元素,并放在适当的位置。


归并排序:

         思想:将两个有序的序列合并成一个有序的序列,所以如果只有两个元素,所以归并排序就是将一个序列不停拆分,直到拆成一个一个元素为止,然后再进行合并排序。




版权声明:本文为博主原创文章,未经博主允许不得转载。

]]>

本文固定链接: http://zmrlinux.com/2015/05/11/%e5%88%9d%e6%8e%a2%e5%87%a0%e7%a7%8d%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95/ | Kernel & Me

该日志由 root 于2015年05月11日发表在 数据结构&&算法 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 初探几种排序算法 | Kernel & Me