现在的位置: 首页 > 综合 > 正文

排序算法空间、时间复杂度

2013年09月12日 ⁄ 综合 ⁄ 共 964字 ⁄ 字号 评论关闭

排序算法空间、时间复杂度

简单排序法——
冒泡法是第二维循环中自己循环,找最小或最大值
选择排序和交换排序是第二维循环与第一维循环中的值比较;交换法最清晰,选择法作了改进,
只交换位置标号,算法复杂度没变。
插入法,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张(较为复杂)
高级排序法——
快速排序,从冒泡法改进得到,基本思想是任选一个记录,一般选取序列第一个,通过一趟排序将待排 记录分割成相邻的两个区域,其中一个区域中记录的关键字比另一个区域关键字都小,即一个区域的值都大于所取的关键字,另一个区域的指都小于所取的关键字, 则可以分别对这两个区域的记录进行排序,以达到整个序列有序。
将它区别于SHELL排序,后者是先有一个递减的步长数组,对相隔step-1的内容排列,然后改变步长,依次
下去。
归并排序,先在原记录中找一个中间位置(low+high)/2,对两段分别进行归并排序,最后再整体排序(即分三次)。
注意,快速排序没有最后整体排序,但一开始先排了一次。
堆排序,对选择排序的改进,利用堆的特性对记录序列进行排序。
时间复杂度
冒泡排序、选择排序和插入排序的比较次数为O(n2),最坏情况
O(n2),最好
O(n)
(但选择排序最好是
O(n2)
快速排序在平均情况下复杂性为O(nlogn),最坏情况
O(n2),最好O(nlogn)
堆排序和合并排序在最坏情况下复杂性为O(nlogn)。可见,合并排序和堆排序是比较排序算法中时间复杂度最优算法。
空间复杂度
空间性能是排序所需辅助空间大小
所有简单排序和堆排序都是0(1)
快速排序为0(logn),要为递归程序执行过程栈所需的辅助空间
归并排序和基数排序所需辅助空间最多,为O(n)
看个小代码
#include <stdlib.h>
main()
{   int  m,n,p;
//   scanf("m=%dn=%dp=%d",&m,&n,&p);
//   printf("%d%d%d/n",m,n,p);
m=3;
n=m&(-1);
p=m&&(-2);
   printf("%d%d/n",n,p);
}
一、
     n=m&(-1);中n恒等m
     p=m&&(-2);中p恒等1;(改称0则p为0)了
     -1的二进制为11;
二、
   屏蔽的两句使用时,应该
输入 m=1n=2p=3
不能 1 2 3

抱歉!评论已关闭.