分类： C/C++
2015-06-03 11:47:23
1.简单选择排序 2.堆排序 (1和2是属于选择排序，都是选择最大的，与当前的交换)
3.直接插入排序 4.希尔排序 (3和4属于插入排序,有时把改进后的直接插入排序叫做二分插入：根据插入排序的思想，在插入待排序列的第i个元素时，由于前面的序列已经有序，因此可以使用二分法寻找第i个元素的正确位置。最好O(N*log))
5.冒泡排序 6.快速排序 (5和6属于交换排序.交换排序顾名思义是不停的交换数据位置.但实际上选择排序也在不停的交换元素,但次数较少,只有找到最大值才一次交换.侧重点还是在通过遍历或堆来选择出最值.而冒泡排序就是通过不停交换相邻元素得出最大值,快速排序也在不停交换元素使序列一步步接近有序.侧重在交换)
7.基数排序 8.桶排序 (7和8属于分配排序)
（基数排序：将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序(我们常用上一篇blog介绍的计数排序算法, 因为每个位可能的取值范围是固定的从0到9).这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.）
另外要注意的是:算法思想的本身是独立于编程语言的,所以你写代码去实现算法的时候很多细节可以做不同的处理.采用不稳定算法不管你具体实现时怎么写代码,最终相同元素位置总是不确定的(可能位置没变也可能变了).而稳定排序算法是你在具体实现时如果细节方面处理的好就会是稳定的,但有些细节没处理得到的结果仍然是不稳定的.
比如冒泡排序,直接插入排序,归并排序虽然是稳定排序算法,但如果你实现时细节没处理好得出的结果也是不稳定的.
它体现了程序的健壮性.比如你网站上针对最热门的文章或啥音乐电影之类的进行排名.由于这里排名不会像我们成绩排名会有并列第几名之说.所以出现了元素相等时也会有先后之分.如果添加进新的元素之后又要重新排名了.之前并列名次的最好是依然保持先后顺序才比较好.稳定性算法: 冒泡排序， 直接插入排序 , 归并排序 ，基数排序（因为每一位都是稳定排序）
不稳定性算法: 选择排序，希尔排序, 快速排序, ,堆排序 桶排序
(1)基数排序(稳定)与桶排序(不稳定)
这两种算法都是属于分配排序算法.(利用元素值本身的信息直接映射到一个辅助序列中变成有序的.而不是通过与其他元素比较确定顺序位置)
基数排序因为在是把低位按顺序映射到一个临时序列中去,是依次序映射,没有涉及到数据位置的变动.然后再按高位顺序映射.所以相同元素也是按次序映射过去.所以是稳定的
如果数据元素没有重复的则采用简单桶排序,此时没有重复元素,所以自然不存在稳不稳定这一说.如果有重复元素得用改进的桶排序.此时辅助的临时数组只是通过索引来识别待排序元素的键值.丢失了其他信息(这是所有采用辅助的临时序列的算法中唯一一个会丢失信息的算法).假如待排序元素是一个map类型,按它的键值来排序.其他算法采用辅助序列时是把map类型做为元素去考虑的.而只有改进的桶排序不会把map类型当元素,只是利用到了键值信息. 这样一来就无法区分键值相同的信息,因此自然是不稳定的算法了啊.
(2)归并排序(稳定)
归并排序使得了递归的思想,把序列递归的分割成小序列,然后合并排好序的子序列.当有序列的左右两子序列合并的时候一般是先遍历左序列,所在左右序列如果有相等元素,则处在左边的仍然在前,这就稳定了.但是如果你非得先遍历右边序列则算法变成不稳定的了.虽然这样排出来的序也是对的,但变成了不稳定的,所以是不太好的实现.
(3)简单选择排序(不稳定)与堆排序(不稳定)
这两种算法都属于选择排序.(从待排序的元素中挑选出最大或最小值.下面的例子以最小值为例)
简单选择排序由于选出最小值后需要交换位置,位置一变就会变得不稳定.例如8 3 8 1.当从左往右遍历找最小值时,找到了1,这就需要把8跟1交换.这样两个相等元素8的位置就变了.
堆排序的话,也会存在跟上面一样的交换最大值的位置会导致不稳定.例如有大堆 8 8 6 5 2.先选出第一个最大值8,放最末尾.此时就不稳定了.因为第二个8就跑它前面去了.
(4)冒泡排序(稳定)与快速排序(不稳定)
这两种算法都属于交换排序.
冒泡是通过不停的遍历,以升序为例,如果相邻元素中左边的大于右边的则交换.碰到相等的时就不交换保持原位.所以是稳定的.当然如果你非得吃饱了撑着了,在碰到相等的时也交换下,那肯定变成不稳定的算法了.
快速排序是不稳定的.举例8 5 6 6 .以8为基准,第一趟交换后最后一个6跑到第一位,8到最后.第二趟交换.这个6跑到5的位置.变成有序的了.两个6位置变了,所以是不稳定的.
(5)直接插入(稳定),二分插入排序(不稳定)与希尔排序(不稳定)
直接插入时是先在已排序好的的子序列中找到合适的位置再插入.假设左边是已排序的,右边是没排序的.通过从后向前遍历已排序序列,然后插入,此时相等元素依然可以保持原有位置.但是如果你从前向后遍历已排序序列就会是不稳定排序了.
二分插入排序是不稳定的,因为通过二分查找时得到的位置不稳定.例如3 4 4 5 4.但把最后一个4插入时肯定会跑到第二个4前面去了.所以是不稳定的.
1.只要不涉及到两个元素之间位置的交换就肯定是稳定的排序算法.比如归并排序,基数排序.(桶排序不稳定是个特例,因为它丢失了附带信息,不然的话可以弄成稳定排序的)
2.在涉及到不同位置元素交换的算法中除了冒泡和直接插入排序是稳定的,其他都是不稳定的.
你可以这样想,之所以出现相同元素位置变了就是其中一个交换位置时从另一个头顶跳过去了,而冒泡算法是相邻位置互换,跳不过去的,碰到相等元素的时候就停住不交换了.
而直接插入排序是往已排好序的序列中插入.所以你通过由后往前遍历碰到相等的时就停住,这样也能保持稳定.但记住一定得从后往前遍历,不然也会不稳定.(所以说直接插入是半稳吧,而冒泡是非常的稳啊,除非你闲得蛋痛非得把两相等的元素两两交换)
n^2表示n的平方,选择排序有时叫做直接选择排序或简单选择排序
| 排序方法 | 平均时间 | 最好时间 | 最坏时间 |
| 桶排序(不稳定) | O(n) | O(n) | O(n) |
| 基数排序(稳定) | O(n) | O(n) | O(n) |
| 归并排序(稳定) | O(nlogn) | O(nlogn) | O(nlogn) |
| 快速排序(不稳定) | O(nlogn) | O(nlogn) | O(n^2) |
| 堆排序(不稳定) | O(nlogn) | O(nlogn) | O(nlogn) |
| 希尔排序(不稳定) | O(n^1.25) | ||
| 冒泡排序(稳定) | O(n^2) | O(n) | O(n^2) |
| 选择排序(不稳定) | O(n^2) | O(n^2) | O(n^2) |
| 直接插入排序(稳定) | O(n^2) | O(n) | O(n^2) |
http://www.cnblogs.com/pugang/archive/2012/07/02/2573075.html
快速排序 考虑如下极端情况，
最好情况，每次一分为二都很均匀，此时为log2N;（平均情况下表达式复杂，经证明，也是O（N*logN）数量级的）
最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空,即
T[n] = T[n-1] + T[1] + O(n)
这一次的划分白玩了，划分之后一边是一个，一边是n-1个，这种极端情况的时间复杂度就是O(n2).
冒泡:最好情况是序列有序，第一遍循环就没有发生交换，则跳出外城循环。
直接插入：外层循环以进行n-1次插入（O(N))），每次插入时，最好的情况时进行一次比较，不进入内存循环，零次交换（正序）；最差的情况是进行i次比较，i+2次交换（逆序）；
所以最好是O(N)，最差是O(N^2)
O(n)这样的标志叫做渐近时间复杂度,是个近似值.各种渐近时间复杂度由小到大的顺序如下
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
一般时间复杂度到了2^n(指数阶)及更大的时间复杂度,这样的算法我们基本上不会用了,太不实用了.比如递归实现的汉诺塔问题算法就是O(2^n).
平方阶(n^2)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.
冒泡排序,简单选择排序,堆排序(堆是满树，可以用数组来表示。为了节省空间，可以用原数组来的后半部分空间存放排序后的数组，这样就不需额外空间了),直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)
快速排序空间复杂度为logn(因为临时变量在递归调用中定义) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.
基数排序的空间复杂是O(n),桶排序的空间复杂度不确定
所有排序算法中最快的应该是桶排序(很多人误以为是快速排序,实际上不是.不过实际应用中快速排序用的多)但桶排序一般用的不多,因为有几个比较大的缺陷.
1.待排序的元素不能是负数,小数.
2.空间复杂度不确定,要看待排序元素中最大值是多少.
所需要的辅助数组大小即为最大元素的值.
