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

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

简单排序法——

冒泡法是第二维循环中自己循环，找最小或最大值

选择排序和交换排序是第二维循环与第一维循环中的值比较；交换法最清晰，选择法作了改进，

只交换位置标号，算法复杂度没变。

插入法，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张（较为复杂）

高级排序法——

快速排序，从冒泡法改进得到，基本思想是任选一个记录，一般选取序列第一个，通过一趟排序将待排 记录分割成相邻的两个区域，其中一个区域中记录的关键字比另一个区域关键字都小，即一个区域的值都大于所取的关键字，另一个区域的指都小于所取的关键字， 则可以分别对这两个区域的记录进行排序，以达到整个序列有序。

将它区别于SHELL排序，后者是先有一个递减的步长数组，对相隔step-1的内容排列，然后改变步长，依次

下去。

归并排序，先在原记录中找一个中间位置（low+high）/2，对两段分别进行归并排序，最后再整体排序（即分三次）。

注意，快速排序没有最后整体排序，但一开始先排了一次。

堆排序，对选择排序的改进，利用堆的特性对记录序列进行排序。

时间复杂度

冒泡排序、选择排序和插入排序的比较次数为O(n²)，最坏情况 O(n²)，最好O(n)

（但选择排序最好是 O(n²)）

快速排序在平均情况下复杂性为O(nlogn)，最坏情况 O(n²)，最好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