排序方法比较<转>

根据排序的原则,内排序可以分为:

• 插入排序
• 交换排序
• 选择排序
• 归并排序

预备知识:

1.等差数列之和:S=n*(a1+an)/2

等比数列之和:S=a1(1-q^n)/(1-q)

2.使用哨兵提高效率

比如基本的顺序查找我们可以这样做:

 

 

 

int search(int a[],int n,int key){

    for(int i=0;i<n;i++)

        if(a[i]==key)

            return i+1;         //返回第几个,而不是返回下标

    return 0;                       //返回0说明没有找到

}

注意到每次for循环都对边界进行检查(i<n),使用哨兵就不需要进行边界检查. 

 

 

int search(int a[],int n,int key){

    a[0]=key;

    for(int i=n;a[i]!=key;i--);

    return i;

}

但是使用哨兵的前提是在数组中a[1]--a[n]存储的是实际的元素,a[0]是拿来做哨兵的,即a的长度是n+1.

3.time()返回从1970年1月1日到现在的秒数,是实际时间。

clock返回开启进程和调用clock()之间的的CPU时钟计时单元(clock tick)数，不包括显式调用sleep()的时间,常用来测试任务执行的速度。

插入排序

简单插入排序

非常的简单，想想你玩牌的时候一边起牌,一边就把牌排好序了,那就是插入排序.

时间复杂度：O(N^2)，1+2+...+(N-1)=N^2/2。这是最坏的情况，其实大致上说插入排序的平均情况和最坏情况一样差。

空间上来讲，任一时刻最多只有一个数字在存储数组之外，属于原地排序,O(1)。

稳定的排序.

希尔排序

希尔排序利用利用了插入排序的两个特点:

• 基本有序时直接插入排序最快
• 对于数据很少的无序数列,直接插入也很快

谢尔排序的时间复杂度在O(nlogn)和O(n^2)之间,空间复杂度为O(1).

为了使集合基本有序,而不是局部有序,不能简单地逐段分割,而应将相距为某个”增量”的元素组成一个子序列.通常取增量为d₁=n/2,d_i+1=d_i/2.

交换排序

冒泡排序

把待排序的序列分为有序区和无序区,每次把无序区最大的数放到无序区的最后面,这样无序区的末元素成为有序区的首元素.

时间复杂度为O(n^2),空间复杂度O(1).

 快速排序

快速排序是对冒泡排序的改进,由于冒泡排序是不断比较相邻元素然后进行交换,需要比较移动多次才能到达最终位置.而快速排序的比较和移动是从两端向中间进行,因而元素移动的距离较远.

初始主轴的选取采用三元取中法.经过N趟排序,当元素已基本有序后采用直接插入排序法.

 理想情况下,每次划分左右两侧的序列长度是相同的,长度为n的序列可划分为logn层.定位一个元素要对整个序列扫描一遍,所需时间为O(n),总的时间复杂度为O(nlogn).

如果每次都取最左边的元素作主轴，最坏情况下待排序列完全有序(正序或逆序),每次划分只得到比上一次少一个的子序列,总的比较次数为1+2+3+...+(n-1)=O(n^2).

平均来说快速排序的时间复杂度为O(nlogn),栈的深度为O(logn).

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

选择排序

简单选择排序

简单选择排序和冒泡排序很像,每趟排序把把无序序列中最小的元素放到有序列的最后面,有序序列在前,无序序列在后.但有一个重要的区别:冒泡排序在一趟排序中边比较,边交换；而简单选择排序在一趟排序中只作一次交换.

简单选择排序是稳定的,时间复杂度为O(n^2),空间复杂度为O(1).

堆排序

堆排序是对简单选择排序的改进,在简单选择排序中前一次的比较结果没有保存下来,后一趟排序中反复对以前已经做过的比较重新做了一遍.

时间复杂度为O(nlogn),不稳定的排序.

归并排序

二路归并（用内存太多了，不用了。）

 

总结

 

 

 

 

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
直接插入	O(n^2)	O(n)	O(n^2)	O(1)	是
希尔	O(nlogn)~O(n^2)	O(n^1.3)	O(n^2)	O(1)	否
冒泡	O(n^2)	O(n)	O(n^2)	O(1)	是
快速	O(nlogn)	O(nlogn)	O(n^2)	O(nlogn)~O(n)	否
简单选择	O(n^2)	O(n^2)	O(n^2)	O(1)	是
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	否
归并	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	是

注:冒泡排序采用pos来标记已有序的序列位置后,最好情况才是O(n),如果没有采用此改进算法,最好情况也是O(n^2).我们的快速排序每次都把主轴放在vec[0]中,没用另外使用单独的变量,所以辅助空间为O(1),否则就是O(nlogn)~O(n).

http://www.cnblogs.com/zhangchaoyang/articles/1812997.html